将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
升级会员 