资源描述：
《编译原理实验ll分析》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。
1、实验三语法分析…LL(1)分析器目录一.实验的目的与思路2(1)目的2(2)思路2二.基本的功能3三.总体设计4四.详细设计5五.源程序清单6六.源代码6实验的目的与思路(1)目的1.用程序的方法实现语法分析的LL(1)方法。(2)思路本程序是采用的LL(1)方法进行的语法分析，而LL(1)的分析方法是属于自上而下的方法。自上而下分析的基本思想是：对任意输入串，试图用一切可能的方法，从文法开始符号(根结点)出发，自上而下为输入串建立一棵语法树。从推导的角度看，它是从文法的开始符号出发，反复使用各种产生式，寻找与输入串匹配的推导。在输入之前必须要进行该文法是不是LL(1)
2、文法的判断，然后再构造相应的LL(1)分析表来用预测分析方法进行语法分析，依据下血的文法及分析表来设计程序实现预测分析的分析过程。1.文法G[E]：E->E+T
3、TT->T*F
4、FF->(E)
5、i2.通过观察可知道该文法是一个左递归文法，要进行语法分析就必须消除左递归才能继续判断它是不是LL(1)文法，然后才能用预测分析方法进行语法分析。3.消除左递归：E->TMM—>+TM
6、uT->FQQ->*FQ
7、uF(E)
8、i4.在进行LL(1)文法的判断：(1.)各非终结符的FIRST集如下：FIRST(E)=FIRST(TM)={(,i}FIRST(M)={+}FIRST(T
9、)={(,i}FIRST(Q)={*}FIRST(F)={(,i}(2.)各非终结符的FOLLOW集如下：FOLLOW(E)={),#}FOLLOW(M)={),#}FOLLOW(T)={+,),#}FOLLOW(Q)={+,),#}FOLLOW(F)二{*,+,),#}(3.)各产生式的SELECT集如下：SELECT(ETTM)={(,i}SELECT(M-^+TM)={+}SELECT(MF)={},#)SELECT(TTFQ)={(,i}SELECT(Q»FQ)={*}SELECT(QTu)={+,),#)SELECT(FT(E))={()SELECT(F》)=
10、{i}因为：SELECT(MT+TM)QSELECT(MTu)=OSELECT(QT*FQ)nSELECT(QTu)二①SELECT(FT(E))ASELECT(FTi)二①因此可以判断该文法是一个LL(1)文法可以构造预测分析表。1.根据可选集构造预测分析表如下：■1+*()ftEE->TME->TMMM->+TMM->uM->uTT->FQT-〉FQQQ->uQ->*FQQ->uQ->uFF->iF->(E)二.基本的功能下面主要采用了LL(1)分析方法来进行语法分析，先通过判断该文法是不是LL(1)文法，如果不是先将其改写成LL(1)文法，再将LL(1)文法改造成
11、等价形式……LL(1)分析表，通过分析表来进行语法分析，本程序的主要功能是对一个文法句子的生成过程进行分析。三•总体设计LL(1)的语法分析程序包含了三个部分，总控程序，预测分析表函数，先进先出的语法分析栈，本程序也是采用了同样的方法进行语法分析其功能模型图如下：LL(1)语法分析功能模型图本程序是采用预测的分析方法，因此预测分析方法的基本算法如下：(1)判断该文法是不是LL(1)文法，如果该文法不是LL(1)文法，则修改该文法继续判断该文法是不是LL(1)文法，如果是则进行第二步，否则不运行。(2)构造预测分析表：1.对文法G的每个产生式A->a执行第二步和第三步；2
12、.对每个终结符aeFIRST(a),把A->a加至L[A,a]中；3.若eeFIRST(a),则对任意beFOLLOW(A)把A->a加至L[A,b]中;4.把所有无定义的L[A,a]标上“出错标志”；上述算法可应用于任何文法G以构造它的预测分析表L。但是对于某些文法，有些L[A,a]可能持有若干个产生式，或者说有些L[A,a]可能是多重定义的。如果G是左递归或是二义的，那么L至少含有一个多重定义入口。因此，消除左递归和提取左因子将有助于获得无多重定义的分析表Lo本题是在将文法消除左递归和提取左因子等工作之后的基础上进行的，也就是针对LL(1)文法来构造预测分析表，从而
13、达到预测分析表不含多重定义入口的效果。本程序的设计只是一个语法分析程序，预测表的部分将被固定在一个二维数。组中，然后进行预测分析过程。(3)对一个输入串的预测分析过程1.将开始符和进栈输入当前符，进行查表比较，如果不匹配，就将所用产生式进栈然后再进行查表。1.进行查表后如果匹配则将所用的产生式出栈处理2.如果所用到的产生式是u(表示空符)那么就将所用到的产生式出栈处理。3.如果有与'#'匹配则表示成功接收字符串，否则就不能成功接收，不能推导(1)算法的模块图:main()函数模块(2)主程序的流程图程序流程图五•测试数据(1)E*i+i#
