编译原理-实验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: Vn Wt PU Error T(A, t) = A a 当 t First(A a T(A, t) = Error，否则 其中P表示所有产生式的集合。显然，一个文法G是LL(1)文法，当且仅当T的元 素包含唯一的一个产生式或Error

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

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

5、测试结果。 六、实验步骤、 1、分析文法 (1) E=E+T=E+T*F=E+T*(E)即有E=E+T*(E)存在左递归。用直接改写法消除 左递归，得到如下文法：GE: ETE E+TE|& TFT T*FT F(E)|i (2) 对于以上改进的文法，可以得到： FIRST(E )=FIRST(+TE U FIRST(-TE ) U =+，& FIRST(T )=FIRST(*FT ) FIRST(/FT)U & =*，& FIRST(E)= FIRST( T ) = FIRST( F )=FIRST(E) U FIRST(i)=(，i 由此得到各非终结符的FOLLOW集合： FOLLOW(E

6、)= )，$ FOLLOW(E )=FOLLOW(E)=)，$ FOLLOW(T)=FIRST(E )U FOLLOW(E )= +，)，$ FOLLOW(T )=FOLLOW(T)= +，)，$ FOLLOW(F)=FIRST 1、构造LL(1)分析表 采用手工操作构造LL(1)分析表。LL(1)分析表用一个二维矩阵表示，其中每个非终 结符对应一行，每个终结符对应一列，一个非终结符和一个终结符可以确定矩阵中的一 个元素，元素的值表示该非终结符和该终结符对应的产生式。每个矩阵元素都是一个符 号串，所有元素初始化为”；构造LL(1)表时，根据文法和各个产生式的 First集，填写 LL(1)分析

7、表的内容。各产生式只要降右端填入到对应的表项中即可，用空串表示 Error。在根据LL(1)分析表选择产生式进行推导时，若查到的产生式为空串表示无相应 的产生式可选，不匹配错误；否则根据符号串得到相应的产生式进行推导，即进行压栈 操作。 步骤 分析栈 (栈顶符号，当前输入 符) 剩余串 所用产生式 1 $E (E, i)查表 i+i*i$ E-TEX 2 $EXT (T, i)查表 i+i*i$ T-FTX 3 $EXF (F, i)查表 i+i*i$ F-i 4 $EX Txi (i , i) i匹配 i+i*i$ 5 $EX (，+)查表 +i*i$ - 6 $EX (Ex, +)查表 +

8、i*i$ Ex -+T Ex 7 $EX T+ (+, +) +匹配 +i*i$ 8 厂 $EXT (T, i)查表 i*i$ T-FJ 9 $EX TXF (F, i)查表 i*i$ F-i 10 $EXi (i , i) i匹配 i*i$ 11 $EX (，*)查表 *i$ - *F T / 12 $EXF* (*, *) *匹配 *i$ 13 $EX TXF (F, i)查表 i$ F-i 14 $EX Txi (i , i) i匹配 i$ 15 $EX (，$)查表 $ - 16 $EX (E / ,$)查表 $ Ex - 17 $ $ $ 2 数据结构 LL(1)语法分析程序共用到个

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

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

11、入串已经完全得到匹配，此时即可宣告分析成功而结束分 析。 其它情形，转错误处理程序。 程序见附录 七、实验结果 正确的语法： Input | Action +4 Input Lf$ ：f$ Etablepression:i*-i + -i TEF xT, 宀 *$5 f$ *$ 9, 宀 w 昔 XS TXf xs XS *F 错误的语法: E - TE1 T -； FT | f - i i 1 Matching | T* - *FT? * Matching F - 1 | i Matehing | T* - E | ET - +TET | + Hatchn ng | T - E F 1 |

12、i Matching | T* - E I E E Input | Action nput Etablepressi on:i *1+i Iii+i$ i+i$| j1*14+1$| |i*i+i$| E -A TE， T - FT F - -i 订 Matching 六、实验小结 1、在本次实验中，通过设计、编制、调试一个递归下降语法分析程序，实现对词 法分析程序所提供的单词序列进行语法检查和结构分析，掌握 LL(1) 分析法的基本原 理、掌握LL(1)分析表的构造方法、掌握LL(1)驱动程序的构造方法； 2、通过本次实验，对 LL(1) 递归下降分析程序的构造和设计有了更为全面的认 识，对

13、LL(1)文法分析程序的实现有了进一步了解； 3、实验输入串以 $结束，才用栈的形式，依次弹出进行处理； 附录：程序代码： #coding:utf-8 from prettytable import PrettyTable def LL1(): global c,flag if(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=1 elif(c=X): if(ak=+): table.add

14、_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.pop() else: error() flag=1 elif(c=T): if(ak=i or ak=(): table.add_row(ak:, T - FT) stack.append(Y) stack.append(F) print stack c=stack.pop() e

15、lse: error() flag=1 elif(c=Y): if(ak=*): table.add_row(ak:, T - *FT) 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=1 elif(c=F): if(ak=i): table.add_row(ak:, F - i) stack.appe

16、nd(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() error() flag=1 def error(): global k table.add_row(ak, Error) print stack k+=1 if _name_ = _main_: a=raw_input(Input Etablepression:) a=a+$ for temp in a: if

17、(temp!=i and temp!=+ and temp!=* and temp!=( and temp!=) and temp!=$): print You input is wrong! exit(0) table = PrettyTable(Input, Action) table.padding_width = 1 table.alignInput = r table.alignAction = l stack= k=0 flag=0 stack.append($) stack.append(E) table.add_row(ak:, ) print stack c=stack.pop() while(c!=$): if(c=ak): table.add_row(ak+1:,+ak+ Matching) print stack k+=1 c=stack.pop() elif(c=) and c!=a