编译原理-实验3-LL(1)分析文法构造

1、课程名称：编译原理 实验编号：实验三 班级：计算14上机实践日期：2017.6集美大学计算机工程学院实验报告指导教师：付永钢实验成绩：实验名称：LL(1)语法分析器的构造姓名：学号上机实践时间：6学时 一、实验目的1、掌握LL(1)分析法的基本原理；2、掌握LL(1)分析表的构造方法；3、掌握LL(1)驱动程序的构造方法。 二、实验环境Ubuntu三、实验原理1、对文法要求LL(1)分析法属于自顶向下分析方法，因此需要预测匹配的产生式。即在 LL(1)分析 法中，每当在符号栈的栈顶出现非终结符时，要预测用哪个产生式的右部去替换该非终 结符。LL(1)分析方法要求文法满足如下条件：对于任一非终结

2、符A,其任意两个产生式A ,A ,都要满足下面条件：First(A )A First (A )=2、分析表构造LL(1)分析表的作用是对当前非终结符和输入符号确定应该选择用哪个产生式进行推 导。它的行对应文法的非终结符，列对应终结符，表中的值有两种：一是产生式的编 号，一是错误编号。若用T表示LL(1)分析表，则T可表示如下：T: VnWt PU ErrorT(A, t) = A 当 t First(A )T(A, t) = Error,否则其中P表示所有产生式的集合。显然，一个文法 G是LL(1)文法，当且仅当T的元 素包含唯一的一个产生式或Error o3、驱动程序构造LL(1)分析主要包

3、括以下四个动作，其中 X为符号栈栈顶元素，a为输入流当前享替换：当X Vn时选相应产生式的右部 去替换X。匹配：当X Vt时它与a进行匹配，其结果可能成功，也可能失败，如果成功则 符号栈中将X退栈并将输入流指针向前移动一位，否则报错。成功：当格局为(空，空)时报告分析成功。报错：出错后，停止分析。四、实验内容已知文法GE:E-E+T|TTT*F|F F-(E)|i 说明：终结符号i为用户定义的简单变量，即标识符的定义。1、消除文法的左递归，构造对应文法的预测分析表；2、根据构造的预测分析表，实现 LL(1)分析中控制程序(表驱动程序)，并完成整 个的LL(1)分析程序的界面设计、运行；3、P1

4、04中，3.36写一个Yacc程序，把输入的算术表达式翻译成对应的后缀表达式 输出。要求转换正确，同时对于简单错误能够识别。4、P104中，3.37,写一个Yacc “台式计算器”程序，它计算布尔表达式，其中的 词法分析器用Lex写。要求转换正确，同时对于简单错误能够识别。五、实验要求1、输入用应是词法分析的输出二元式序列，即某算术表达式“实验项目一”的输 出结果。输出为输入用是否为该文法定义的算术表达式的判断结果。2、LL(1)分析过程应能发现输入用中的错误。3、设计至少两个测试用例(尽可能完备，正确和出错)，并给出测试结果。 六、实验步骤、1、分析文法(1) E=>E+T=>E

