LL1语法分析器_B12040921.docx

Four short words sum up what has lifted most successful individuals above the crowd: a little bit more.-author-dateLL1语法分析器_B12040921LL1语法分析器_B12040921实 验 报 告（2014/2015学年 第二学期）课程名称编译原理实验名称语法分析器的构造实验时间2015年5月29日指导单位计算机学院软件工程系指导教师蒋凌云学生姓名Cjj班级学号B-学院(系)计算机学院专 业NIIT成 绩批阅人日期-实 验 报 告实验名称语法分析器的构造指导教师蒋凌云实验类型上机实验学时4实验时间2015-5-14一、 实验目的和要求设计、编制、调试一个LL(1)语法分析程序，利用语法分析器对符号串进行识别，加深对语法分析原理的理解。要求设计并实现一个LL(1)语法分析器，实现对算数文法E->E+T|T T->T*F|F F->(E)|i 所定义的符号串进行识别。 二、 实验环境(实验设备)Mac OS X + Python三、 实验原理及内容AnalyseMachine:Load( )方法 载入文法规则，自动求出First集，Follow集，分析表Judge( )方法 判断某一字符串是否为当前文法的句子程序代码#coding:utf-8#LL(1)分析法#By:Importcjj#由于仓促，代码有很多地方不是科学，但是基本功能已经实现#2015-6-15class AnalyseMachine(object):def _init_(self):passdef load(self, Grammers):"""载入文法规则参数Grammers: 文法的规则列表"""self.Grammers = Grammersself.noLeftRecursionGrammers = self._NoLeftRecursion(self.Grammers)self.start = self.Grammers00self.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)def Judge(self, string):"""判断字符串是否为当前文法的句子"""isMatch = FalseanalyseStack = "#", self.startStringStack = list(string) + "#"print u"="*25,u"判断字符串=%s"%string,u"="*25print "%-30s%-12s%s"%(u"分析栈",u"余留输入串",u"所用生成式")try:while analyseStack:xm = analyseStack-1ai = StringStack0print "%-20s%20s%10s"%("".join(analyseStack),"".join(StringStack), ""),if xm in self.nChars:analyseStack.pop()expression = self.analyseTablexmaiif expression = "ERROR":printraise ValueErrorprint expression,index = expression.find(":=") + 3if self._Split(expressionindex:):-1 != "":analyseStack += self._Split(expressionindex:):-1 #逆序加入elif xm = ai and xm != "#":analyseStack.pop()StringStack.pop(0)elif xm = ai and xm = "#":analyseStack.pop()isMatch = Trueprintexcept Exception as e:passresult = u"%s 为文法定义的句子" if isMatch else u"%s 不是文法定义的句子"print result%stringprint u"="*25,u"判断字符串=%s"%string,"="*25return isMatchdef FirstSet(self, Grammers):"""构造文法的First集"""speSymbol = ":="Vn = self.nCharsVt = self.tCharsFirst = self._SubExpressions(Grammers)#新建一个以所有非终结符作为键，以空列表作为值的字典FirstDict = for nChar in Vn:FirstDictnChar = lock = 1while First and lock<100:for nChar in Vn:if First.has_key(nChar): #如果nChar的First还没求完毕first = FirstnCharfor chars in first:char = chars0if char in Vt: #如果子规则的第一个符号是终结符，直接加入First集FirstDictnChar.append(char)FirstnChar.remove(chars)else: #is in Vnif char not in First: #char是非终结符而且他的First集已经求解完毕FirstDictnChar += FirstDictchar#把该非终结符的First集（除”“外加入nChar的First集中）FirstnChar.remove(chars)if "" in FirstDictchar:FirstDictnChar.remove("")FirstnChar.append(chars1:)#如果该终结符的First中含有”“，那么他的下一个符号的First集也需要被继续计算else:passif not FirstnChar:#如果子规则全部检查计算完毕，那么删去First中以nChar作为键的键值对First.pop(nChar)lock+=1if lock =100:print "Warning !the loop lock is working."return FirstDictdef FollowSet(self, Grammers):"""构造文法的Follow集"""Vn = self.nCharsVt = self.tCharsFollow = self._SubExpressions(Grammers)#新建一个以所有非终结符作为键，以空列表作为值的字典FollowDict = for nChar in Vn:FollowDictnChar = #rule1-”#加入文法的开始符号的Follow集“FollowDictVn0.append("#")#rule2-firstSet = self.firstSetfollowLink = for nChar in Vn:followLinknChar = for nChar, expression in Follow.items():for subExpression in expression:subExpression = self._Split(subExpression)for char in subExpression:-1:if char in Vn:index = subExpression.index(char)+1string = subExpressionindex:followLinkchar.append(''.join(string)# print followLinkfor nChar, stringList in followLink.items():for string in stringList:string = self._Split(string)for char in string:# print "string ",stringif char in Vt:FollowDictnChar.append(char)breakelse:firstSetOfChar = firstSetchar# print "nchar=%s char=%s firstSetOfChar=%s"%(nChar, char, firstSetOfChar)FollowDictnChar += firstSetOfCharif "" in firstSetOfChar:FollowDictnChar.remove("")else:break#rule3-#先求出能推倒出”“的非终结符nilChar = for nChar, subExpressions in Follow.items():if "" in subExpressions:nilChar.append(nChar)nilChar.append('')followLink2 = for nChar in Vn:followLink2nChar = for nChar, subExpressions in Follow.items():# print "ncahr=%s, subExpressions="%nChar,subExpressionsfor expression in subExpressions:expression = self._Split(expression)index = len(expression) -1while index >= 0:char = expressionindexif char = nChar:breakelif char in Vt:breakelif char not in nilChar:followLink2char.append(nChar)# print "1 add %s to follow %s"%(nChar, char)breakelse:followLink2char.append(nChar)# print "2 add %s to follow %s"%(nChar, char)index -= 1# print followLink2hasFollowChar = notFollowChar = for nChar, links in followLink2.items():if not links:hasFollowChar.append(nChar)else:notFollowChar.append(nChar)# print hasFollowChar# print notFollowCharlock = 1while notFollowChar and lock <100:delChar = for nChar in notFollowChar:# print "nChar is %s"%nCharif set(followLink2nChar).issubset(set(hasFollowChar):for link in followLink2nChar:FollowDictnChar += FollowDictlinkdelChar.append(nChar)# print "delChar", delChar# print "hasFollowChar", hasFollowChar# print "notFollowChar", notFollowCharfor char in delChar:hasFollowChar.append(char)notFollowChar.remove(char)lock += 1if lock = 100:print "Warning! The loop lock is walking."for nChar in Vn:FollowDictnChar = list(set(FollowDictnChar)return FollowDictdef AnalyseTable(self, Grammer, firstSet, followSet):"""建立文法的分析表"""Table = tChars = self.tCharsnChars = self.nCharsfor n_char in nChars:Tablen_char = for t_char in tChars:Tablen_chart_char = "ERROR"subRules = for rule in Grammer:left_char = rule.split(":=")0rightExpressions = rule.split(":=")1subRules += left_char +":="+right_expression for right_expression in rightExpressions.split("|")for sub_rule in subRules:left_char, meetChars = self._ExpressionAnalyse(sub_rule, firstSet, followSet)for meet_char in meetChars:Tableleft_charmeet_char=sub_rulereturn Tabledef _NoLeftRecursion(self, Grammers):"""消除文法规则的左递归"""RightFirstIndex = 4noLeftRecursionGrammers = for rule in Grammers:# print ruleindex = rule.find(':=') #左边终结符号的终止位置leftSymbol = rule:index #获取左边的非终结符rightFirstSymbol = ruleRightFirstIndex #获取右边的第一个符号if rightFirstSymbol = leftSymbol: #如果左边的非终结符与右边第一个符号相等，则进行消除左递归resultOne = symbol for symbol in ruleRightFirstIndex:.split('|') if leftSymbol not in symbol #单独取出含左非终结符的子表达式resultTwo = symbol for symbol in ruleRightFirstIndex:.split('|') if leftSymbol in symbol #单独取出不含左非终结符的子表达式# print resultTwonewLeftSymbol = leftSymbol+"'" #引入一个新终结符resultOne = symbol + newLeftSymbol for symbol in resultOnerightExpressionOne = "|".join(resultOne)expressionOne = rule0:RightFirstIndex+rightExpressionOne# print expressionOneresultTwo = symbol.replace(leftSymbol, "")+newLeftSymbol for symbol in resultTworesultTwo.append('')rightExpressionTwo = "|".join(resultTwo)expressionTwo = newLeftSymbol+rule1:RightFirstIndex+rightExpressionTwo# print expressionTwonoLeftRecursionGrammers += expressionOne,expressionTwo #返回经过改写法消除直接左递归后的文法规则# print ruleelse:noLeftRecursionGrammers += rule #如果不含直接左递归，则直接返回return noLeftRecursionGrammersdef _GetVt(self, Grammer):"""获取文法中的终结符号"""Vt = speSymbol = ":="Vn = self._GetVn(self.noLeftRecursionGrammers)Vn.append(speSymbol)Vn.append("'")Vn.append("|")for grammer in Grammer:for symbol in Vn:grammer = grammer.replace(symbol,'')for char in grammer:if char not in Vt:Vt.append(char)# for char in Vt:# print charreturn Vtdef _GetVn(self, Grammer):"""获取文法中的非终结符号"""Vn = for grammer in Grammer:index = grammer.find(':=') #左边终结符号的终止位置char = grammer:indexif char not in Vn:Vn.append(char)return Vndef _SubExpressions(self, Grammer):"""获取文法的子规则集形如左边非终结符: 对应的右边的所有文法子规则"""speSymbol = ":="_Grammer = for grammer in Grammer:_grammer = grammer.split(speSymbol)_Grammer_grammer0 = _grammer1#新建一个字典subExpressions 形如非终结符: 所有文法子规则subExpressions = for nChar, rightExpression in _Grammer.items():subExpressionsnChar = subExpression for subExpression in rightExpression.split("|")# print subExpressionsreturn subExpressionsdef _Split(self, Expression):"""将一个文法规则按单个字符切分"""char_list = length = len(Expression)for _ in xrange(length):char = Expression_if char = "'":char_list_ - 1 += charelse:char_list.append(char)return char_listdef _ExpressionAnalyse(self, expression, firstSet, followSet):"""建立分析表时，判断某个表达式应该填入分析表的哪一个位置"""tChars = self.tCharsnChars = self.nCharsleft_char, rightChars = expression.split(":=")meetChars = for right_char in rightChars:if right_char = "":meetChars += followSetleft_charbreakelif right_char in tChars:meetChars.append(right_char)breakelse:meetChars += firstSetright_charif "" not in firstSetright_char:breakelse:meetChars.remove("")return left_char, meetCharsif _name_ = "_main_":import pprint# grammer_list = 'A:=BCc|gDB', 'B:=|bCDE', 'C:=DaB|ca', 'D:=|dD', 'E:=gAf|c'grammer_list = 'E:=E+T|T', 'T:=T*F|F', 'F:=(E)|i'# grammer_list = "S:=iCtSS'|a", "S':=eS|", "C:=b"ll1am = AnalyseMachine()ll1am.load(grammer_list)print u"消除文法左递归"print ll1am.noLeftRecursionGrammersprint u"非终极符"print ll1am.nCharsprint u"终结符"print ll1am.tCharsprint u"First集"pprint.pprint(ll1am.firstSet)print u"Follow集"pprint.pprint(ll1am.followSet)print u"LL(1)分析表"pprint.pprint(ll1am.analyseTable)string1 = "i+i*i"ll1am.Judge(string1)string2 = "i*(i+i)"ll1am.Judge(string2)string3 = "i+i(i*i)i"ll1am.Judge(string3)实验结果：四、实验小结 通过本次实验基本掌握了语法分析的原理和LL（1）语法分析方法，以及预测分析表的构造，了解了语法分析的过程。由于开始的时候不了解具体求法，感觉有点麻烦。但在仔细翻阅书本了解到了具体的分析方法后，就感觉手到擒来了。但是编写仓促，该程序虽然可以随意输入文法规则来分析，但是可能在一些小问题上还有待改进。如果有时间的话，还会好好改进一下的。