《编译原理课程设计》LL1文法判定.docx

1、编译原理课程设计LL1文法判定目 录1 前言 12需求分析 13概要设计（特殊功能） 14详细设计 25源代码及调试 26使用说明及测试结果 117结论 128总结与体会 129参考文献 12 1 前言 1.1 课题简介试编写一个程序，用来计算给定文法的全部FIRST集及FOLLOW集，并判定所给文法是否LL(1)文法，掌握消除左递归及消除回溯的方法，掌握LL(1)分析器的基本结构及FIRST集、FOLLOW集、LL(1)分析表的构造方法，能根据文法写出给定输入串的自下而上分析过程。1.2 方案及其论证LL(1)文法使用的是确定的自顶向下的分析技术。LL(1)的含义是：第一个L表明自顶向下分析

2、是从左向右扫描输入串，第2个L表明分析过程中将使用最左推导，1表明只需向右看一个符号便可决定如何推导，即选择哪个产生式(规则)进行推导。LL(1)文法的判别需要依次计算FIRST集、FOLLOW集和SELLECT集,然后判断是否为LL(1)文法,最后再进行句子分析。2需求分析本次课程设计要求编写一个程序，用来计算给定文法的全部FIRST集及FOLLOW集，并判定所给文法是否LL(1)文法。首先要面临一个问题就是本次程序具体实现的是一个内部给定的正确文法，其次是依次计算FIRST集、FOLLOW集和SELLECT集，然后判断是否为LL(1)文法,最后再进行句子分析。终结符，非终结符，FIRST集

3、，FOLLOW集，SELLECT集和LL(1)分析表对于课程设计LL(1)问题的解决是特别的重要，计算出FIRST集、FOLLOW集和SELLECT集后，后面LL(1)分析表的构造以及判断文法是否为LL(1)文法就很容易解决了。3概要设计（特殊功能） 3.1系统结构图3.2主要控制流程改造文法无4详细设计4.1 词法分析程序的实现由于本程序简单，所以依次扫描遇到的每一个字符即可确定哪些是终结符哪些是非终结符。4.2 语法分析程序的实现4.2.1 能推出$的非终结符首先进行第一次扫描，把能够直接推出$的非终结符号记录到空串表，把不能直接推出$的符号依次记录下来，然后单个扫描每一个不能直接推出$的

4、符号。扫描这个符号能够直接推出的第一个非终结符记录到一个队列，接下来依次检查队列中每一个元素，把二次能够推出$的符号记录到空串表，把二次也推不出空串的继续送入到队列，然后再从队列取元素扫描，直到队列为空没能找到能够星推导出$的终结符，那么可以确定这个非终结符推导不出$，接下去扫描下一个非终结符。4.2.2 FIRST集的确定FIRST集使用以下四个步骤判定：(1)、若XVT ,则FIRST(X)=X(2)、若XVN,且有产生式Xa，aVT 则把a加入到FIRST(X)中，即aFIRST(X)(3)、若XVN,且有产生式X$， 则把$也加到FIRST(X)中，即$FIRST(X)(4)、若XVN

5、, 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)其中第1-3个方法都很好处理，关键是第四个方法判断时首先判断第一个字符为非终结符，设定一个布尔型扫描标志FLAG，赋初值TRUE，接下去依次扫描产生式右部每一个字符Yi，假如第i个字符可以推出空，那么就把这个字符的FIRST集去除$加入到产生式左部字符的

6、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集中去，没有完成的非终结符再

7、送回到队列，这时候可能出现死循环，比如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次循环或许有些多了，那么到极限情况，可能就是循环总共产生式的个数次数时如果再循环就可以确定是进入死循环了。4.2.3 FOLLOW集的确定FOLLOW集使用

