实验3：LL(1)文法构造

实验报告实验课程：编译原理学生姓名：学号：专业班级：计科实验3LL（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；ji-1；j++)将Pj代入Pi的产生式（若可代入的话）；消除关于Pi的直接左递归：Pi-Piα|β，其中β不以Pi开头，则修改产生式为：Pi—＞βPi′Pi′—＞αPi′|ε3）化简上述所得文法。3、提取左因子的算法：A—＞δβ1|δβ2|…|δβn|γ1|γ2|…|γm(其中,每个γ不以δ开头)那么,可以把这些产生式改写成A—＞δA′|γ1|γ2…|γmA′—＞β1|β2|…|βn4、利用上述算法，实现构造一个LL（1）文法：1）从文本文件g.txt中读入文法，利用实验1的结果，存入实验1设计的数据结构；2）设计函数remove_left_recursion（）和remove_left_gene（）实现消除左递归和提取左因子算法，分别对文法进行操作，消除文法中的左递归和提出左因子；3）整理得到的新文法；4）在一个新的文本文件newg.txt输出文法，文法输出按照一个非终结符号一行，开始符号引出的产生式写在第一行，同一个非终结符号的候选式用“|”分隔的方式输出。四、实验环境PC微机DOS操作系统或Windows操作系统TurboC程序集成环境或VisualC++程序集成环境五、实验步骤1、学习LL（1）文法的分析条件；2、学习构造LL（1）文法的算法；3、结合实验1给出的数据结构，编程实现构造LL（1）文法的算法；4、结合实验1编程和调试实现对一个具体文法运用上述算法，构造它的LL（1）文法形式；5、把实验结果写入一个新建立的文本文件。六、测试数据输入数据：编辑一个文本文文件g.txt，在文件中输入如下内容：正确结果：本实验的输出结果是不唯一的，根据消除左递归是选择非终结符号的顺序不同，或选择新的非终结符号的不同，可能会得到不同的结果，下面只是可能的一个结果：七、实验报告要求实验报告应包括以下几个部分：1、满足LL（1）文法的分析条件；2、构造LL（1）文法的算法；3、消除左递归文法和提取左因子算法实现方法；4、整个测试程序的流程；5、程序的测试结果和问题；6、实验总结。S-Qc|c|cab;Q-Rb|b;R-Sa|a;S-Qc|cT;T-@|ab;//由于无法输出ε，用@代替Q-Rb|b;R-bcaU|caU|cabaU|aU;U-bcaU|@;代码#includeiostream#includestringusingnamespacestd;typedefstructChomsky//定义一个产生式结构体{stringleft;//定义产生式的左部stringright;//定义产生式的右部}Chomsky;intn;//产生式总数stringstrings;//存储产生式charq[20];voidapart(Chomsky*p,inti)//i代表产生式的编号{intj;for(j=0;jstrings.length();j++)if(strings[j]=='-'){p[i].left=strings.substr(0,j);//从0开始的j0~j-1p[i].right=strings.substr(j+1,strings.length()-j);//从j+1开始的后面子串}}intzero(Chomsky*p)//0型文法{intflag(0),count(0);inti,j;for(i=0;in;i++){for(j=0;j(int)p[i].left.length();j++){if(p[i].left[j]='A'&&p[i].left[j]='Z')//有否非终结符flag++;//非终结符个数加1}if(flag0)//说明某一个产生式左部有非终结符{flag=0;//下个产生式判断前清零count++;//左部存在非终结符的产生式个数加1}elsebreak;//}if(count==n)return1;//属于0型文法else{coutendl所输产生式不属于任何文法。endl;return0;}}intone(Chomsky*p)//1型文法{intflag(0);inti;if(zero(p)){for(i=0;in;i++){if(p[i].right.length()p[i].left.length())//1型{flag++;break;}}}else//即不是0型文法flag--;//flag=-1if(flag0){coutendl此文法属于0endl;return0;//不属于1型文法}elseif(flag==0)return1;//属于1型文法elsereturn0;}inttwo(Chomsky*p)//2型文法{intflag(0);inti;if(one(p)){for(i=0;in;i++)if((p[i].left.length()!=1)||!(p[i].left[0]='A'&&p[i].left[0]='Z'))//左部不属于一个字符或不属于非终结符{flag++;//则不为2型break;}}else//不为1flag=-1flag--;if(flag0){coutendl此文法属于1endl;return0;//不属于2型文法}elseif(flag==0){return1;//属于2型文法}elsereturn0;}intremove(Chomsky*p,intn)//消除左递归{//把文法的所有非终结符按某一顺序排序inti,j,count=1,count1=n,flag=0,m,x;q[0]=p[0].left[0];for(i=1;in;i++){for(j=0;ji;j++){if(p[i].left==p[j].left)break;}if(j==i)q[count++]=p[i].left[0];}count--;for(i=0;in;i++)//判断第一个非终结符是否存在直接左递归if(p[i].left[0]==q[0]&&p[i].left[0]==p[i].right[0])flag++;if(flag!=0)//消除第一个非终结符的直接左递归{for(i=0;in;i++){if(p[i].left[0]==q[0]){if(p[i].left[0]==p[i].right[0]){p[i].left=p[i].left+';p[i].right=p[i].right.substr(1,p[i].right.length())+p[i].left;}elsep[i].right=p[i].right+p[i].left+';}}p[count1].left=p[0].left;p[count1++].right=#;//用#代替空产生式}//消一切左递归for(m=0;m=count;m++){for(i=0;in;i++){if(p[i].left[0]==q[m]){for(j=0;jcount1;j++){for(x=m+1;x=count;x++)if(p[j].left[0]==q[x]&&p[j].right[0]==q[m]){p[count1].left=p[j].left;p[count1].right=p[i].right+p[j].right.substr(1,p[j].right.length());count1=count1+1;}}}}for(j=0;jcount1;j++){for(x=m+1;x=count;x++)if(p[j].right[0]==q[m]&&p[j].left[0]==q[x]){p[j].right=;p[j].left=;}}for(x=0,flag=0;xcount1;x++)//判断第m个非终结符是否存在直接左递归if(p[x].left[0]==q[m]&&p[x].left[0]==p[x].right[0])flag++;//消直接左递归if(flag!=0){for(i=0;icount1;i++){if(p[i].left[0]==q[m]){if(p[i].left[0]==p[i].right[0]){p[i].left=p[i].left+';p[i].right=p[i].right.substr(1,p[i].right.length())+p[i].left;p[count1].left=p[i].left;p[count1].right=#;//用#代替空产生式}elsep[i].right=p[i].right+p[i].left+';}}count1=count1+1;}}count1--;returncount1;}voidmain(){inti,j,count1;cout...............LL(1)文法到LL(1)文法的转换................endl;coutendl其中左右部之间用'-''#'表示endl;cinn;Chomsky*p=newChomsky[50];//初始化产生式数组for(i=0;in;i++){cinstrings;apart(p,i);}if(two(p)){cout...endl;count1=remove(p,n);coutendl;for(i=0;i=count1;i++){if(p[i].left[0]!=NULL)coutp[i].left-p[i].rightendl;}}elsecout该文法不是2LL(1)endl;system(pause);}八、思考题1、是不是所有的文法都可以通过上述程序构造LL（1）文法？2、LL（1）文法在整个语法分析中的作用？3、实验1中设计的文法数据结构对本实验的影响？4、如何更好地组合实验1和实验3，使之具有更高的效率？