编译原理实验报告《LL(1)语法分析器构造》Word文档格式.doc
《编译原理实验报告《LL(1)语法分析器构造》Word文档格式.doc》由会员分享，可在线阅读，更多相关《编译原理实验报告《LL(1)语法分析器构造》Word文档格式.doc（15页珍藏版）》请在冰点文库上搜索。
//求符号串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>
cstring>
iostream>
usingnamespacestd;
voidinput_grammer（string*G）//输入文法G,n个非终结符
{
inti=0;
//计数
charch='
y'
;
while（ch=='
）{
cin>
>
G[i++];
cout<
<
"
继续输入?
（y/n）\n"
ch;
}
}
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赋值，可以用U.append（1,a）
for（n=0;
!
G[n].empty（）;
n++）
{U[n]=G[n][0];
}//非终结符集合，n为非终结符个数
for（i=0;
n;
i++）
{
for（j=4;
j<
G[i].length（）;
j++）
{
if（U.find（G[i][j]）==string:
:
npos&
&
u.find（G[i][j]）==string:
npos）
if（G[i][j]!
='
|'
G[i][j]!
^'
）
//if（G[i][j]!
（'
）'
u[t++]=G[i][j];
}
}//终结符集合，t为终结符个数
flag=0;
r=4;
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（flag==1）P[k][r++]=C;
k++;
j++;
P[k][0]=U[i];
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开始增加，只要不在原来问法的非终结符中即可加入
for（i=0;
20&
U[i]!
'
{flagg=0;
arfa=beta="
for（j=0;
100&
P[j][0]!
if（P[j][0]==U[i]）
if（P[j][4]==U[i]）//产生式j有左递归
{
flagg=1;
for（temp=5;
P[j][temp]!
temp++）arfa.append（1,P[j][temp]）;
if（P[j+1][4]==U[i]）arfa.append（"
|"
）;
//不止一个产生式含有左递归
}
else
for（temp=4;
temp++）beta.append（1,P[j][temp]）;
if（P[j+1][0]==U[i]&
P[j+1][4]!
=U[i]）beta.append（"
if（flagg==0）//对于不含左递归的文法规则不重写
{GG[m]=G[i];
m++;
else
flag=1;
//文法存在左递归
GG[m].append（1,U[i]）;
GG[m].append（"
="
if（beta.find（'
）!
=string:
npos）GG[m].append（"
（"
+beta+"
）"
elseGG[m].append（beta）;
while（U.find（C）!
npos）{C++;
GG[m].append（1,C）;
m++;
if（arfa.find（'
+arfa+"
elseGG[m].append（arfa）;
|^"
C++;
}//A:
=Aα|β改写成A:
=βA‘，A’=αA'
|β，
returnflag;
int*ifempty（string*P,stringU,intk,intn）
int*empty=newint[n];
//指示非终结符能否推导到空串
inti,j,r;
for（r=0;
r<
r++）empty[r]=0;
//默认所有非终结符都不能推导到空
intflag=1;
//1表示empty数组有修改
intstep=100;
//假设一条规则最大推导步数为100步
while（step--）
{
for（i=0;
k;
r=U.find（P[i][0]）;
if（P[i][4]=='
）empty[r]=1;
//直接推导到空
else
{
for（j=4;
P[i][j]!
{
if（U.find（P[i][j]）!
{
if（empty[U.find（P[i][j]）]==0）break;
}
elsebreak;
if（P[i][j]=='
//多步推导到空
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;
//cout<
P[i]<
r=U.find（P[i][0]）;
if（P[i][4]=='
first[r].find（'
）==string:
npos）first[r].append（1,'
//规则右部首符号为空
else
for（j=4;
a=P[i][j];
if（u.find（a）!
first[r].find（a）==string:
npos）//规则右部首符号是终结符
{
first[r].append（1,a）;
break;
//添加并结束
}
if（U.find（P[i][j]）!
npos）//规则右部首符号是非终结符,形如X：
：
=Y1Y2...Yk
s=U.find（P[i][j]）;
//cout<
P[i][j]<
\n"
for（tmp=0;
first[s][tmp]!
\0'
tmp++）
{
a=first[s][tmp];
if（a!
npos）//将FIRST[Y1]中的非空符加入
first[r].append（1,a）;
}
if（!
empty[s]）break;
//若Y1不能推导到空，结束
if（P[i][j]=='
if（first[r].find（'
first[r].append（1,'
//若Y1、Y2...Yk都能推导到空，则加入空符号
returnfirst;
stringFIRST（stringU,stringu,string*first,strings）//求符号串s=X1X2...Xn的FIRST集
inti,j,r;
stringfir;
s.length（）;
if（s[i]=='
）fir.append（1,'
if（u.find（s[i]）!
fir.find（s[i]）==string:
npos）{fir.append（1,s[i]）;
break;
}//X1是终结符，添加并结束循环
if（U.find（s[i]）!
npos）//X1是非终结符
r=U.find（s[i]）;
for（j=0;
first[r][j]!
a=first[r][j];
if（a!
fir.find（a）==string:
npos）//将FIRST（X1）中的非空符号加入
fir.append（1,a）;
if（first[r].find（'
npos）break;
//若X1不可推导到空，循环停止
if（i==s.length（））//若X1-Xk都可推导到空
if（fir.find（s[i]）==string:
npos）//fir中还未加入空符号
fir.append（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];
i++）table[i]=newstring[t+1];
for（j=0;
t+1;
table[i][j]="
//table存储分析表的元素，“”表示error
arfa=P[i];
arfa.erase（0,4）;
//删除前4个字符，如：
E:
=E+T,则arfa="
E+T"
fir=FIRST（U,u,first,arfa）;
t;
{
p=U.find（P[i][0]）;
if（fir.find（u[j]）!
q=j;
table[p][q]=P[i];
}//对first（）中的每一终结符置相应的规则
}
if（fir.find（'
follow=FOLLOW[p];
//对规则左部求follow（）
for（j=0;
if（（q=follow.find（u[j]））!
q=j;
}//对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];
if（u.find（s[i]）==string:
npos）//出现非法的符号
cout<
s<
不是该文法的句子\n"
return;
s.append（1,'
#'
stack.append（1,'
//’#’进入分析栈
stack.append（1,U[0]）;
i++;
//文法开始符进入分析栈
a=s[0];
//cout<
stack<
cout<
步骤分析栈余留输入串所用产生式\n"
while（!
flag）
//cout<
步骤分析栈余留输入串所用产生式\n"
cout<
step<
"
"
"
x=stack[i];
stack.erase（i,1）;
i--;
//取栈顶符号x,并从栈顶退出
//cout<
x<
if（u.find（x）!
npos）//x是终结符的情况
if（x==a）
{
s.erase（0,1）;
a=s[0];
//栈顶符号与当前输入符号匹配，则输入下一个符号
cout<
\n"
//未使用产生式，输出空
}
else
cout<
error\n"
ss<
不是该文
升级会员 