编译原理LL(1)语法分析实验报告要点.pdf
学号 20102798 专业 软件工程姓名 薛建东 实验日期2013.04.08 教师签字成绩 实验报告 【实验名称 】LL（1）语法分析 【实验目的 】 通过完成预测分析法的语法分析程序，了解预测分析法和递归子程序法的区别和联系。 使了解语法分析的功能，掌握语法分析程序设计的原理和构造方法，训练掌握开发应用程序 的基本方法。 【实验内容 】 根据某一文法编制调试LL （ 1 ）分析程序，以便对任意输入的符号串进行分析。 构造预测分析表，并利用分析表和一个栈来实现对上述程序设计语言的分析程序。 分析法的功能是利用LL （1）控制程序根据显示栈栈顶内容、向前看符号以及LL （1）分析表，对输入符号串自上而下的分析过程。 【设计思想 】 （1） 、LL（1）文法的定义 LL(1) 分析法属于确定的自顶向下分析方法。LL(1) 的含义是： 第一个 L 表明自顶向下分 析是从左向右扫描输入串，第2 个 L 表明分析过程中将使用最左推导，1 表明只需向右看一 个符号便可决定如何推导，即选择哪个产生式( 规则 ) 进行推导。 LL(1) 文法的判别需要依次计算FIRST集、 FOLLOW 集和 SELLECT 集 , 然后判断是否为LL(1) 文法 , 最后再进行句子分析。 需要预测分析器对所给句型进行识别。即在LL(1) 分析法中，每当在符号栈的栈顶出现 非终极符时， 要预测用哪个产生式的右部去替换该非终极符；当出现终结符时，判断其与剩 余输入串的第一个字符是否匹配，如果匹配，则继续分析，否则报错。LL(1) 分析方法要求 文法满足如下条件： 对于任一非终极符A的两个不同产生式A,A， 都要满足下面条件： SELECT(A) SELECT(A)= （2） 、预测分析表构造 LL(1) 分析表的作用是对当前非终极符和输入符号确定应该选择用哪个产生式进行推 导。它的行对应文法的非终极符，列对应终极符，表中的值有两种：一是产生式的右部的字 符串，一是null 。若用 M表示 LL(1) 分析表，则M可表示如下： 1 M: VN×VTPError M(A, t) = A，当 tselect(A) ，否则 M(A, t) = Error 其中 P表示所有产生式的集合。 （3） 、语法分析程序构造 LL(1) 分析中 X为符号栈栈顶元素， a 为输入流当前字符， E为给定测试数据的开始符号， #为句子括号即输入串的括号。分析表用一个二位数组M表示， 数组元素MA，a 中的下标A 表示非终结符， a 为终结符或句子括号# ，二维数组中存放的是一条关于A 的产生式， 表 明当非终结符A向下推导时， 面临输入符a 时，所采用的候选产生式，当元素内容无产生式 时，则表明用A 的左部向下推导时出现了不该出现的符号，因此元素内容转向出错处理的 信息。 LL(1) 分析过程主要包括以下四个动作： 替换：当 X VN时选相应产生式的右部去替换 X。此时 X出栈，逆序入栈。 匹配：当 X VT时它与 a 进行匹配，其结果可能成功，也可能失败，如果成功则符号栈 中将 X退栈并将输入流指针向前移动一位，否则报错。 接受：当格局为（#，空 #）时报告分析成功。 报错：出错后，停止分析。并给出相应的错误提示信息。 【实验要求】 1、编程时注意编程风格：空行的使用、注释的使用、缩进的使用等。 2、如果遇到错误的表达式，应输出错误提示信息。 【流程图 】 1.总体思路分析及流程图 给定一个正规文法G，在 LL(1) 预测分析中， 必须先求出First集和 Follow 集，然后求 出 Select集，通过 Select集判断是否是LL1 文法， 如果是的话，构造预测分析表。求出预 测分析表之后，再输入一个字符串，依据LL1 分析表单步输出字符串的分析过程。 2 读取正规文法 求文法的 First 集求文法的 Follow 集 求文法的 Select 集 字符串分析键盘输入字符串 功能模块分解图 （1）主程序流程图 3 开始 输入文法 构造预测分析 表 提示 i*i+i#为 可接受的字符 串 判断文法是否为 LL(1) 文法 输入要分析的 符号串 Y 出错处理 N 判断该符号串是否可被 该文法识别 出错处理 结束 Y N （2）核心算法流程图 1. 计算非终结符的First集的算法及流程： First集合的构造算法： （1）若 X VT ，则 First（X）=X 。 （2）若 X VN ，且有产生式X a，则把a 加入到 First (X) 中；若 X也是一条 产生式，则把 也加到 First (X)中。 （3）若XY是一个产生式且YVN ，则把First (Y)中的所有非 - 元素都加到 First (X) 中；若 XY1Y2Yk 是一个产生式，Y1， Yi-1都是非终结符，而且，对于任 何 j ， 1j i-1 ，First (Yj)都含有 （即 Y1Yi-1* ） ，则把First (Yj)中的所有非 - 元素都加到First (X) 中；特别是，若所有的First (Yj) 均含有 ，j=1,2,， k，则把 加到 First (X)中。 连续使用上面的规则，直至每个集合First不再增大为止。 4 开始 读取一个非终 结符 V 遍历所有产生 式，查找左部 是V的产生式 取出得到的一 条产生式 产生式右部第一个符 号V*是终结符？ V* 是不是有推导规 则V*- 空 将该终结符V* 加入 V 的First 集 中 空标志为真 剩有非终结符？ 删除空，得到 V的First 集 结束 添加一个删除 空的标志为 true 2. 计算非终结符的Follow 集： Follow 集合的具体构造算法如下： （1）对于文法的开始符号S，置 #于 Follow(S)中； （2）若 A B 是一个产生式，则把First()| 加至 Follow(B) 中； （3）若 A B是一个产生式， 或 AB是一个产生式而 （即 First() ） ， 则把 Follow(A)加至 Follow(B)中。 连续使用上面的规则，直至每个集合Follow 不再增大为止。 5 开始 取得一个非终结符 V 查找产生式的右部 含有 V 的产生式 V 是不是最后一个字符 V 后一个字符 V* 是 否为终结符 添加 #到V的 Follow 集中 添加 V* 到V的 Follow 中 是否遍历完所有右 部含有 V的产生式 是否有未求解过的 非终结符 将V* 的First集加入到 V 的 Follow 集中 完成 Y Y Y N Y N Y N 3. 预测分析控制程序的算法流程 6 # E进 栈，当前终结 符号送入 a 显示分析步骤 AVt? A=#？ 产生式不存 在？ 若产生式为 A A1A2An,按逆序即 AnA2A1入栈 产生式右部为空？ 出错 A=a？ 读入下一符号 出错 N Y Y N N Y Y Y N 输入要分析的 字符串 判断字符串是否 正确 Y N 显示栈中内容 显示剩余输入 串 显示产生式N Y 匹配字符 串？ 接受 N Y 【源代码 】 #include #include #include 7 #include char A20;/*分析栈 */ char B20;/*剩余串 */ char v120='i','+','*','(',')','#'/*终结符 */ char v220='E','G','T','S','F'/*非终结符 */ int j=0,b=0,top=0,l;/*L为输入串长度 */ typedef struct type/*产生式类型定义 */ char origin;/*大写字符 */ char array5;/*产生式右边字符 */ int length;/*字符个数 */ type; type e,t,g,g1,s,s1,f,f1;/*结构体变量 */ type C1010;/*预测分析表 */ void print()/*输出分析栈 */ int a;/*指针 */ for(a=0;a“,cha.origin);/*输出产生式 */ for(j=0;j=0;j-)/*产生式逆序入栈*/ A+top=cha.arrayj; if(Atop='')/*为空则不进栈*/ top-; /*if*/ else/*出错处理 */ print(); print1(); printf(“%c出错 n“,x);/*输出出错非终结符*/ exit(1); /*else*/ /*else*/ while(finish=0); /*main*/ 【运行结果 】 11
