文档介绍：该【编译原理实验报告《LL语法分析器构造》(文档) 】是由【夏天教育】上传分享，文档一共【15】页，该文档可以免费在线阅读，需要了解更多关于【编译原理实验报告《LL语法分析器构造》(文档) 】的内容，可以使用淘豆网的站内搜索功能，选择自己适合的文档，以下文字是截取该文章内的部分文字，如需要获得完整电子版，请下载此文档到您的设备，方便您编辑和打印。《LL（1）分析器的结构》实验报告
一、实验名称
LL(1)分析器的结构
二、实验目的
设计、编制、调试一个LL(1)语法分析器，利用语法分析器对符号串的鉴识，加深对语法分析原理的理解。
三、实验内容和要求
设计并实现一个LL(1)语法分析器，实现对算术文法:
G[E]:E->E+T|T
T->T*F|F
F->(E)|i
所定义的符号串进行鉴识，比方符号串i+i*i为文法所定义的句子，符号串ii+++*i+不是文法所定义的句子。
实验要求:
、检测左递归，假如有则进行除去；
、求解FIRST集和FOLLOW集；
、建立LL(1)分析表；
、建立LL分析程序，关于用户输入的句子，可以利用所结构的分析程序进行分析，并显示出分析过程。
四、主要仪器设施
硬件：微型计算机。
软件：Codeblocks（也可以是其余集成开发环境）。
五、实验过程描绘
1、程序主要框架
程序中编写了以下函数，各个函数实现的作用以下：
voidinput_grammer(string*G);//输入文法G
voidpreprocess(string*G,string*P,string&U,string&u,int&n,int&t,int&k);
1
//将文法G预办理获取产生式会合P，非终结符、终结符会合U、u，
inteliminate_1(string*G,string*P,stringU,string*GG);//除去文法G中全部直接左递归获取文法GGint*ifempty(string*P,stringU,intk,intn);//判断各非终结符能否能推导为空
string*FIRST_X(string*P,stringU,stringu,int*empty,intk,intn)；求全部非终结符的FIRST集stringFIRST(stringU,stringu,string*first,strings)；//求符号串s=X1X2...Xn的FIRST集string**create_table(string*P,stringU,stringu,intn,intt,intk,string*first)；//结构分析表
voidanalyse(string**table,stringU,stringu,intt,strings)；//分析符号串s
2、编写的源程序
#include<cstdio>
#include<cstring>
#include<iostream>
usingnamespacestd;
voidinput_grammer(string*G)//输入文法G,n个非终结符
{
inti=0;//计数
charch='y';
while(ch=='y'){
cin>>G[i++];
cout<<"连续输入?(y/n)\n";
cin>>ch;
}
}
voidpreprocess(string*G,string*P,string&U,string&u,int&n,int&t,int&k)//将文法G预办理产生式会合P，
非终结符、终结符会合U、u，
{
inti,j,r,temp;//计数
charC;//记录规则中（）后的符号
intflag;//检测到（）
n=t=k=0;
for(i=0;i<50;i++)P[i]="";//字符串假如不初始化，在使用P[i][j]=a时将不可以改变，可以
用P[i].append(1,a)
U=u="";//字符串假如不初始化，没法使用U[i]=a赋值，(1,a)
for(n=0;!G[n].empty( );n++)
{U[n]=G[n][0];
}//非终结符会合，n为非终结符个数
for(i=0;i<n;i++)
{
for(j=4;j<G[i].length( );j++)
{
if((G[i][j])==string::npos&&(G[i][j])==string::npos)
if(G[i][j]!='|'&&G[i][j]!='^')
//if(G[i][j]!='('&&G[i][j]!=')'&&G[i][j]!='|'&&G[i][j]!='^')
u[t++]=G[i][j];
2
}
}//终结符会合，t为终结符个数
for(i=0;i<n;i++)
{
flag=0;r=4;
for(j=4;j<G[i].length( );j++)
{
P[k][0]=U[i];P[k][1]=':';P[k][2]=':';P[k][3]='=';
/*if(G[i][j]=='(')
{j++;flag=1;for(temp=j;G[i][temp]!=')';temp++);
C=G[i][temp+1];
//C记录（）后跟的字符，将C增添到（）中全部字符串后边
}
if(G[i][j]==')'){j++;flag=0;}
*/
if(G[i][j]=='|')
{
//if(flag==1)P[k][r++]=C;
k++;j++;
P[k][0]=U[i];P[k][1]=':';P[k][2]=':';P[k][3]='=';
r=4;
P[k][r++]=G[i][j];
}
else
{
P[k][r++]=G[i][j];
}
}
k++;
}//获取产生式会合P，k为产生式个数
}
inteliminate_1(string*G,string*P,stringU,string*GG)
//除去文法G1中全部直接左递归获取文法G2，要可以除去含有多个左递归的状况）
{
stringarfa,beta;//全部形如A::=Aα|中β的α、β连结起来形成的字符串arfa、beta
inti,j,temp,m=0;//计数
intflag=0;//flag=1表示文法有左递归
intflagg=0;//flagg=1表示某条规则有左递归
charC='A';//因为除去左递归新增的非终结符，从A开始增添，只需不在本来问法的非终结符中即可加
3
入
for(i=0;i<20&&U[i]!='';i++)
{flagg=0;arfa=beta="";for(j=0;j<100&&P[j][0]!='';j++)
{
if(P[j][0]==U[i])
{
if(P[j][4]==U[i])//产生式j有左递归
{
flagg=1;
for(temp=5;P[j][temp]!='';temp++)(1,P[j][temp]);if(P[j+1][4]==U[i])("|");//不单一个产生式含有左递归
}
else
{
for(temp=4;P[j][temp]!='';temp++)(1,P[j][temp]);
if(P[j+1][0]==U[i]&&P[j+1][4]!=U[i])("|");
}
}
}
if(flagg==0)//关于不含左递归的文法例则不重写
{GG[m]=G[i];m++;}
else
{
flag=1;//文法存在左递归
GG[m].append(1,U[i]);GG[m].append("::=");
if(('|')!=string::npos)GG[m].append("("+beta+")");
elseGG[m].append(beta);
while((C)!=string::npos){C++;}
GG[m].append(1,C);
m++;
GG[m].append(1,C);GG[m].append("::=");
if(('|')!=string::npos)GG[m].append("("+arfa+")");
elseGG[m].append(arfa);
GG[m].append(1,C);GG[m].append("|^");
m++;
C++;
}//A::=Aα改|β写成A::=βA‘，A’=αA'|β，
}
returnflag;
}
int*ifempty(string*P,stringU,intk,intn)
{
4
int*empty=newint[n];//指示非终结符能否推导到空串
inti,j,r;
for(r=0;r<n;r++)empty[r]=0;//默认全部非终结符都不可以推导到空
intflag=1;//1
表示empty数组有改正
intstep=100;//
假定一条规则最大推导步数为
100步
while(step--)
{
for(i=0;i<k;i++)
{
r=(P[i][0]);
if(P[i][4]=='^')empty[r]=1;//直接推导到空
else
{
for(j=4;P[i][j]!='';j++)
{
if((P[i][j])!=string::npos)
{
if(empty[(P[i][j])]==0)break;
}
elsebreak;
}
if(P[i][j]=='')empty[r]=1;//多步推导到空
elseflag=0;
}
}
}
returnempty;
}
string*FIRST_X(string*P,stringU,stringu,int*empty,intk,intn)
{
inti,j,r,s,tmp;
string*first=newstring[n];
chara;
intstep=100;//最大推导步数
while(step--){
cout<<"step"<<100-step<<endl;for(i=0;i<k;i++)
{
//cout<<P[i]<<endl;
r=(P[i][0]);
5
if(P[i][4]=='^'&&first[r].find('^')==string::npos)first[r].append(1,'^');//规则右部首符号为空
else
{
for(j=4;P[i][j]!='';j++)
{
a=P[i][j];
if((a)!=string::npos&&first[r].find(a)==string::npos)//规则右部首符号是终结符
{
first[r].append(1,a);
break;//增添并结束
}
if((P[i][j])!=string::npos)//规则右部首符号是非终结符,形如X：：=Y1Y2...Yk{
s=(P[i][j]);
//cout<<P[i][j]<<":\n";
for(tmp=0;first[s][tmp]!='\0';tmp++)
{
a=first[s][tmp];
if(a!='^'&&first[r].find(a)==string::npos)//将FIRST[Y1]中的非空符加入
first[r].append(1,a);
}
}
if(!empty[s])break;//若Y1不可以推导到空，结束
}
if(P[i][j]=='')
if(first[r].find('^')==string::npos)
first[r].append(1,'^');//若Y1、Y2...Yk都能推导到空，则加入空符号
}
}
}
returnfirst;
}
stringFIRST(stringU,stringu,string*first,strings)//求符号串s=X1X2...Xn的FIRST集
{
inti,j,r;
chara;
stringfir;
for(i=0;i<( );i++)
{
if(s[i]=='^')(1,'^');
if((s[i])!=string::npos&&(s[i])==string::npos){(1,s[i]);break;}//X1是终结符，添
6
加并结束循环
if((s[i])!=string::npos)//X1是非终结符
{
r=(s[i]);
for(j=0;first[r][j]!='\0';j++)
{
a=first[r][j];
if(a!='^'&&(a)==string::npos)//将FIRST(X1)中的非空符号加入
(1,a);
}
if(first[r].find('^')==string::npos)break;//若X1不可以推导到空，循环停止
}
if(i==( ))//若X1-Xk都可推导到空
if((s[i])==string::npos)//fir中还未加入空符号
(1,'^');
}
returnfir;
}
string**create_table(string*P,stringU,stringu,intn,intt,intk,string*first)//结构分析表，P为文法G的产生式
组成的会合
{
inti,j,p,q;
stringarfa;//记录规则右部
stringfir,follow;
stringFOLLOW[5]={")#",")#","+)#","+)#","+*)#"};
string**table=newstring*[n];
for(i=0;i<n;i++)table[i]=newstring[t+1];
for(i=0;i<n;i++)
for(j=0;j<t+1;j++)
table[i][j]="";//table储蓄分析表的元素，“”表示error
for(i=0;i<k;i++)
{
arfa=P[i];
(0,4);//删除前4个字符，如：E::=E+T,则arfa="E+T"
fir=FIRST(U,u,first,arfa);
for(j=0;j<t;j++)
{
p=(P[i][0]);
if((u[j])!=string::npos)
{
q=j;
table[p][q]=P[i];
}//对first（）中的每一终结符置相应的规则
7
}
if(('^')!=string::npos)
{
follow=FOLLOW[p];//对规则左部求follow( )
for(j=0;j<t;j++)
{
if((q=(u[j]))!=string::npos)
{
q=j;
table[p][q]=P[i];
}//对follow（）中的每一终结符置相应的规则
}
table[p][t]=P[i];//对#所在元素置相应规则
}
}
returntable;
}
voidanalyse(string**table,stringU,stringu,intt,strings)//分析符号串s
{
stringstack;//分析栈
stringss=s;//记录原符号串
charx;//栈顶符号
chara;//下一个要输入的字符
intflag=0;//般配成功标记
inti=0,j=0,step=1;//符号栈计数、输入串计数、步骤数
intp,q,r;
stringtemp;
for(i=0;!s[i];i++)
{
if((s[i])==string::npos)//出现非法的符号
cout<<s<<"不是该文法的句子\n";
return;
}
(1,'#');
(1,'#');//’#’进入分析栈
(1,U[0]);i++;//文法开始符进入分析栈
a=s[0];
//cout<<stack<<endl;
cout<<"步骤分析栈余留输入串所用产生式\n";
while(!flag)
{
//cout<<"步骤分析栈余留输入串所用产生式\n"
cout<<step<<""<<stack<<""<<s<<"";
8
x=stack[i];(i,1);i--;//取栈顶符号x,并从栈顶退出
//cout<<x<<endl;
if((x)!=string::npos)//x是终结符的状况
{
if(x==a)
{
(0,1);a=s[0];//栈顶符号与目前输入符号般配，则输入下一个符号
cout<<"\n";//未使用产生式，输出空
}
else
{
cout<<"error\n";
cout<<ss<<"不是该文法的句子\n";
break;
}
}
if(x=='#')
{
if(a=='#'){flag=1;cout<<"成功\n";}//栈顶和余留输入串都为#，般配成功
else
{
cout<<"error\n";
cout<<ss<<"不是该文法的句子\n";
break;
}
}
if((x)!=string::npos)//x是非终结符的状况
{
p=(x);
q=(a);
if(a=='#')q=t;
temp=table[p][q];
cout<<temp<<endl;//输出使用的产生式
if(temp[0]!='')//分析表中对应项不为error
{
r=9;
while(temp[r]=='')r--;
while(r>3)
{
if(temp[r]!='^')
{
(1,temp[r]);//将X::=x1x2...的规则右部各符号压栈i++;
}
9
r--;
}
}
else
{
cout<<"error\n";
cout<<ss<<"不是该文法的句子\n";
break;
}
}
step++;
}
if(flag)cout<<endl<<ss<<"是该文法的句子\n";
}
intmain( )
{
inti,j;
string*G=newstring[50];//文法G
string*P=newstring[50];//产生式会合P
stringU,u;//文法G非终结符会合U，终结符会合u
intn,t,k;//非终结符、终结符个数,产生式数
string*GG=newstring[50];//除去左递归后的文法GG
string*PP=newstring[50];//文法GG的产生式会合PP
stringUU,uu;//文法GG非终结符会合U，终结符会合u
intnn,tt,kk;//除去左递归后的非终结符、终结符个数,产生式数
string**table;//分析表
cout<<"欢迎使用LL(1)语法分析器!\n\n\n";
cout<<"请输入文法（同一左部的规则在同一行输入，比方：E::=E+T|T；用^表示空串）\n";
input_grammer(G);
preprocess(G,P,U,u,n,t,k);
cout<<"\n该文法有"<<n<<"个非终结符：\n";
for(i=0;i<n;i++)cout<<U[i];
cout<<endl;
cout<<"该文法有"<<t<<"个终结符：\n";
for(i=0;i<t;i++)cout<<u[i];
cout<<"\n\n左递归检测与除去\n\n";
if(eliminate_1(G,P,U,GG))
10