LL1语法分析器B1921.docx
《LL1语法分析器B1921.docx》由会员分享，可在线阅读，更多相关《LL1语法分析器B1921.docx（17页珍藏版）》请在冰点文库上搜索。
LL1语法分析器B1921
实验报告
（2014/2015学年第二学期）
课程名称
编译原理
实验名称
语法分析器的构造
实验时间
2015
年
5
月
29
日
指导单位
计算机学院软件工程系
指导教师
蒋凌云
学生姓名
Cjj
班级学号
B---------
学院（系）
计算机学院
专业
NIIT
成绩
批阅人
日期
实验报告
实验名称
语法分析器的构造
指导教师
蒋凌云
实验类型
上机
实验学时
4
实验时间
2015-5-14
一、实验目的和要求
设计、编制、调试一个LL
（1）语法分析程序，利用语法分析器对符号串进行识别，加深对语法分析原理的理解。
要求设计并实现一个LL
（1）语法分析器，实现对算数文法E->E+T|TT->T*F|FF->（E）|i所定义的符号串进行识别。
二、实验环境（实验设备）
MacOSX+Python
三、实验原理及内容
AnalyseMachine:
Load（）方法载入文法规则，自动求出First集，Follow集，分析表
Judge（）方法判断某一字符串是否为当前文法的句子
程序代码
#coding:
utf-8
#LL
（1）分析法
#By:
Importcjj
#由于仓促，代码有很多地方不是科学，但是基本功能已经实现
#2015-6-15
classAnalyseMachine（object）:
def__init__（self）:
pass
defload（self,Grammers）:
"""载入文法规则
参数
Grammers:
文法的规则列表
"""
self.Grammers=Grammers
self.noLeftRecursionGrammers=self.__NoLeftRecursion（self.Grammers）
self.start=self.Grammers[0][0]
self.nChars=self.__GetVn（self.noLeftRecursionGrammers）
self.tChars=self.__GetVt（self.noLeftRecursionGrammers）
self.firstSet=self.FirstSet（self.noLeftRecursionGrammers）
self.followSet=self.FollowSet（self.noLeftRecursionGrammers）
self.analyseTable=self.AnalyseTable（self.noLeftRecursionGrammers,self.firstSet,self.followSet）
defJudge（self,string）:
"""判断字符串是否为当前文法的句子
"""
isMatch=False
analyseStack=["#",self.start]
StringStack=list（string）+["#"]
printu"="*25,u"判断字符串=%s"%string,u"="*25
print"%-30s%-12s%s"%（u"分析栈",u"余留输入串",u"所用生成式"）
try:
whileanalyseStack:
xm=analyseStack[-1]
ai=StringStack[0]
print"%-20s%20s%10s"%（"".join（analyseStack）,"".join（StringStack）,""）,
ifxminself.nChars:
analyseStack.pop（）
expression=self.analyseTable[xm][ai]
ifexpression=="ERROR":
print
raiseValueError
printexpression,
index=expression.find（":
:
="）+3
ifself.__Split（expression[index:
]）[:
:
-1]!
=["~"]:
analyseStack+=self.__Split（expression[index:
]）[:
:
-1]#逆序加入
elifxm==aiandxm!
="#":
analyseStack.pop（）
StringStack.pop（0）
elifxm==aiandxm=="#":
analyseStack.pop（）
isMatch=True
print
exceptExceptionase:
pass
result=u"%s为文法定义的句子"ifisMatchelseu"%s不是文法定义的句子"
printresult%string
printu"="*25,u"判断字符串=%s"%string,"="*25
returnisMatch
defFirstSet（self,Grammers）:
"""构造文法的First集
"""
speSymbol=":
:
="
Vn=self.nChars
Vt=self.tChars
First=self.__SubExpressions（Grammers）
#新建一个以所有非终结符作为键，以空列表作为值的字典
FirstDict={}
fornCharinVn:
FirstDict[nChar]=[]
lock=1
whileFirstandlock<100:
fornCharinVn:
ifFirst.has_key（nChar）:
#如果nChar的First还没求完毕
first=First[nChar]
forcharsinfirst:
char=chars[0]
ifcharinVt:
#如果子规则的第一个符号是终结符，直接加入First集
FirstDict[nChar].append（char）
First[nChar].remove（chars）
else:
#isinVn
ifcharnotinFirst:
#char是非终结符而且他的First集已经求解完毕
FirstDict[nChar]+=FirstDict[char]#把该非终结符的First集（除”~“外加入nChar的First集中）
First[nChar].remove（chars）
if"~"inFirstDict[char]:
FirstDict[nChar].remove（"~"）
First[nChar].append（chars[1:
]）#如果该终结符的First中含有”~“，那么他的下一个符号的First集也需要被继续计算
else:
pass
ifnotFirst[nChar]:
#如果子规则全部检查计算完毕，那么删去First中以nChar作为键的键值对
First.pop（nChar）
lock+=1
iflock==100:
print"Warning!
thelooplockisworking.."
returnFirstDict
defFollowSet（self,Grammers）:
"""构造文法的Follow集
"""
Vn=self.nChars
Vt=self.tChars
Follow=self.__SubExpressions（Grammers）
#新建一个以所有非终结符作为键，以空列表作为值的字典
FollowDict={}
fornCharinVn:
FollowDict[nChar]=[]
#rule1----------------”#加入文法的开始符号的Follow集“
FollowDict[Vn[0]].append（"#"）
#rule2----------------
firstSet=self.firstSet
followLink={}
fornCharinVn:
followLink[nChar]=[]
fornChar,expressioninFollow.items（）:
forsubExpressioninexpression:
subExpression=self.__Split（subExpression）
forcharinsubExpression[:
-1]:
ifcharinVn:
index=subExpression.index（char）+1
string=subExpression[index:
]
followLink[char].append（''.join（string））
#printfollowLink
fornChar,stringListinfollowLink.items（）:
forstringinstringList:
string=self.__Split（string）
forcharinstring:
#print"string",string
ifcharinVt:
FollowDict[nChar].append（char）
break
else:
firstSetOfChar=firstSet[char]
#print"nchar=%schar=%sfirstSetOfChar=%s"%（nChar,char,firstSetOfChar）
FollowDict[nChar]+=firstSetOfChar
if"~"infirstSetOfChar:
FollowDict[nChar].remove（"~"）
else:
break
#rule3----------------
#先求出能推倒出”~“的非终结符
nilChar=[]
fornChar,subExpressionsinFollow.items（）:
if"~"insubExpressions:
nilChar.append（nChar）
nilChar.append（''）
followLink2={}
fornCharinVn:
followLink2[nChar]=[]
fornChar,subExpressionsinFollow.items（）:
#print"ncahr=%s,subExpressions="%nChar,subExpressions
forexpressioninsubExpressions:
expression=self.__Split（expression）
index=len（expression）-1
whileindex>=0:
char=expression[index]
ifchar==nChar:
break
elifcharinVt:
break
elifcharnotinnilChar:
followLink2[char].append（nChar）
#print"1add%stofollow%s"%（nChar,char）
break
else:
followLink2[char].append（nChar）
#print"2add%stofollow%s"%（nChar,char）
index-=1
#printfollowLink2
hasFollowChar=[]
notFollowChar=[]
fornChar,linksinfollowLink2.items（）:
ifnotlinks:
hasFollowChar.append（nChar）
else:
notFollowChar.append（nChar）
#printhasFollowChar
#printnotFollowChar
lock=1
whilenotFollowCharandlock<100:
delChar=[]
fornCharinnotFollowChar:
#print"nCharis%s"%nChar
ifset（followLink2[nChar]）.issubset（set（hasFollowChar））:
forlinkinfollowLink2[nChar]:
FollowDict[nChar]+=FollowDict[link]
delChar.append（nChar）
#print"delChar",delChar
#print"hasFollowChar",hasFollowChar
#print"notFollowChar",notFollowChar
forcharindelChar:
hasFollowChar.append（char）
notFollowChar.remove（char）
lock+=1
iflock==100:
print"Warning!
Thelooplockiswalking.."
fornCharinVn:
FollowDict[nChar]=list（set（FollowDict[nChar]））
returnFollowDict
defAnalyseTable（self,Grammer,firstSet,followSet）:
"""建立文法的分析表
"""
Table={}
tChars=self.tChars
nChars=self.nChars
forn_charinnChars:
Table[n_char]={}
fort_charintChars:
Table[n_char][t_char]="ERROR"
subRules=[]
forruleinGrammer:
left_char=rule.split（":
:
="）[0]
rightExpressions=rule.split（":
:
="）[1]
subRules+=[left_char+":
:
="+right_expressionforright_expressioninrightExpressions.split（"|"）]
forsub_ruleinsubRules:
left_char,meetChars=self.__ExpressionAnalyse（sub_rule,firstSet,followSet）
formeet_charinmeetChars:
Table[left_char][meet_char]=sub_rule
returnTable
def__NoLeftRecursion（self,Grammers）:
"""消除文法规则的左递归
"""
RightFirstIndex=4
noLeftRecursionGrammers=[]
forruleinGrammers:
#printrule
index=rule.find（':
:
='）#左边终结符号的终止位置
leftSymbol=rule[:
index]#获取左边的非终结符
rightFirstSymbol=rule[RightFirstIndex]#获取右边的第一个符号
ifrightFirstSymbol==leftSymbol:
#如果左边的非终结符与右边第一个符号相等，则进行消除左递归
resultOne=[symbolforsymbolinrule[RightFirstIndex:
].split（'|'）ifleftSymbolnotinsymbol]#单独取出含左非终结符的子表达式
resultTwo=[symbolforsymbolinrule[RightFirstIndex:
].split（'|'）ifleftSymbolinsymbol]#单独取出不含左非终结符的子表达式
#printresultTwo
newLeftSymbol=leftSymbol+"'"#引入一个新终结符
resultOne=[symbol+newLeftSymbolforsymbolinresultOne]
rightExpressionOne="|".join（resultOne）
expressionOne=rule[0:
RightFirstIndex]+rightExpressionOne
#printexpressionOne
resultTwo=[symbol.replace（leftSymbol,""）+newLeftSymbolforsymbolinresultTwo]
resultTwo.append（'~'）
rightExpressionTwo="|".join（resultTwo）
expressionTwo=newLeftSymbol+rule[1:
RightFirstIndex]+rightExpressionTwo
#printexpressionTwo
noLeftRecursionGrammers+=[expressionOne,expressionTwo]#返回经过改写法消除直接左递归后的文法规则
#printrule
else:
noLeftRecursionGrammers+=[rule]#如果不含直接左递归，则直接返回
returnnoLeftRecursionGrammers
def__GetVt（self,Grammer）:
"""获取文法中的终结符号
"""
Vt=[]
speSymbol=":
:
="
Vn=self.__GetVn（self.noLeftRecursionGrammers）
Vn.append（speSymbol）
Vn.append（"'"）
Vn.append（"|"）
forgrammerinGrammer:
forsymbolinVn:
grammer=grammer.replace（symbol,''）
forcharingrammer:
ifcharnotinVt:
Vt.append（char）
#forcharinVt:
#printchar
returnVt
def__GetVn（self,Grammer）:
"""获取文法中的非终结符号
"""
Vn=[]
forgrammerinGrammer:
index=grammer.find（':
:
='）#左边终结符号的终止位置
char=grammer[:
index]
ifcharnotinVn:
Vn.append（char）
returnVn
def__SubExpressions（self,Grammer）:
"""获取文法的子规则集
形如{左边非终结符:
[对应的右边的所有文法子规则]}
"""
speSymbol=":
:
="
_Grammer={}
forgrammerinGrammer:
_grammer=grammer.split（speSymbol）
_Grammer[_grammer[0]]=_grammer[1]
#新建一个字典subExpressions形如{非终结符:
[所有文法子规则]}
subExpressions={}
fornChar,rightExpressionin_Grammer.items（）:
subExpressions[nChar]=[subExpressionforsubExpressioninrightExpression.split（"|"）]
#printsubExpressions
returnsubExpressions
def__Split（self,Expression）:
"""将一个文法规则按单个字符切分
"""
char_list=[]
length=len（Expression）
for_inxrange（length）:
char=Ex
升级会员 