5、+T*F=>E+T*(E)即有E=>E+T*(E)存在左递归。用直接改写法消除 左递归，得到如下文法：GE:E-TE'E'+TE'|eT-FT'T'一*FT 卜F 一 (E)|i(2)对于以上改进的文法，可以得到：FIRST(E'尸FIRST(+T U FIRST(-TE ') U e =+ , £ FIRST(T' )=FIRST(*FT U FIRST(/FT') U £ =* , £ FIRST(E)= FIRST( T ) = FIRST( F 尸FIRST(E) U FI

6、RST(i)=( , i 由此得到各非终结符的FOLLOW集合：FOLLOW(E)= ) , $FOLLOW(E '尸FOLLOW(E)=) , $FOLLOW(T尸FIRST(E ') U FOLLOW(E')= +, ), $FOLLOW(T '尸FOLLOW(T)= + , ), $FOLLOW(F尸FIRST1、构造LL(1)分析表采用手工操作构造LL(1)分析表。LL(1)分析表用一个二维矩阵表示，其中每个非终 结符对应一行，每个终结符对应一列，一个非终结符和一个终结符可以确定矩阵中的一 个元素，元素的值表示该非终结符和该终结符对应的产生式。每个矩阵元

7、素都是一个符 号用，所有元素初始化为构造LL(1)表时，根据文法和各个产生式的 First集，填写 LL(1)分析表的内容。各产生式只要降右端填入到对应的表项中即可，用空用表示 Erroro在根据LL(1)分析表选择产生式进行推导时，若查到的产生式为空用表示无相应 的产生式可选，不匹配错误；否则根据符号用得到相应的产生式进行推导，即进行压栈 操作。步骤 1分析栈(栈顶符号，当前输入 符)剩余用所用产生式$E(E, i)查表i+i*i$E->TE，2$E，T(T, i)查表i+i*i$T->FT，3$E，T，F(F, i)查表i+i*i$F->i4$E，T，i(i , i) i

8、匹配i+i*i$5$E，T，(T，, +)查表+i*i$T，->e6$E，(E，, +)查表+i*i$E，->+T E，7$E，T+(+, +) +匹配+i*i$8 r$E，T(T, i)查表i*i$T->FT，9$E，T，F(F, i)查表i*i$F->i10$E，T，i(i , i) i匹配i*i$11$E，T，(T，, *)查表*i$T，->*F T /12$E，T，F*(*, *)*匹配*i$13$E，T，F(F, i)查表i$F->i114$E，T，i(i , i) i匹配i$15$E，T，(T，, $)查表$T，->e16$E，(E /查表

9、$E / - > £17$2 .数据结构LL(1)语法分析程序共用到个栈，分别称为：符号栈，语法树栈，操作符栈和操作数栈。其中，符号栈用于进行LL(1)语法分析；其它的栈是为了在语法分析的过程中同 时生成与源程序结构对应的语法树而设。语法树栈用于生成声明部分和语句部分的语法 树；操作符栈和操作数栈用于生成表达式部分的语法树。3 .构造驱动程序构造LL(1)驱动程序的算法：(1) .分析开始时，首先将标志符号#和文法开始符号S依次压入符号栈；输入流 指针指向第一个输入符号，即由符号栈和输入流构成的初始格局为：(#S,aa2.a#)然后，反复执行第2步所列的工作。(2) .设在分析

10、的某一步，符号栈及剩余的输入流处于如下的格局(#XiX2Xm-iXm,aiai+1an#)其中，X1X2Xm-lXm为分析过程中所得的文法符号，此时，可视栈顶符号Xm的不同情况，分别作如下动作：若Xm Vn,则以Xm及ai组成的符号对(Xm, a)查分析表To设T(Xm, ai)为一产 生式，假设是Xm UVW,此时将Xm从分析栈中退出，并将 UVW压入栈中，从而 得到新的格局(#XiX2.Xm-iWVU, aiai+1 an#)但若T(Xm, a尸Error,则调用出错处理程序进行处理；若Xm=ai #,则表明栈顶符号已经与当前扫描的输入符号得到匹配，此时应将Xm (即ai)从栈中退出，并将

11、输入流指针向前移动一个位置。若Xm=ai=#,则表明输入用已经完全得到匹配，此时即可宣告分析成功而结束分 析。其它情形，转错误处理程序。程序见附录七、实验结果 正确的语法：Input | ActionInputLf$US',Etablepression:i*-i + -i TEFT*x»x'TXf.XLYY, (F»+Ii*i+S$ i+i+54 -i*田$I EII|3$I斗|标|?$裆E -> TE1 T -> FT' F -> i i Match"! ng T* -> *FT? * Matching F -&g

12、t;电 i Matching T, -> E E -> +TET + Hatchn ng T -> FT' F -> i i Matching T* -> E错误的语法:六、实验小结1、 在本次实验中，通过设计、编制、调试一个递归下降语法分析程序，实现对词法分析程序所提供的单词序列进行语法检查和结构分析，掌握LL(1) 分析法的基本原理、掌握LL(1)分析表的构造方法、掌握LL(1)驱动程序的构造方法；2、通过本次实验，对LL(1) 递归下降分析程序的构造和设计有了更为全面的认识，对 LL(1) 文法分析程序的实现有了进一步了解；3、实验输入串以$结束，才

13、用栈的形式，依次弹出进行处理；附录：程序代码：#coding:utf-8from prettytable import PrettyTabledef LL1():global c,flagif(c='E'):if(ak='i' or ak='('):table.add_row(ak:, "E -> TE'")stack.append('X') stack.append('T') print stack c=stack.pop() else:error()flag=1elif(c=&

14、#39;X'):if(ak='+'):table.add_row(ak:, "E' -> +TE'")stack.append('X') stack.append('T') stack.append('+') print stack c=stack.pop() elif(ak=')' or ak='$'):table.add_row(ak:, "E' ->£ ")print stack c=stack.po

15、p()else:error()flag=1elif(c='T'):if(ak='i' or ak='('):table.add_row(ak:, "T -> FT'") stack.append('Y') stack.append('F') print stack c=stack.pop()else:error()flag=1elif(c='Y'):if(ak='*'):table.add_row(ak:, "T' -> *F

16、T'") stack.append('Y') stack.append('F') stack.append('*') print stack c=stack.pop()elif(ak='+' or ak=')' or ak='$'): table.add_row(ak:, "T' ->£ ")print stack c=stack.pop()else:error()flag=1elif(c='F'):if(ak='

17、i'):table.add_row(ak:, "F -> i") stack.append('i') print stack c=stack.pop()elif(ak='('):table.add_row(ak:, "F -> (E)") stack.append(')') stack.append('E') stack.append('(') print stack c=stack.pop()else:error() flag=1def error():

18、global ktable.add_row(ak, "Error")print stackk+=1if _name_ = '_main_':a=raw_input("Input Etablepression:")a=a+'$'for temp in a:if(temp!='i' and temp!='+' and temp!='*' and temp!='(' and temp!=')' and temp!='$'):print "You input is wrong!"exit(0)table = PrettyTable(&quo