LL1语法分析器_B12040921

1、实 验 报 告（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 所定义的符号串进行识别。 二、 实验环境

2、(实验设备)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.Gra

3、mmers = 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 = sel

4、f.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%-12

5、s%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.fi

6、nd(:=) + 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 不是文法定义

7、的句子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= 0:char

8、 = 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 =

9、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(hasFo

10、llowChar):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! T

11、he 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 = ERRORsubRules =

12、 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 meetCha

13、rs: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 rightFi

14、rstSymbol = 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 = lef

15、tSymbol+ #引入一个新终结符resultOne = symbol + newLeftSymbol for symbol in resultOnerightExpressionOne = |.join(resultOne)expressionOne = rule0:RightFirstIndex+rightExpressionOne# print expressionOneresultTwo = symbol.replace(leftSymbol, )+newLeftSymbol for symbol in resultTworesultTwo.append()rightExpressi

16、onTwo = |.join(resultTwo)expressionTwo = newLeftSymbol+rule1:RightFirstIndex+rightExpressionTwo# print expressionTwonoLeftRecursionGrammers += expressionOne,expressionTwo #返回经过改写法消除直接左递归后的文法规则# print ruleelse:noLeftRecursionGrammers += rule #如果不含直接左递归，则直接返回return noLeftRecursionGrammersdef _GetVt(se

17、lf, 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

18、_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(

19、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):将一个文法规则

20、按单个字符切分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,

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