将Pj代入Pi的产生式(若可代入的话);
消除关于Pi的直接左递归:
Pi->Piα|β,其中β不以Pi开头,则修改产生式为:
Pi—>βPi′
Pi′—>αPi′|ε
3)化简上述所得文法。
3、提取左因子的算法:
A—>δβ1|δβ2|…|δβn|γ1|γ2|…|γm
(其中,每个γ不以δ开头)
那么,可以把这些产生式改写成
A—>δA′|γ1|γ2…|γm
A′—>β1|β2|…|βn
4、利用上述算法,实现构造一个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,在文件中输入如下内容:
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)文法的分析条件;
转换前要求文法中不含回路(经过推导有形如P->P之类的),也不含以ε为右部的产生式。
一个文法要能进行LL
(1)分析,那么这个文法应该满足:
无二义性,无左递归,无左公因子。
首先需要定义一些规则:
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;w<26;w++){
ch=word[w];
for(x=0;xif(ch==p[x]){
break;
}
}
if(x==m)break;
}
returnch;
}
/*判断非终结符是否已存在*/
boolcheckWord(charch,stringVn){
inti;
boolflag=true;
for(i=0;iif(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;ifor(j=3;jP[sVn[i]].size();j++){
for(k=0;kif(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中没有的有用非终结符插入str
inte=str.size();
sVn[e]=k;
str.insert(str.size(),1,gp->Vn[k]);
}
break;
}
}
}
}
for(l=0;lcharch;
if(flag[l]){
gp->Vn[l]='';
for(o=l+1;och=gp->Vn[o-1];
gp->Vn[o-1]=gp->Vn[o];
gp->Vn[o]=ch;
gp->P[o-1].clear();
gp->P[o-1].s>P[o]);
}
m--;
}
}
}
voidremove_left_recursion(structgrammar*gp){//子函数,消除文法左递归
inti,j,num_i,num_j,ipos,jpos;
charch_i,ch_j;
for(i=1;iboolrepeat=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;lstringchange;
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].s);//清空字符串
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].s);
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].s);
intlink=0;
while
(1){
if(link==num_j)break;
str_j[link]=s1+str_j[link]+s2;
if(link==num_j-1)str_i[l]+=str_j[link];
elsestr_i[l]=str_i[l]+str_j[link]+"|";
link++;
}
}
}
stringstri="->";
stri.insert(0,1,ch_i);
intindex=0;
while
(1){//将替换后的Pi的所有候选进行重组并存进文法中
if(index==num_i)break;
if(index==num_i-1)stri=stri+str_i[index];
elsestri=stri+str_i[index]+"|";
index++;
}
gp->P[i-1]=stri;
}
//消除直接左递归
stringsplitstr[30],resplitstr[30];
ints=0,ps=3,h=0;
while
(1){//分割替换后的产生式
splitstr[s]=strsplit(gp->P[i-1],ps);
resplitstr[s]=splitstr[s];
ps=ps+splitstr[s].size()+1;
if(ps==gp->P[i-1].size()+1)break;
s++;
}
stringPi="->",Pichange="->";
Pi=ch_i+Pi;
intlink=0,flag=-1;
boolflagpos[30];
charnewWord;
for(;link<=s;link++){//遍历所有候选,校验其中是否有左递归
size_tposi;
posi=resplitstr[link].find(ch_i);
if(posi==0){//存在直接左递归
flag++;//对候选标记左递归
if(flag==0){//处理出现左递归的第一个候选
newWord=GetWord(gp->Vn);//获取一个新的非终结符
gp->Vn[m]=newWord;
Pichange=newWord+Pichange;
m++;
splitstr[link]=splitstr[link].substr
(1)+newWord;
flagpos[link]=false;
gp->P[m-1]=Pichange+splitstr[link]+"|";
}
if(flag>0){
splitstr[link]=splitstr[link].substr
(1)+newWord;
flagpos[link]=false;
gp->P[m-1]=gp->P[m-1]+splitstr[link]+"|";
}
}
}
//对消除了直接左递归的候选进行重组成为产生式并存入文法
if(flag>-1){
gp->P[i-1]="->";
gp->P[i-1].insert(0,1,ch_i);
for(;h<=s;h++){
if(flagpos[h]){
splitstr[h]+=newWord;
gp->P[i-1]=gp->P[i-1]+splitstr[h]+"|";
}
}
gp->P[m-1]+="@";
gp->P[i-1].erase(gp->P[i-1].size()-1,1);
}
}
simplify(gp);//化简无用的产生式
}
提取左因子(包括辅助函数):
//对字符串数组排序
voidstr_sort(string*str,intnum){
inti,j;
for(i=0;ifor(j=i+1;jif(str[i]>str[j])
str[i].s[j]);
}
}
}
/*子函数,提取左因子*/
voidremove_left_gene(structgrammar*gp){
intrule_a,i,j,k,l,matchnum,oldmatchnum,resize,size;
charch,newWord;
for(rule_a=0;rule_aintbre=-1;//标记已对产生式进行过左因子的提取
intoldpo=0;
intnum=0,ps=3;
stringstr[30],restr[30];//前者用于判断,需要保持原样,后者用于对有公共左因子的候选进行提取,可变
while(ps!
=gp->P[rule_a].size()+1){//分割替换后的产生式
str[num]=strsplit(gp->P[rule_a],ps);
restr[num]=str[num];
ps=ps+str[num].size()+1;
num++;
}
str_sort(str,num);//对所有候选按ASCII码进行排序,以便于简化对公共左因子的判断,只需先对前面候选判断
str_sort(restr,num);
intca_i;
stringPa="->";
Pa.insert(0,1,gp->Vn[rule_a]);
for(ca_i=0;ca_iif(ca_i==num-1)
Pa+=str[ca_i];
else
Pa+=str[ca_i]+"|";
}
gp->P[rule_a]=Pa;
intipo=0;//辅助免除对已判断过有左因子的候选的遍历
for(i=0;iipo=0;
size=0;
resize=0;
oldmatchnum=0;
inti_s=str[i].size();
for(j=0;jmatchnum=0;//标记除了本身,有几个候选有公共左因子
ch=str[i][j];
intkf=num;
for(k=i+1;k