8、以下三个步骤判定：(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集已经求出，所以第一次扫描就可以把相

9、应的FIRST集加入到FOLLOW集中，设置FOLLOW集完成标记位，设置队列，把未完成的非终结符送入队列，依次取出队列元素，把求出FOLLOW集的非终结符的FOLLOW集加入到相应的FOLLOW集中，把未求出的送回队列。如果碰到死循环使用FIRST集一样的方法处理就可以。4.2.4 SELLECT集的确定FIRST集FOLLOW集都已经求出来后SELLECT集就很好求了，扫描每一个产生式，使用以下三个步骤确定：A AVN，V*，(1)、若是终结符，那么SELLECT(A)=；(2)、若是$，则SELECT(A)=FOLLOW(A)；(3)、若是非终结符，那么 若*=$，则SELECT(A)=

10、(FIRST()-$)FOLLOW(A)； 若*=$ 则SELECT(A)=FIRST()。4.2.5 LL(1)文法的判定当SELLECT集求出来后就可以判断是不是一个文法是不是LL(1)文法了，扫描产生式左部相同的SELLCET集是否含有相同元素，一旦发现相同元素立刻返回FALSE，扫描结束没有发现相同元素则返回TRUE。4.3 句子的判定当一个文法确定是LL(1)文法时就可以对输入的语句进行判定了。首先要安装SELLECT集生成LL(1)预测分析表，最简单的方法是使用哈希表来表示，把每一个产生式左部依次和这个产生式SELLECT集中的每一个终结符组成关键字，其值即为这个产生式，送入哈希表

11、。这样在进行句子的分析时就可以很容易判断是否使用某一个产生式来进行规约。在实际分析时设置两个栈，把#压入分析栈和剩余栈，把开始符压入分析栈，把输入串从右向左送入剩余栈，然后只要两个栈元素个数同时大于1，那么依次从两个栈中取出两个元素进行比较，假如一样就匹配，假如可以规约就规约，否则就不是该文法的句子。5源代码及调试frmMain.cs主要算法：#region 主要步骤 #region 得到FIRST集 / / 得到FIRST集 / / ArrayList public ArrayList FirstSet() ArrayList lstFirst = new ArrayListLeftItem

12、.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)=X if(SymbolSet.getInstance().IsInEndSet(product.LeftItem) lstFirsti.Add(produ

13、ct.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); /Cons

14、ole.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=produc

15、t.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.StringRightItemA

16、t(j).Substring(l,1); /Console else strQueueElement=product.LeftItem + product.StringRightItemAt(j).Substring(l,1) + $; if(!Tools.IsInQueue(strQueueElement,queueFirst) queueFirst.Enqueue(strQueueElement); Console.WriteLine(strQueueElement + txp); else bNext=false; string strQueueElement=product.LeftI

17、tem + product.StringRightItemAt(j).Substring(l,1); if(!Tools.IsInQueue(strQueueElement,queueFirst) queueFirst.Enqueue(strQueueElement); Console.WriteLine(strQueueElement + txp); else string strQueueElement=product.LeftItem + product.StringRightItemAt(j).Substring(0,1); if(!Tools.IsInQueue(strQueueEl

18、ement,queueFirst)queueFirst.Enqueue(strQueueElement); Console.WriteLine(strQueueElement+ txp); else /假如产生式的右部并非都是非终结符 /那么取出第一个字符,假如是终结符,那么在上面的第2步里就已经计算过了,所以不用再计算 /假如是非终结符就假如到待取队列 if(SymbolSet.getInstance().IsInNotEndSet(product.StringRightItemAt(j).Substring(0,1) string strQueueElement=product.LeftI

19、tem + 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 i lstItems=FinishFirst(lstFirst,queueFirst); return lstItems; #endregion #region

20、完成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) iOutExc

21、eption+; /首先取出队列中的一个元素 string strQueue=queueFirst.Dequeue().ToString(); /获取队列元素相关信息 int iPos1=getLeftIndex(strQueue.Substring(0,1); int iPos2=getLeftIndex(strQueue.Substring(1,1); /假如右部的FIRST集已经求出,那么就把右部的FIRST集加入到左部FIRST if(FirstFinishediPos2) ArrayList nextArray=FirstListiPos2; if(strQueue.Length=3

22、) 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=tr

23、ue; else queueFirst.Enqueue(strQueue); ArrayList aryFirst=new ArrayList(); foreach (ArrayList arylst in FirstList) aryFirst.Add(arylst); return aryFirst; #endregion #region 得到FOLLOW集 / / 得到FOLLOW集 / / 需要把FIRST集传入 / ArrayList public ArrayList FollowSet(ArrayList aryFirst) if(LeftItem.Count=0) return

24、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); bo

25、ol 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 Follo