(完整word版)编译原理实验3LL分析文法构造.docxVIP

集美大学计算机工程学院实验报告 课程名称 ：编译原理 指导教师 ：付永钢 实验成绩 ： 实验编号 ： 实验三 实验名称 ： LL(1) 语法分析器的构造 班级：计算 14 姓名： 学号 上机实践日期 ：2017.6 上机实践时间 ： 6 学时 一、实验目的1、掌握2、掌握3、掌握  LL(1) 分析法的基本原理； LL(1) 分析表的构造方法； LL(1) 驱动程序的构造方法。 二、实验环境 Ubuntu 三、实验原理 1、对文法要求 LL(1) 分析法属于自顶向下分析方法，因此需要预测匹配的产生式。即在  LL(1) 分析 法中，每当在符号栈的栈顶出现非终结符时，要预测用哪个产生式的右部去替换该非终 结符。 LL(1) 分析方法要求文法满足如下条件：对于任一非终结符 A，其任意两个产生式 A ,A ，都要满足下面条件： First(A )∩First (A )= 2、分析表构造 LL(1) 分析表的作用是对当前非终结符和输入符号确定应该选择用哪个产生式进行推导。它的行对应文法的非终结符，列对应终结符，表中的值有两种：一是产生式的编号，一是错误编号。若用 T 表示 LL(1) 分析表，则 T 可表示如下： T: V N ×V T P∪ {Error} T(A, t) = A α，当 t First(A T(A, t) = Error ，否则  α) 其中 P 表示所有产生式的集合。显然，一个文法 G 是 LL(1) 文法，当且仅当 T 的元 素包含唯一的一个产生式或 Error。 3、驱动程序构造 LL(1) 分析主要包括以下四个动作，其中 X 为符号栈栈顶元素， a 为输入流当前字 符。 替换：当 X V N 时选相应产生式的右部 去替换 X 。 匹配：当 X V T 时它与 a 进行匹配，其结果可能成功，也可能失败，如果成功则 符号栈中将 X 退栈并将输入流指针向前移动一位，否则报错。 成功：当格局为（空，空）时报告分析成功。 报错：出错后，停止分析。 四、实验内容 已知文法 G[E]: E→ E+T|T T→ T*F|F F→(E)|i 说明：终结符号 i 为用户定义的简单变量 , 即标识符的定义。 1、消除文法的左递归，构造对应文法的预测分析表； 2、根据构造的预测分析表，实现 LL(1) 分析中控制程序（表驱动程序），并完成整个的 LL(1) 分析程序的界面设计、运行； 3、 P104 中， 3.36 写一个 Yacc 程序，把输入的算术表达式翻译成对应的后缀表达式输出。要求转换正确，同时对于简单错误能够识别。 4、 P104 中， 3.37，写一个 Yacc“台式计算器”程序，它计算布尔表达式，其中的词法分析器用 Lex 写。要求转换正确，同时对于简单错误能够识别。 五、实验要求 1、输入串应是词法分析的输出二元式序列，即某算术表达式“实验项目一”的输出结果。输出为输入串是否为该文法定义的算术表达式的判断结果。 2、 LL(1) 分析过程应能发现输入串中的错误。 3、设计至少两个测试用例（尽可能完备，正确和出错），并给出测试结果。 六、实验步骤、 1、分析文法 （1）E=E+T=E+T*F=E+T*(E) 即有 E=E+T*(E) 存在左递归。用直接改写法消除左递归，得到如下文法： G[E]: E→TE’ E’→+TE’|ε T→FT’ T’→*FT ’|ε F→(E)|i （2）对于以上改进的文法，可以得到： FIRST(E’ )=FIRST(+TE∪’FIRST(-TE ’)∪{ ε}={+ ，ε} FIRST(T ’ )=FIRST(*FT ∪’)FIRST(/FT ’)∪ { ε }={* ， ε} FIRST(E)= FIRST( T ) = FIRST( F )=FIRST((E)) ∪FIRST(i)={( ，i } 由此得到各非终结符的 FOLLOW 集合： FOLLOW(E)={ ) ，$} FOLLOW(E ’)=FOLLOW(E)={) ，$} FOLLOW(T)=FIRST(E ’)∪ FOLLOW(E ’)={ + ， )， $} FOLLOW(T ’)=FOLLOW(T)={ + ，)， $} FOLLOW(F)=FIRST 1、构造 LL(1) 分析表 采用手工操作构造 LL(1) 分析表。 LL(1) 分析表用一个二维矩阵表示，其中每个非终结符对应一行，每个终结符对应一列，一个非终结符和一个终结符可以确定矩阵中的一个元素，元素的值表示该非终结符和该终结符对应的产生式。每个矩阵元素都是一个符 号串，所有元素初始化为 ””；构造 LL(1) 表时，根据文法和各个产生式的 First 集，填写 LL(1) 分析表的内容。各产生式只要降右端填入到对应的表项中即可，用空串表示