LL文法判定.doc

编译原理课程设计LL(1)文法判定专业班号_软件0303_学生姓名_尹_君_指导教师_王_红_联系电话4128邮箱地址：2005年 12 月 29 日目 录目 录2第一章 前 言31.1 原理简单概述31.2 文档概述3第二章 语言文法规则32.1 语言的词法规则32.2 语言的语法规则32.3 代码生成规则3第三章 程序设计43.1 词法分析程序的实现43.2 语法分析程序的实现43.2.1 能推出$的非终结符43.2.2 FIRST集的确定43.2.3 FOLLOW集的确定63.2.4 SELLECT集的确定63.2.5 LL(1)文法的判定73.3 句子的判定73.4其它说明7第四章 系统运行及测试84.1 运行和安装环境84.2 系统运行84.2 系统测试104.2.1 测试一104.2.2 测试二11第五章 结 论125.1 系统结论125.2 存在的不足12参考文献12附 录 112测试1 完整结果截图12测试2完整结果截图：14附 录 215源程序15第一章 前 言1.1 原理简单概述LL(1)文法使用的是确定的自顶向下的分析技术。LL(1)的含义是：第一个L表明自顶向下分析是从左向右扫描输入串，第2个L表明分析过程中将使用最左推导，1表明只需向右看一个符号便可决定如何推导，即选择哪个产生式(规则)进行推导。LL(1)文法的判别需要依次计算FIRST集、FOLLOW集和SELLECT集,然后判断是否为LL(1)文法,最后再进行句子分析。1.2 文档概述此文档主要介绍FIRST集、FOLLOW集和SELLECT集的计算以及句子分析的算法。第二章 语言文法规则2.1 语言的词法规则在本示例程序中，单个字符（字母、数字、符号甚至是汉字）可以规定为终结符或非终结符，但是$和#符号作为空串处理不可以作为终结符或非终结符去处理。2.2 语言的语法规则（1）产生式的右部不全是有终结符组成（2）如果两个产生式有相同的左部，他们的右部是由不同的终结符或非终结符开始2.3 代码生成规则略第三章 程序设计3.1 词法分析程序的实现由于本程序简单，所以依次扫描遇到的每一个字符即可确定哪些是终结符哪些是非终结符。3.2 语法分析程序的实现3.2.1 能推出$的非终结符首先进行第一次扫描，把能够直接推出$的非终结符号记录到空串表，把不能直接推出$的符号依次记录下来，然后单个扫描每一个不能直接推出$的符号。扫描这个符号能够直接推出的第一个非终结符记录到一个队列，接下来依次检查队列中每一个元素，把二次能够推出$的符号记录到空串表，把二次也推不出空串的继续送入到队列，然后再从队列取元素扫描，直到队列为空没能找到能够星推导出$的终结符，那么可以确定这个非终结符推导不出$。接下去扫描下一个非终结符。3.2.2 FIRST集的确定FIRST集使用以下四个步骤判定：(1)若XVTT,则FIRST(X)=X(2)若XVN,且有产生式Xa，aVT 则把a加入到FIRST(X)中，即aFIRST(X)(3)若XVN,且有产生式X$， 则把$也加到FIRST(X)中，即$FIRST(X)(4)若XVN, Y1，Y2，Yi 都VN，且有产生式XY1Y2Yn。 当Y1，.Yi-1=$ (1in)，则FIRST(Y1)-$，FIRST(Yi-1)- $，FIRST(Yi)都包含在FIRST(X)中，即： FIRST(Yi-1)-$ FIRST(X) 所有Y1,Yn *= $ ，则把$加到FIRST(X)中,即： FIRST(Yi) FIRST(X)其中第13个方法都很好处理，关键是第四个方法判断时首先判断第一个字符为非终结符，设定一个布尔型扫描标志FLAG，赋初值TRUE，接下去依次扫描产生式右部每一个字符Yi，假如第i个字符可以推出空，那么就把这个字符的FIRST集去除$加入到产生式左部字符的FIRST集中，即FIRST(Yi)-$FIRST(X),假如Yi是终结符或者不可以推出$，那么就把这个字符的FIRST集直接加入到FIRST(X)中，即FIRST(Yi)FIRST(X)同时置FLAG为FALSE不再向下扫描，假如Yi恰好是最后一个字符，那么不管它能不能星推导出空都直接把它的FIRST集加入到FIRST(X)中。同时要设置一个队列和一组布尔型变量记录FIRST集是否完成，队列用来记录FIRST(X)用到了哪些其它非终结符的FIRST集。第一遍扫描完成后就扫描队列，把FIRST集完成的非终结符的FIRST集加入到那些没有完成的非终结符的FIRST集中去，没有完成的非终结符再送回到队列，这时候可能出现死循环，比如FIRST(S)用到了FIRST(A),而FIRST(A)用到了FIRST(B)，FIRST(B)又用到了FIRST(S),这时候S,A,B的FIRST标志均为FALSE，无限循环下去。这时候可以记录一下，比如循环了100次，强行设置FIRST(S)的标志为TRUE，那么FIRST(A),FIRST(B)也就依次可以求出了。我们在实际计算时也是这样处理的。只是没有把标志写出来而是记录在心里的。对于100次循环或许有些多了，那么到极限情况，可能就是循环总共产生式的个数次数时如果再循环就可以确定是进入死循环了。3.2.3 FOLLOW集的确定FOLLOW集使用以下三个步骤判定：(1)如果 X 是开始符 那么把 # 加入到 FOLLOW(X)(2)若=B是一个产生式,则把FIRST()$加至FOLLOW(B)中(3)若=B是一个产生式，或=B是一个产生式而*=$(即$FIRST()），则把 FOLLOW(A)加至FOLLOW(B)中FOLLOW集的求法与FIRST集类似，但有不同的地方。FOLLOW集需要扫描每一个产生式。而FIRST集扫描的是产生式左部不同的产生式，然后扫描左部相同的产生式的每一个右部。FOLLOW集第一次扫描可以确定哪些FIRST集或FOLLOW集属于所求的FOLLOW集，由于FIRST集已经求出，所以第一次扫描就可以把相应的FIRST集加入到FOLLOW集中，设置FOLLOW集完成标记位，设置队列，把未完成的非终结符送入队列，依次取出队列元素，把求出FOLLOW集的非终结符的FOLLOW集加入到相应的FOLLOW集中，把未求出的送回队列。碰到死循环使用FIRST集一样的方法处理就可以。3.2.4 SELLECT集的确定FIRST集FOLLOW集都已经求出来后SELLECT集就很好求了，扫描每一个产生式，使用以下三个步骤确定：A AVN，V*，(1)若是终结符，那么SELLECT(A)=(2)若是$，则SELECT(A)=FOLLOW(A)(3)若是非终结符那么 若*=$，则SELECT(A)=(FIRST()-$)FOLLOW(A) 若*=$ 则SELECT(A)=FIRST()3.2.5 LL(1)文法的判定当SELLECT集求出来后就可以判断是不是一个文法是不是LL(1)文法了，扫描产生式左部相同的SELLCET集是否含有相同元素，一旦发现相同元素立刻返回FALSE，扫描结束没有发现相同元素则返回TRUE。3.3 句子的判定当一个文法确定是LL(1)文法时就可以对输入的语句进行判定了。首先要安装SELLECT集生成LL(1)预测分析表，最简单的方法是使用哈希表来表示，把每一个产生式左部依次和这个产生式SELLECT集中的每一个终结符组成关键字，其值即为这个产生式，送入哈希表。这样在进行句子的分析时就可以很容易判断是否使用某一个产生式来进行规约。在实际分析时设置两个栈，把#压入分析栈和剩余栈，把开始符压入分析栈，把输入串从右向左送入剩余栈，然后只要两个栈元素个数同时大于1，那么依次从两个栈中取出两个元素进行比较，假如一样就匹配，假如可以规约就规约，否则就不是该文法的句子。3.4其它说明本程序使用C#编写，有良好的用户界面，在程序当中，SymboleSet类表示终结符和非终结符集合，使用单例模式在整个运行当中只有一个实例，Product类是产生式类，一个对象记录一个左部，和多个右部产生式。因为程序中用到了栈，队列和ArrayList类(对象数组类，数组中每个元素都可以是一个object对象)，因此还编写了Tools类，来处理一些栈的顺序输出，栈的逆序输出，ArrayList的连接，输出等操作，其中的方法全部均为静态，Tools类的UML图如下其它主要算法均包含在frmMain.cs当中。第四章 系统运行及测试4.1 运行和安装环境2000或XP系统，安装.NetFrameWork 1.1 以上版本即可运行。需要调试程序请安装.NetFrameWork SDK 1.1 以上版本或直接安装 Visual Studio .Net 2003以上版本。4.2 系统运行运行界面如下：4.2 系统测试4.2.1 测试一产生式集： SABSbCA$AbB$BaDCADCbDaSDc 非终结符推出空$FIRST集FOLLOW集STRUE$ b a#ATRUEba c #BTRUEa#CTRUE$ b a c#DFALSEa c#产生式SELECT集SABb a #SbCbA$a c #AbbB$#BaDaCADb a cCbbDaSaDcc该文法不是LL(1)文法 测试字符串： abcdeda 预测分析表： 无 步骤 分析栈 剩余输入字符 使用产生式或匹配 无 结论：字符串abcdeda无法检测是不是该文法的句子 4.2.2 测试二产生式集：SaHHaMdHdMAbM$AaMAe非终结符推出空$FIRST集FOLLOW集SFALSEa#HFALSEa d#MTRUE$ a ed bAFALSEa eb产生式SELECT集SaHaHaMdaHddMAba eM$d bAaMaAee该文法是LL(1)文法测试字符串： aaabd预测分析表：adbe#SSaHHHaMdHdMMAbM$M$MAbAAaMAe步骤分析栈剩余输入字符使用产生式或匹配1#Saaabd#SaH2#Haaaabd#a匹配3#Haabd#HaMd4#dMaaabd#a匹配5#dMabd#MAb6#dbAabd#AaM7#dbMaabd#a匹配8#dbMbd#M$9#dbbd#b匹配10#dd#d匹配11#分析成功结论：字符串aaabd是该文法的句子第五章 结 论5.1 系统结论该示例程序能够很好地判断LL(1)文法5.2 存在的不足不能够处理左递归和左公因子。参考文献编译原理 张素琴 吕映之 蒋维杜 戴桂兰 著 清华大学出版社 2005年2月 第2版附 录 1测试1 完整结果截图测试2完整结果截图：附 录 2源程序frmMain.cs主要算法：#region 主要步骤#region 得到FIRST集/ / 得到FIRST集/ / ArrayListpublic ArrayList FirstSet()ArrayList lstFirst = new ArrayListLeftItem.Count;ArrayList lstItems = new ArrayList();Queue queueFirst=new Queue();for(int i=0 ; i LeftItem.Count ; i+ )lstFirsti=new ArrayList();Product product=(Product)LeftItemi;/分成四步求FIRST集式 SELECT集 /1.如果 X 属于VT 则FIREST(X)=Xif(SymbolSet.getInstance().IsInEndSet(product.LeftItem)lstFirsti.Add(product.LeftItem);else lstFirsti=new ArrayList();/以此检测每一个右部for(int j=0 ; ja.,a属于VT,则 a 属于 FIREST(X)string strFirstLetter=product.StringRightItemAt(j).Substring(0,1);if(SymbolSet.getInstance().IsInEndSet(strFirstLetter)if(!Tools.IsInList(strFirstLetter,lstFirsti)lstFirsti.Add(strFirstLetter);/Console.Write(strFirstLetter + x );/3.如果 X 推出 $ ,则 $ 属于 FIRST(X)if(Tools.IsInList(product.LeftItem,emptyList)if(!Tools.IsInList($,lstFirsti)lstFirsti.Add($);/if(i=1)Console.WriteLine(bbbbbbbbb);/Console.Write($ 0 );/4.如果产生式的右部的每一个字符都是非终结符集if(product.CheckRightItemAt(j)string strRightTemp=product.StringRightItemAt(j);if(CheckEmptySymbol(strRightTemp.Substring(0,1)for(int l=0 ; lstrRightTemp.Length ; l+ )bool bNext=true;if(CheckEmptySymbol(strRightTemp.Substring(l,1) & bNext)string strQueueElement=;if(l=strRightTemp.Length-1)strQueueElement=product.LeftItem + product.StringRightItemAt(j).Substring(l,1);/ConsoleelsestrQueueElement=product.LeftItem + product.StringRightItemAt(j).Substring(l,1) + $;if(!Tools.IsInQueue(strQueueElement,queueFirst)queueFirst.Enqueue(strQueueElement);Console.WriteLine(strQueueElement + txp);elsebNext=false;string strQueueElement=product.LeftItem + product.StringRightItemAt(j).Substring(l,1);if(!Tools.IsInQueue(strQueueElement,queueFirst)queueFirst.Enqueue(strQueueElement);Console.WriteLine(strQueueElement + txp);elsestring strQueueElement=product.LeftItem + product.StringRightItemAt(j).Substring(0,1);if(!Tools.IsInQueue(strQueueElement,queueFirst)queueFirst.Enqueue(strQueueElement);Console.WriteLine(strQueueElement+ txp);else/假如产生式的右部并非都是非终结符/那么取出第一个字符,假如是终结符,那么在上面的第2步里就已经计算过了,所以不用再计算/假如是非终结符就假如到待取队列if(SymbolSet.getInstance().IsInNotEndSet(product.StringRightItemAt(j).Substring(0,1)string strQueueElement=product.LeftItem + product.StringRightItemAt(j).Substring(0,1);if(!Tools.IsInQueue(strQueueElement,queueFirst)queueFirst.Enqueue(strQueueElement);Console.WriteLine(strQueueElement + txp);/end for j/end if IsInEndSet(X)/end for ilstItems=FinishFirst(lstFirst,queueFirst);return lstItems;#endregion#region 完成FIRST集计算,把未求出FIRST集的非终结符求出public ArrayList FinishFirst(ArrayList FirstList,Queue queueFirst)/初始化标记数组bool FirstFinished=new boolFirstList.Length;for(int i=0 ; iFirstFinished.Length ; i+)FirstFinishedi=true;/将队列中元素依次取出,将出现的元素标记为false,意为这个FIRST集未求出for(int i=0 ; i0 & iOutException!=100)iOutException+;/首先取出队列中的一个元素string strQueue=queueFirst.Dequeue().ToString();/获取队列元素相关信息int iPos1=getLeftIndex(strQueue.Substring(0,1);int iPos2=getLeftIndex(strQueue.Substring(1,1);/假如右部的FIRST集已经求出,那么就把右部的FIRST集加入到左部FIRSTif(FirstFinishediPos2)ArrayList nextArray=FirstListiPos2;if(strQueue.Length=3)FirstListiPos2.Remove($);FirstListiPos1=Tools.AddArrayList(FirstListiPos1,FirstListiPos2);if(strQueue.Length=3 & this.CheckEmptySymbol(strQueue.Substring(1,1)FirstListiPos2.Add($);/假如该元素不再在队列中元素左部出现,那么标记该元素FIRST集已经求出if(Tools.IsQueueElement(strQueue,0,1,queueFirst)=false)FirstFinishediPos1=true;elsequeueFirst.Enqueue(strQueue);ArrayList aryFirst=new ArrayList();foreach (ArrayList arylst in FirstList)aryFirst.Add(arylst);return aryFirst;#endregion#region 得到FOLLOW集/ / 得到FOLLOW集/ / 需要把FIRST集传入/ ArrayListpublic ArrayList FollowSet(ArrayList aryFirst)if(LeftItem.Count=0) return null;ArrayList lstFollow = new ArrayListLeftItem.Count;ArrayList lstFirst = Tools.ConvertToArray(aryFirst);ArrayList lstItems = new ArrayList();Stack RemoveList=new StackLeftItem.Count;Queue queueFollow=new Queue();string strStartLetter=this.listboxProducts.Items0.ToString().Substring(0,1);bool iFollowFinished=new boolLeftItem.Count;for(int i=0 ; iLeftItem.Count ; i+ )/初始化标记位iFollowFinishedi=true;/初始化Follow集lstFollowi=new ArrayList();RemoveListi=new Stack();/FOLLOW集的求法(规定第一个产生式的第一个字符式开始符)/1.如果 X 是开始符 那么把 # 加入到 FOLLOW(X)lstFollow0.Add(#);/第一次进行扫描,把符合条件的符号和FIRST集,FOLLOW集全部加入for(int i=0 ; iLeftItem.Count ; i+ )Product product=(Product)LeftItemi;lstFollowi=FollowLetter(product.LeftItem,lstFollowi);/扫描同时把能够替换FIRST集,FOLLOW集的先替换int FollowCount=lstFollowi.Count;for(int j=0; j=0)int indexLeft=this.getLeftIndex(strNextFollow.Substring(6,1);lstFollowi=Tools.AddArrayList(lstFollowi,lstFirstindexLeft);elsestring strNextLetter=strNextFollow.Substring(7,1);queueFollow.Enqueue(product.LeftItem + strNextLetter);Console.WriteLine(Queuet + product.LeftItem + strNextLetter);/end first follow/end if strNextFollow.Length!=1/end for jwhile(RemoveListi.Count0)string strRemove=(String)RemoveListi.Pop();lstFollowi.Remove(strRemove);/end for i/将队列中元素依次取出,将出现的元素标记为false,意为这个FOLLOW集未求出for(int i=0 ; i0 & iOutException!=100)iOutException+;/首先取出队列中的一个元素string strQueue=queueFollow.Dequeue().ToString();/获取队列元素相关信息int iPos1=getLeftIndex(strQueue.Substring(0,1);int iPos2=getLeftIndex(strQueue.Substring(1,1);/如果后续元素FOLLOW集已经求出那么就把它加入到前面元素的FOLLOW集if(iFollowFinishediPos2)lstFollowiPos1=Tools.AddArrayList(lstFollowiPos1,lstFollowiPos2);/假如该元素不再在队列中元素左部出现,那么标记该元素FIRST集已经求出if(Tools.IsQueueElement(strQueue,0,1,queueFollow)=false)iFollowFinishediPos1=true;elsequeueFollow.Enqueue(strQueue);if(iOutException=100)/假如进入了死循环,强行把第一个FOLLOW集设置为已经求出,然后依次再计算一次iFollowFinished0=true;iOutException=0;while(queueFollow.Count0 & iOutException!=100)iOutException+;/首先取出队列中的一个元素string strQueue=queueFollow.Dequeue().ToString();/获取队列元素相关信息int iPos1=getLeftIndex(strQueue.Substring(0,1);int iPos2=getLeftIndex(strQueue.Substring(1,1);/如果后续元素FOLLOW集已经求出那么就把它加入到前面元素的FOLLOW集if(iFollowFinishediPos2)lstFollowiPos1=Tools.AddArrayList(lstFollowiPos1,lstFollowiPos2);/假如该元素不再在队列中元素左部出现,那么标记该元素FIRST集已经求出if(Tools.IsQueueElement(strQueue,0,1,queueFollow)=false)iFollowFinishediPos1=true;elsequeueFollow.Enqueue(strQueue);/把FOLLOW集拼装好并返回for(int i=0 ; iLeftItem.Count ; i+)/FOLLOW集中没有空串,移除所有空串while(Tools.IsInList($,lstFollowi)lstFollowi.Remove($);lstItems.Add(lstFollowi);return lstItems;#endregion#region 辅助求FOLLOW集,返回所有产生式右部指定的字符后边的字母private ArrayList FollowLetter(string strChar,ArrayList arylstFollow)for(int i=0 ; i=0 )/假如所求字符的下一个字符并不存在if(strRightItem.Length-1=iPos)if(!Tools.IsInList(strFollow,arylstFollow)arylstFollow.Add(strFollow);elsestring strNextChar=strRightItem.Substring(iPos+1,1);/所求字符X的下一个字符如果是终结符,直接加入FOLLOW(X)集if(SymbolSet.getInstance().IsInEndSet(strNextChar)if(!Tools.IsInList(strNextChar,arylstFollow)arylstFollow.Add(strNextChar);else/否则把下一个字符的FIRST集加入FOLLOW(X)集if(!Tools.IsInList(FIRST( + strNextChar + ),arylstFollow)arylstFollow.Add(FIRST( + strNextChar + );/所求字符X的下一个字符如果能够星推导出空,就把产生式左部字符的FOLLOW集直接加入FOLLOW(X)集if(CheckEmptySymbol(strNextChar) )if(!Tools.IsInList(strFollow,arylstFollow)arylstFollow.Add(strFollow);return arylstFollow;#endregion#region 得到SELECT集public ArrayList SelectSet(ArrayList aryFirst,ArrayList aryFollow)ArrayList lstSellect = new ArrayListlistboxProducts.Items.Count;ArrayList lstItems = new ArrayList();bool bNeedFollow = new boollistboxProducts.Items.Count;for(int i=0 ; ia , a 属于终结符集,那么select(X-a)=alstSellecti.Add(strFirstLetter);else if(strFirstLetter=$)/2.假如 X-$ 那么select(X-$)=FOLLOW(X)lstSellecti=Tools.AddArrayList(lstSellecti,(ArrayList)aryFollowgetLeftIndex(strLeft);else /3.如果 X-A 如果A是非终结符且A能星推导出$/那么 select(X-A)=FIRST(A)-$ U FOLLOW(X)/否则 select(X-A)=FIRST(A)string strRight=listboxProducts.Itemsi.ToString().Substring(2);/if(Tools.IsAllNotEnd(strRight)/bool bNext=true;for(int j=0 ; jstrRight.Length ; j+)string strChar=strRight.Substring(j,1);if(CheckEmptySymbol(strChar) & bNext)/Console.WriteLine(strChar + asdfasdfsad);ArrayList firstlist=(ArrayList)aryFirstgetLeftIndex(strChar);firstlist.Remove($);lstSellecti=Tools.AddArrayList(lstSellecti,firstli