编译原理实验报告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）文法的分析条件；转换前要求文法中不含回路（经过推导有形如P-P之类的），也不含以ε为右部的产生式。一个文法要能进行LL（1）分析，那么这个文法应该满足：无二义性，无左递归，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|@;无左公因子。首先需要定义一些规则：1.在程序运行前文法就必须输入进文本文件中，输入的文法只包含其中的所有产生式，并且默认其为可转换的非LL（1）文法，即通过消除左递归和反复提取公共左因子，就转换成了LL（1）文法。2.输入的产生式为原实验1的结果，即一个非终结符只有一条产生式，候选之间用“|”隔开。3.产生式与产生式之间只能以换行符或分号隔开。4.开始符号对应的产生式必须第一个输入，即默认输入的第一个产生式的左部的大写字母是开始符号。5.输入与输出都会保存在文本文件中文件名分别是g.txt和newg.txt，本实验测试数据时，将两个文本放在了桌面。6.ε用@代替，输入与输出都使用@。7.新产生的非终结符统一使用没有在非终结符集合中出现的大写字母。8.规定产生式最多只有20个。2、构造LL（1）文法的算法；算法：1)从文本文件g.txt中读入文法，存入结构体中。将第一个读到的大写字母记为开始符号S，将读到的包括开始符号在内的所有大写字母判定为非终结符，并将第一次出现的存入文法的非终结符集合中，终结符小写字母也一样。将以换行符或分号隔开的字符串判断为一条产生式存入文法中。实现函数是scanP()。2)对文法中的产生式消除左递归。实现函数是remove_left_recursion()。3)对文法中的产生式反复提取公共左因子。实现函数是remove_left_gene()。4)向newg.txt中输出文法的所有产生式。3、消除左递归文法和提取左因子算法实现方法；消除左递归文法（包括其中用到其它的子函数）：/*字符串分割函数，将产生式右部的候选返回,识别‘|’，从pos位开始分割*/stringstrsplit(stringstrTok,intpos){stringstr;size_tposition;position=strTok.find(|,pos);if(position!=string::npos){//找到了‘|’str=strTok.substr(pos,position-pos);}else{//没找到str=strTok.substr(pos,strTok.size()-pos);}returnstr;}/*获得一个文法中尚未定义的非终结符，即特定的大写字母*/charGetWord(char*p){charch,word[]={'A','B','C','D','E','F','G','H','I','J','K','L','M','N','O','P','Q','R','S','T','U','V','W','X','Y','Z'};intw,x;for(w=0;w26;w++){ch=word[w];for(x=0;xm;x++){if(ch==p[x]){break;}}if(x==m)break;}returnch;}/*判断非终结符是否已存在*/boolcheckWord(charch,stringVn){inti;boolflag=true;for(i=0;iVn.size();i++){if(ch==Vn[i])flag=false;}returnflag;}/*化简无用产生式*/voidsimplify(structgrammar*gp){stringstr;//存储从开始符号可以到达的非终结符的序列intsVn[20];//标记在哪个产生式sVn[0]=0;str.insert(0,1,gp-Vn[0]);//初始化设置开始符号boolflag[20];flag[0]=false;//标记哪个产生式需要删除charch;inti,j,k,l,o;for(i=0;istr.size();i++){for(j=3;jgp-P[sVn[i]].size();j++){for(k=0;km;k++){if(gp-P[sVn[i]][j]'A'||gp-P[sVn[i]][j]'Z')break;//不是非终结符无需判断if(gp-P[sVn[i]][j]==gp-Vn[k]){//判断从开始符号可以到达的非终结符在Vn的哪个位置flag[k]=false;if(checkWord(gp-Vn[k],str)){//将在str中没有的有用非终结符插入strinte=str.size();sVn[e]=k;str.insert(str.size(),1,gp-Vn[k]);}break;}}}}for(l=0;lm;l++){//删除无用的产生式和相应的非终结符charch;if(flag[l]){gp-Vn[l]='';for(o=l+1;om;o++){ch=gp-Vn[o-1];gp-Vn[o-1]=gp-Vn[o];gp-Vn[o]=ch;gp-P[o-1].clear();gp-P[o-1].swap(gp-P[o]);}m--;}}}voidremove_left_recursion(structgrammar*gp){//子函数，消除文法左递归inti,j,num_i,num_j,ipos,jpos;charch_i,ch_j;for(i=1;im+1;i++){boolrepeat=true;//标记相对于本轮循环上轮过程产生式是否有过变化，有则需要重新分割得到候选num_i=0,ipos=3;stringstr_i[20],restr_i[20],ex=a;ch_i=gp-Vn[i-1];//获取当前要被处理的非终结符，即Pi//分割产生式，得到右部的所有候选while(ipos!=gp-P[i-1].size()+1){str_i[num_i]=strsplit(gp-P[i-1],ipos);restr_i[num_i]=str_i[num_i];ipos=ipos+str_i[num_i].size()+1;num_i++;}for(j=1;j=i-1;j++){if(!repeat){num_i=0,ipos=3;ch_i=gp-Vn[i-1];//重新获取当前要被处理的非终结符，即Pi//分割产生式，得到右部的所有候选while(ipos!=gp-P[i-1].size()+1){str_i[num_i]=strsplit(gp-P[i-1],ipos);restr_i[num_i]=str_i[num_i];ipos=ipos+str_i[num_i].size()+1;num_i++;}}repeat=true;stringstr_j[20];intl;jpos=3;num_j=0;ch_j=gp-Vn[j-1];//获取当前要替换的非终结符，即Pj//分割产生式，得到右部的所有候选while(jpos!=gp-P[j-1].size()+1){str_j[num_j]=strsplit(gp-P[j-1],jpos);jpos=jpos+str_j[num_j].size()+1;num_j++;}for(l=0;lnum_i;l++){//逐个判断Pi的候选中是否含有Pj,有则进行替换stringchange;ex[0]=ch_j;size_tpos=restr_i[l].find(ex);if(pos==string::npos){continue;}//无需替换elseif(pos==0){//Pj在该候选的第一个字符repeat=false;//strings=str_i[l].substr(1,str_i[l].size()-1);//得到候选中除Pj外的剩余部分str_i[l].swap(change);//清空字符串intlink=0;while(1){//将Pj的所有候选与Pi中匹配的候选的剩余部分连接，中间还添加“|”if(link==num_j)break;str_j[link]+=s;if(link==num_j-1)str_i[l]+=str_j[link];elsestr_i[l]=str_i[l]+str_j[link]+|;link++;}}elseif(pos==str_i[l].size()-1){//Pj在该候选的最后一个字符repeat=false;//strings=str_i[l].substr(0,str_i[l].size()-1);str_i[l].swap(change);intlink=0;while(1){if(link==num_j)break;str_j[link]=s+str_j[link];if(link==num_j-1)str_i[l]+=str_j[link];elsestr_i[l]=str_i[l]+str_j[link]+|;link++;}}else{//Pj在该候选的中间repeat=false;//strings1=str_i[l].substr(0,pos-1);//得到该候选中Pj前的字符串strings2=str_i[l].substr(pos+1,str_i[l].size()-pos-1);//得到该候选中Pj后的字符串str_i[l].swap(change);intlink