LL1语法分析器_B12040921.docx

《LL1语法分析器_B12040921.docx》由会员分享，可在线阅读，更多相关《LL1语法分析器_B12040921.docx（16页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、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成 绩批阅人日期-实 验 报 告实验名称语法分析器的构造指导教师蒋凌云实验类型

2、上机实验学时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:Imp

3、ortcjj#由于仓促，代码有很多地方不是科学，但是基本功能已经实现#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.noLeft

4、RecursionGrammers)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

5、(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

6、 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()S

7、tringStack.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

8、.tCharsFirst = self._SubExpressions(Grammers)#新建一个以所有非终结符作为键，以空列表作为值的字典FirstDict = for nChar in Vn:FirstDictnChar = lock = 1while First and lock= 0:char = expressionindexif char = nChar:breakelif char in Vt:breakelif char not in nilChar:followLink2char.append(nChar)# print 1 add %s to follow %s%(nCh

9、ar, 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 notFoll

10、owCharlock = 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, hasFollo

11、wChar# 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, follow

12、Set):建立文法的分析表Table = tChars = self.tCharsnChars = self.nCharsfor n_char in nChars:Tablen_char = for t_char in tChars:Tablen_chart_char = ERRORsubRules = for rule in Grammer:left_char = rule.split(:=)0rightExpressions = rule.split(:=)1subRules += left_char +:=+right_expression for right_expression in

13、 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

14、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 #单独取

15、出含左非终结符的子表达式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:RightFirstIn

16、dex+rightExpressionOne# print expressionOneresultTwo = symbol.replace(leftSymbol, )+newLeftSymbol for symbol in resultTworesultTwo.append()rightExpressionTwo = |.join(resultTwo)expressionTwo = newLeftSymbol+rule1:RightFirstIndex+rightExpressionTwo# print expressionTwonoLeftRecursionGrammers += expre

17、ssionOne,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 Gr

18、ammer: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(ch

19、ar)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():subExpre

20、ssionsnChar = 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)ret

21、urn 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 t

22、Chars: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|cgrammer_list = E:=E+T|T, T:=T*F|F, F:=(E)|i

23、# grammer_list = S:=iCtSS|a, S:=eS|, C:=bll1am = AnalyseMachine()ll1am.load(grammer_list)print u消除文法左递归print ll1am.noLeftRecursionGrammersprint u非终极符print ll1am.nCharsprint u终结符print ll1am.tCharsprint uFirst集pprint.pprint(ll1am.firstSet)print uFollow集pprint.pprint(ll1am.followSet)print uLL(1)分析表ppri

24、nt.pprint(ll1am.analyseTable)string1 = i+i*ill1am.Judge(string1)string2 = i*(i+i)ll1am.Judge(string2)string3 = i+i(i*i)ill1am.Judge(string3)实验结果：四、实验小结 通过本次实验基本掌握了语法分析的原理和LL（1）语法分析方法，以及预测分析表的构造，了解了语法分析的过程。由于开始的时候不了解具体求法，感觉有点麻烦。但在仔细翻阅书本了解到了具体的分析方法后，就感觉手到擒来了。但是编写仓促，该程序虽然可以随意输入文法规则来分析，但是可能在一些小问题上还有待改进。如果有时间的话，还会好好改进一下的。