实验3LL1文法构造

1、实验报告实验课程：编译原理学生姓名：学 号：专业班级：计科实验 3 LL( 1)文法构造一、实验目的熟悉LL (1 )文法的分析条件，了解 LL (1)文法的构造方法。二、实验内容1 、编制一个能够将一个非 LL( 1 )文法转换为 LL( 1 )文法；2、消除左递归；3、消除回溯。三、实验要求1、 将一个可转换非 LL (1)文法转换为LL (1)文法，要经过两个阶段，1)消除文法 左递归， 2)提取左因子，消除回溯。2、提取文法左因子算法：1) 对文法G的所有非终结符进行排序2) 按上述顺序对每一个非终结符Pi 依次执行 :for( j=1 ； j Pi a | 3 ，其中B不以Pi开头，

2、则修改产生式为：Pi 3 Pi Pi a Pi I &3) 化简上述所得文法。3、提取左因子的算法：A SB 11 S3 2l I SB nl Y 1l Y 2l I 丫 m(其中，每个丫不以S开头)那么 , 可以把这些产生式改写成A S A 1 Y 11 Y 21 Y mA 3 1l 3 2l I 3n4、利用上述算法，实现构造一个 LL( 1 )文法：1 ) 从文本文件 g.txt 中读入文法，利用实验 1 的结果，存入实验 1 设计的数据结 构；2) 设计函数 remove_left_recursion ()和 remove_left_gene ()实现消除左递归和 提取左因子算法，分别

3、对文法进行操作，消除文法中的左递归和提出左因子；3) 整理得到的新文法；4) 在一个新的文本文件 newg.txt 输出文法，文法输出按照一个非终结符号一行，开始符号引出的产生式写在第一行，同一个非终结符号的候选式用“l”分隔的方式输出。四、实验环境PC微机DOS操作系统或 Windows操作系统Turbo C程序集成环境或 Visual C+程序集成环境五、实验步骤1、学习LL (1)文法的分析条件；2、学习构造LL( 1)文法的算法；3、 结合实验1给出的数据结构，编程实现构造LL( 1)文法的算法；4、 结合实验1编程和调试实现对一个具体文法运用上述算法，构造它的LL( 1)文法 形式；

4、5、把实验结果写入一个新建立的文本文件。六、测试数据输入数据：编辑一个文本文文件 g.txt，在文件中输入如下内容：SQc|c|cab;Q-Rb|b;R-Sa|a;正确结果：本实验的输出结果是不唯一的，根据消除左递归是选择非终结符号的顺序不同，或选择新的非终结符号的不同，可能会得到不同的结果，下面只是可能的一个结果：S-Qc|cT;T-|ab;/由于无法输出，用 代替Q-Rb|b;R-bcaU|caU|cabaU|aU;U-bcaU|;七、实验报告要求实验报告应包括以下几个部分：1、满足LL (1)文法的分析条件；2、构造LL (1)文法的算法；3、消除左递归文法和提取左因子算法实现方法;4、

5、整个测试程序的流程；5、程序的测试结果和问题；6、实验总结。代码#in clude#in cludeusing n amespace std;typedef struct Chomsky /定义一个产生式结构体string left; /定义产生式的左部string right; II定义产生式的右部Chomsky;int n;II产生式总数string strings;存储产生式char q20;void apart(Chomsky *p,int i) II分开产生式左右部 i代表产生式的编号int j;for(j=0;jstri ngs.len gth();j+)if(stringsj=

6、_)pi.left=strings.substr(Oj);/ 从 0 开始的 j 长度的子串即 0j-1pi.right=strings.substr(j+1,strings.length() -j);II 从 j+1 开始的后面子串 int zero(Chomsky *p)II0 型文法int flag(0),cou nt(0);int i,j;for(i=0;i n;i+)for(j=0;j=A&pi.leftj0)/说明某一个产生式左部有非终结符flag=0;/下个产生式判断前清零count+;/左部存在非终结符的产生式个数加1elsebreak; /左部没有非终结符结束if(co un

7、t=n)return 1; /属于0型文法elsecoutendl所输产生式不属于任何文法。endl;return 0;int on e(Chomsky *p)/1 型文法int flag(0);int i;if(zero(p)for(i=0;i n; i+)if(pi.right.le ngth()0)coutendl此文法属于0型文法 即短语文法。endl; return 0;/不属于1型文法elseif(flag=0)return 1; /属于1型文法elsereturn 0;int two(Chomsky *p)/2 型文法int flag(0);int i;if(o ne(p)for

8、(i=0;i =A&pi.leftO0)coutendl此文法属于1型文法即上下文有关文法。endl; return 0;/不属于2型文法elseif(flag=0)return 1; /属于2型文法elsereturn 0;int remove(Chomsky *p,int n) 消除左递归/把文法的所有非终结符按某一顺序排序int i,j,co un t=1,co un t1= n, flag=0,m,x; qO=pOeftO;for(i=1;in;i+)for(j=0;ji;j+)if(pi.left=pj.left)break;if(j=i)qcount+=pi.left0;count

9、 -;for(i=0;in;i+)/ 判断第一个非终结符是否存在直接左递归if(pi.left0=q0&pi.left0=pi.right0)flag+;if(flag!=0)/ 消除第一个非终结符的直接左递归for(i=0;in;i+)if(pi.left0=q0)if(pi.left0=pi.right0)pi.left=pi.left+;pi.right=pi.right.substr(1,pi.right.length()+pi.left;elsepi.right=pi.right+pi.left+;pcount1.left=p0.left;pcount1+.right=#;/ 用 #

10、代替空产生式/ 消一切左递归for(m=0;m=count;m+)for(i=0;in;i+)if(pi.left0=qm)for(j=0;jcount1;j+) for(x=m+1;x=count;x+)if(pj.left0=qx&pj.right0=qm)pcount1.left=pj.left;pcount1.right=pi.right+pj.right.substr(1,pj.right.length();count1=count1+1;for(j=0;jcount1;j+)for(x=m+1;x=count;x+)if(pj.right0=qm&pj.left0=qx)pj.ri

11、ght=;pj.left=;for(x=0,flag=0;xcount1;x+)/ 判断第 m 个非终结符是否存在直接左递归if(px.left0=qm&px.left0=px.right0)flag+;/ 消直接左递归if(flag!=0)for(i=0;icount1;i+)if(pi.left0=qm)if(pi.left0=pi.right0)pi.left=pi.left+;pi.right=pi.right.substr(1,pi.right.le ngth()+pi.left;pcou nt1.left=pi.left;pcount1.right=#; 用#代替空产生式elsep

12、i.right=pi.right+pi.left+;coun t1=co un t1+1;count1 -;return coun t1;void mai n()int i,j,co un t1;空用#表cout编译原理实验非LL文法到LL(1)文法的转换endl;cout请输入产生式总数及各产生式e ndl其中左右部之间用-表示示e ndl;cinn;Chomsky *p=new Chomsky50; / 初始化产生式数组for(i=0;i stri ngs;apart(p,i);if(two(p)cout该文法属于二型文法实验继续.vvendl;coun t1=remove(p ,n);coutvv转换后的文法输出如下e ndl;for(i=0;i=co un t1;i+)if(pi.leftO!=NULL)cout卩口血6ndl;elsecout该文法不是2型文法 无需进行LL(1)的转换实验结束endl