编译原理实验LL(1)文法的判断及转换

PAGE\*MERGEFORMAT12016.11.30LL(1)文法的判断及转换目录TOC\o"1-3"\h\z\uHYPERLINK\l"_Toc469177013"一、实验名称PAGEREF_Toc469177013\h2HYPERLINK\l"_Toc469177014"二、实验目的PAGEREF_Toc469177014\h2HYPERLINK\l"_Toc469177015"三、实验原理PAGEREF_Toc469177015\h2HYPERLINK\l"_Toc469177016"1、First集定义PAGEREF_Toc469177016\h2HYPERLINK\l"_Toc469177017"2、Follow集定义PAGEREF_Toc469177017\h2HYPERLINK\l"_Toc469177018"3、Select集定义PAGEREF_Toc469177018\h3HYPERLINK\l"_Toc469177019"4、含左递归文法PAGEREF_Toc469177019\h3HYPERLINK\l"_Toc469177020"四、实验思路PAGEREF_Toc469177020\h3HYPERLINK\l"_Toc469177021"1、求非终结符是否能导出空PAGEREF_Toc469177021\h3HYPERLINK\l"_Toc469177022"2、求First集算法PAGEREF_Toc469177022\h3HYPERLINK\l"_Toc469177023"3、求Follow集算法PAGEREF_Toc469177023\h3HYPERLINK\l"_Toc469177024"4、求Select集算法PAGEREF_Toc469177024\h4HYPERLINK\l"_Toc469177025"五、实验小结PAGEREF_Toc469177025\h4HYPERLINK\l"_Toc469177026"六、附件PAGEREF_Toc469177026\h4HYPERLINK\l"_Toc469177027"1、源代码PAGEREF_Toc469177027\h4HYPERLINK\l"_Toc469177028"2、运行结果截图PAGEREF_Toc469177028\h10一、实验名称LL(1)文法的判断及转换二、实验目的输入：任意一个文法输出：(1)是否为LL(1)文法(2)若是，给出每条产生式的select集(3)若不是，看看是否含有左公共因子或者含有左递归，并用相应的方法将非LL(1)文法变成LL(1)文法，并输出新文法中每条产生式的select集。三、实验原理1、First集定义令X为一个文法符号（终止符或非终止符）或ε，则集合First（X）有终止符组成，此外可能还有ε，它的定义如下：1. 若X是终止符或ε，则First（X）= {X}。2. 若X是非终结符，则对于每个产生式X—>X1X2…Xn，First（X）包含了First（X1）-{ε}。若对于某个i < n，所有的集合First（X1），... ，First（Xi）都包含了ε，则First（X）也包 括了First（Xi+1）- {ε}。若所有集合First（X1），...，First（Xn）都包括了ε，则First（X）也包括了ε。2、Follow集定义给出一个非终结符A，那么集合Follow（A）则是由终结符组成，此外可能还含有#（#是题目约定的字符串结束符）。集合Follow（A）的定义如下：1.若A是开始符号，则#在Follow（A）中。2.若存在产生式B—>αAγ，则First（γ）-{ε}在Follow（A）中。3.若存在产生式B—>αAγ，且ε在First（γ）中，则Follow（A）包括Follow（B）。3、Select集定义对于产生式A—>α。集合select（A—>α）定义如下：1.若α不能推出ε，则select（A—>α）=first（α）。2.若α能推出ε，则select（A—>α）=first（α）∪follow(A)。4、含左递归文法一个文法G，若存在P经过一次或多次推导得到Pa（即能推导出以P开头的式子），则称G是左递归的。　　左递归分为直接左递归和间接左递归。　　直接左递归经过一次推导就可以看出文法存在左递归，如P→Pa｜b。　　间接左递归侧需多次推导才可以看出文法存在左递归，如文法：S→Qc｜c，Q→Rb｜b，R→Sa｜a有S=>Qc=>Rbc=>Sabc四、实验思路本次实验采用python完成。1、求非终结符是否能导出空a.第一轮扫描。当前的产生式还没被删除，非终结符lp可以导出空，将以该非终结符为左部的产生式标记为要删除的。产生式右部分解，若该产生式右部包含终结符，删除该产生式因为由它不会导出空。判断没有被删除的产生式中是否还有以该非终结符为左部的产生式。b.第二轮扫描。逐一扫描每一条产生右部的每一个符号，循化直至每个非终结符的状态都确定下来。2、求First集算法存储每一个非终结符对应的First集，扫描每一条产生式， 记录 混凝土 养护记录下载土方回填监理旁站记录免费下载集备记录下载集备记录下载集备记录下载 每一轮扫描是每个非终结符First集是否增大过。全部初始化为没有增大的状态，对于课本的五种类型依次求解，每次将结果加入对应的集合中，若一次扫描First集没有增大，则说明循环结束。3、求Follow集算法存储每一个非终结符对应的Follow集，将'#'加入文法的开始符号的Follow集合中，记录每一轮扫描是每个非终结符Follow集合是否增大过，全部初始化为没有增大的状态，扫描每一条产生式的右部，扫描到非终结符,判断在该非终结符之后的子串能否推导空，若该符号串可以推导出空,还要将Follow(lp)加入到里面。4、求Select集算法初始化每条产生式对应的Select集合为空，若产生式右部不能推导出空，则将右部的First集加入Select集，如果可以推出空，则需要同时将左部的Follow集合右部的First集去掉空的部分加入Select集。五、实验小结通过本次实验，知道了如何判断一个文法是不是LL（1）文法，同时对于First、Follow以及Select集的求解原理变得更加熟悉，并且知道了如何用计算机语言求解First，Follow以及Select集。不足之处是，没有完成判断文法是否为左递归文法以及左递归文法的转换部分。六、附件1、源代码classGw:def__init__(self):withopen('Gw.txt')asf:content=f.readlines()content=[line.strip()forlineincontent]self.Vn=content[0].split('')self.Vt=content[1].split('')self.start=content[2]self.produce=[]self.left=[]self.right=[]foriinrange(3,len(content)):self.produce.append(content[i])self.left.append(content[i].split('->')[0])self.right.append(content[i].split('->')[1])defshowGw(self):print('非终结符:',self.Vn)print('终结符:',self.Vt)print('开始符号:',self.start)print('产生式如下:')forl,rinzip(self.left,self.right):print(l+'->'+r)defcanEmpty(self):self.isEmpty=dict()foriinrange(len(self.Vn)):self.isEmpty[self.Vn[i]]=-1print(self.isEmpty)temp=self.produce[::]deleteIndex=[]pointer=0whilepointer')[0]rp=temp[pointer].split('->')[1]ifrp=='!':self.isEmpty[lp]=1foriinrange(len(temp)):iftemp[i].split('->')[0]==lpandinotindeleteIndex:deleteIndex.append(i)l=list(rp)isContainVt=[iinself.Vtforiinl]ifTrueinisContainVt:deleteIndex.append(pointer)forkinrange(len(temp)):ifknotindeleteIndex:iftemp[k].split('->')[0]==lp:breakelse:self.isEmpty[lp]=0pointer=pointer+1while-1inself.isEmpty.values():foriinrange(len(temp)):ifinotindeleteIndex:lp=temp[i].split('->')[0]rp=temp[i].split('->')[1]rlsit=list(rp)forjinrange(len(rlsit)):ifself.isEmpty[rlsit[j]]==1:ifj==len(rlsit)-1:self.isEmpty[lp]=1elifself.isEmpty[rlsit[j]]==0:deleteIndex.append(i)forkinrange(len(temp)):ifknotindeleteIndex:iftemp[k].split('->')[0]==lp:breakelse:self.isEmpty[lp]=0else:continuedefshow(self):print('非终结符能否推导出空的信息:')forvinself.Vn:ifself.isEmpty[v]==1:yon='是'else:yon='否'print('%s:%s'%(v,yon))defgetFirst(self):self.First=dict()foriinself.Vn:self.First[i]=list()isChange=dict()whileTrue:forkinself.Vn:isChange[k]=0foriinrange(len(self.produce)):lp=self.produce[i].split('->')[0]rp=self.produce[i].split('->')[1]rlist=list(rp)ifrlist[0]=='!'orrlist[0]inself.Vt:ifrlist[0]notinself.First[lp]:self.First[lp].append(rlist[0])isChange[lp]=1else:forjinrlist:ifjinself.Vn:ifself.isEmpty[j]==1:oldsize=len(self.First[lp])templist=self.First[j][::]if'!'intemplist:templist.remove('!')forxintemplist:ifxnotinself.First[lp]:self.First[lp].append(x)ifrp.endswith(j)and'!'notinself.First[lp]:self.First[lp].append('!')newsize=len(self.First[lp])ifoldsize!=newsize:isChange[lp]=1else:oldsize=len(self.First[lp])ifjinself.Vn:templist=self.First[j][::]forxintemplist:ifxnotinself.First[lp]:self.First[lp].append(x)else:ifjnotinself.First[lp]:self.First[lp].append(x)newsize=len(self.First[lp])ifoldsize!=newsize:isChange[lp]=1breakif1notinisChange.values():print('First集合不在增大!')breakelse:print('First集合有增大!')passdefshowFirst(self):print('First集合信息:')forvinself.Vn:print(v,self.First[v])defcanCauseEmpty(self,plist):first=list()iflen(plist)==0:first.append('!')else:foriinplist:ifiinself.Vn:ifself.isEmpty[i]==1:t=self.First[i][::]if'!'int:t.remove('!')forkint:ifknotinfirst:first.append(k)if''.join(plist).endswith(i)and'!'notinfirst:first.append('!')else:forkinself.First[i]:ifknotinfirst:first.append(k)breakelse:ifinotinfirst:first.append(i)breakreturnfirstdefgetFollow(self):self.Follow=dict()foriinself.Vn:self.Follow[i]=list()self.Follow[self.start].append('#')isChange=dict()whileTrue:forkinself.Vn:isChange[k]=0foriinrange(len(self.produce)):lp=self.produce[i].split('->')[0]rp=self.produce[i].split('->')[1]rlist=list(rp)forjinrange(len(rlist)):ifrlist[j]inself.Vn:reslist=self.canCauseEmpty(rlist[j+1::])if'!'inreslist:oldsize=len(self.Follow[rlist[j]])foryinself.Follow[lp]:ifynotinself.Follow[rlist[j]]:self.Follow[rlist[j]].append(y)newsize=len(self.Follow[rlist[j]])ifoldsize!=newsize:isChange[rlist[j]]=1else:passoldsize=len(self.Follow[rlist[j]])forxinreslist:ifx!='!'andxnotinself.Follow[rlist[j]]:self.Follow[rlist[j]].append(x)newsize=len(self.Follow[rlist[j]])ifoldsize!=newsize:isChange[rlist[j]]=1if1notinisChange.values():breakdefshowFollow(self):print('Follow集合信息:')forkeyinself.Vn:print(key,self.Follow[key])defgetSelect(self):self.Select=dict()foriinself.produce:self.Select[i]=list()foriinrange(len(self.produce)):lp=self.produce[i].split('->')[0]rp=self.produce[i].split('->')[1]rlist=list(rp)ifrlist[0]=='!':forvinself.Follow[lp]:ifvnotinself.Select[self.produce[i]]:self.Select[self.produce[i]].append(v)elifrlist[0]inself.Vt:self.Select[self.produce[i]].append(rlist[0])else:res=self.canCauseEmpty(rlist)if'!'notinres:forvinres:ifvnotinself.Select[self.produce[i]]:self.Select[self.produce[i]].append(v)else:forvinres:ifvnotinself.Select[self.produce[i]]andv!='!':self.Select[self.produce[i]].append(v)forvinself.Follow[lp]:ifvnotinself.Select[self.produce[i]]:self.Select[self.produce[i]].append(v)defshowSelect(self):print('Select集合信息:')forkeyinself.produce:print(key,self.Select[key])defisLLone(self):isright=[]forkinself.Vn:tset=set()tset.add('#')tset=tset|set(self.Vt)forl,rinzip(self.left,self.right):ifk==l:p=l+'->'+rtset=tset&set(self.Select[p])iflen(tset)==0:isright.append(1)else:isright.append(0)if0inisright:print('不是LL(1)文法!')self.isll1=Falseelse:print('是LL(1)文法!')self.isll1=Trueprint(isright)if__name__=='__main__':w=Gw()w.showGw()w.canEmpty()w.show()w.getFirst()w.showFirst()w.getFollow()#res=w.canCauseEmpty(['A','D'])#print('res=',res)w.showFollow()w.getSelect()w.showSelect()w.isLLone()2、运行结果截图