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.G

3、rammers = 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 = s

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

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

6、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 不是文法

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:ch

8、ar = 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(has

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

11、 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 = 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 meetC

13、hars: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 right

14、FirstSymbol = 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 = l

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

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

17、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 Vtde

18、f _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.spli

19、t(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_cha

21、r, 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:=B