编译原理语法分析实验报告.docx
《编译原理语法分析实验报告.docx》由会员分享，可在线阅读，更多相关《编译原理语法分析实验报告.docx（23页珍藏版）》请在冰点文库上搜索。
编译原理语法分析实验报告
一．语法分析方法
有文法G[S]：
（0）S’→#S#
（1）S→V
（2）V→T|ViT
（3）T→F|T+F
（4）F→）V*|（
分析的句子为（+（i（
1.判断为算符优先文法：
文法没有A->…BC…且BC均为非终结符，因此它为OG文法
文法没有同时存在
①A->…ab…或A->….aBb….
②A->…aB…且B＝>b….或B＝>Cb….
③A->…Bb….且B＝>…a或B＝>…aC
文法为算符优先文法
2.求FirstVT集和LastVT集
有产生式（0）S’→#S#可得’#’
’#’
表1-1非终结符的FIRSTVT和LASTVT集合表
FIRSTVT
LASTVT
S’
#
#
S
i,+,）,（
i,+,*,（
V
i,+,）,（
i,+,*,（
T
+,）,（
+,（,*
F
）,（
*,（
3.根据FirstVT和LastVT集构造算符优先表
表1-2G[S]的算符优先关系矩阵表
#
i
+
*
（
）
#
i
+
*
（
）
二．程序设计
1.总体设计
图2-1总体设计图
2.子程序设计
创建文法关系表模块
图2-2子程序设计创建文法关系模块图
三．程序中的结构说明
1.重要函数介绍
intdeal（）;//对输入串的分析函数
intzhongjie（charc）;//判断字符c是否是终结符函数
intxiabiao（charc）;//求字符c在算符优先关系表中的下标
voidout（intj,intk,char*s）;//打印s栈
voidfirstvt（charc）;//求非终结符c的FIRSTVT集
voidlastvt（charc）;//求非终结符c的LASTVT集
voidtable（）;//创建文法优先关系表
voidprtfun（charbiao[10][10]）;//打印firstvt或者lastvt集
2.函数代码
#include"stdio.h"
#include"stdlib.h"
chardata[20][20];//算符优先关系
chars[100];//模拟符号栈s
charlable[20];//文法终结符集
charinput[100];//文法输入符号串
charstring[20][10];//用于输入串的分析
intk;
chara;
intj;
charq;
intr;//文法规则个数
intr1;//转化后文法规则个数
charst[10][30];//用来存储文法规则
charfirst[10][10];//文法非终结符FIRSTVT集
charlast[10][10];//文法非终结符LASTVT集
intfflag[10]={0};//标志第i个非终结符的FIRSTVT集是否已求出
intlflag[10]={0};//标志第i个非终结符的LASTVT集是否已求出
intdeal（）;//对输入串的分析
intzhongjie（charc）;//判断字符c是否是终结符
intxiabiao（charc）;//求字符c在算符优先关系表中的下标
voidout（intj,intk,char*s）;//打印s栈
voidfirstvt（charc）;//求非终结符c的FIRSTVT集
voidlastvt（charc）;//求非终结符c的LASTVT集
voidtable（）;//创建文法优先关系表
voidprtfun（charbiao[10][10]）;//打印firstvt或者lastvt集
intmain（）
{
inti,j,k=0;
printf（"请输入文法规则数：
"）;
scanf（"%d",&r）;
printf（"请输入文法规则：
\n"）;
for（i=0;i{
scanf（"%s",st[i]）;//存储文法规则，初始化FIRSTVT集和LASTVT集
first[i][0]=0;//first[i][0]和last[i][0]分别表示st[i][0]非终结
符的FIRSTVT集和LASTVT集中元素的个数*/
last[i][0]=0;
}
for（i=0;i{
for（j=0;st[i][j]!
='\0';j++）
{
if（st[i][0]<'A'||st[i][0]>'Z'）//判断首字母若不是非终结符
{printf（"不是算符文法!
\n"）;
exit（-1）;
}
if（st[i][j]>='A'&&st[i][j]<='Z'）//判断两个非终结符相连
{
if（st[i][j+1]>='A'&&st[i][j+1]<='Z'）
{printf（"不是算符文法!
\n"）;
exit（-1）;
}
}
}
}
for（i=0;i{
for（j=0;st[i][j]!
='\0';j++）
{
if（（st[i][j]<'A'||st[i][j]>'Z'）&&st[i][j]!
='-'&&st[i][j]!
='>'&&st[i][j]!
='|'）
lable[k++]=st[i][j];
}
}
lable[k]='#';
lable[k+1]='\0';
table（）;
printf（"每个非终结符的FIRSTVT集为：
\n"）;//输出每个非终结符的FIRSTVT集
prtfun（first）;
printf（"每个非终结符的LASTVT集为：
\n"）;//输出每个非终结符的LASTVT集
prtfun（last）;
printf（"算符优先分析表如下:
\n"）;
for（i=0;lable[i]!
='\0';i++）
printf（"\t%c",lable[i]）;//打印优先关系矩阵第一行
printf（"\n"）;
for（i=0;i{
printf（"%c\t",lable[i]）;//打印优先关系矩阵第一列元素
for（j=0;j{
printf（"%c\t",data[i][j]）;//打印每一列的优先关系
}
printf（"\n"）;
}
printf（"请输入文法输入符号串以#结束:
"）;
scanf（"%s",input）;//接受输入分析串
deal（）;
}
voidprtfun（charbiao[10][10]）//打印firstvt或者lastvt集
{
inti,j;
for（i=0;i{
printf（"%c:
",st[i][0]）;//输入对应非终结符
for（j=0;j{
printf（"%c",biao[i][j+1]）;
}
printf（"\n"）;
}
}
voidtable（）//创建文法优先关系表
{
chartext[20][10];
inti,j,k,t,l,x=0,y=0;
intm,n;
x=0;
for（i=0;i{firstvt（st[i][0]）;//求对应非终结符的FIRSTVT集
lastvt（st[i][0]）;//求对应非终结符的LASTVT集
}
for（i=0;i{text[x][y]=st[i][0];
y++;
for（j=1;st[i][j]!
='\0';j++）
{
if（st[i][j]=='|'）
{
text[x][y]='\0';//将“|”前部分作为一条规则
x++;
y=0;
text[x][y]=st[i][0];//将“|”后部分作为另一条规则
y++;
text[x][y++]='-';
text[x][y++]='>';
}
else
{
text[x][y]=st[i][j];
y++;
}
}
text[x][y]='\0';
x++;
y=0;
}
r1=x;
printf（"转化后的文法为:
\n"）;
for（i=0;i{
printf（"%s\n",text[i]）;
}
for（i=0;i"后的转化文法，用于最后的规约）*/
{string[i][0]=text[i][0];
for（j=3,l=1;text[i][j]!
='\0';j++,l++）
string[i][l]=text[i][j];
string[i][l]='\0';
}
for（i=0;i{
for（j=1;text[i][j+1]!
='\0';j++）
{
if（zhongjie（text[i][j]）&&zhongjie（text[i][j+1]））//求“=”关系
{
m=xiabiao（text[i][j]）;
n=xiabiao（text[i][j+1]）;//求终结符在优先关系表中的下标
data[m][n]='=';
}
if（text[i][j+2]!
='\0'&&zhongjie（text[i][j]）&&zhongjie（text[i][j+2]）&&!
zhongjie（text[i][j+1]））//求“=”关系
{
m=xiabiao（text[i][j]）;
n=xiabiao（text[i][j+2]）;
data[m][n]='=';
}
if（zhongjie（text[i][j]）&&!
zhongjie（text[i][j+1]））
{
for（k=0;k{
if（st[k][0]==text[i][j+1]）
break;
}
m=xiabiao（text[i][j]）;
for（t=0;t{
n=xiabiao（first[k][t+1]）;
data[m][n]='<';
}
}
if（!
zhongjie（text[i][j]）&&zhongjie（text[i][j+1]））//求“>”关系
{
for（k=0;k{
if（st[k][0]==text[i][j]）
break;
}
n=xiabiao（text[i][j+1]）;
for（t=0;t{
m=xiabiao（last[k][t+1]）;
data[m][n]='>';
}
}
}
}
m=xiabiao（'#'）;
for（t=0;t{
n=xiabiao（first[0][t+1]）;
data[m][n]='<';
}
n=xiabiao（'#'）;
for（t=0;t{
m=xiabiao（last[0][t+1]）;
data[m][n]='>';
}
data[n][n]='=';
}
voidfirstvt（charc）//求FIRSTVT集
{
inti,j,k,m,n;
for（i=0;i{
if（st[i][0]==c）
break;
}
if（fflag[i]==0）
{
n=first[i][0]+1;
m=0;
do
{if（m==2||st[i][m]=='|'）
{if（zhongjie（st[i][m+1]））
{first[i][n]=st[i][m+1];
n++;
}
else
{if（zhongjie（st[i][m+2]））
{first[i][n]=st[i][m+2];
n++;
}
if（st[i][m+1]!
=c）
{firstvt（st[i][m+1]）;
for（j=0;j{if（st[j][0]==st[i][m+1]）
break;
}
for（k=0;k{
intt;
for（t=0;t{
if（first[i][t]==first[j][k+1]）
break;
}
if（t==n）
{
first[i][n]=first[j][k+1];
n++;
}
}
}
}
}
m++;
}while（st[i][m]!
='\0'）;
first[i][n]='\0';
first[i][0]=--n;
fflag[i]=1;
}
}
voidlastvt（charc）//求LASTVT集
{
inti,j,k,m,n;
for（i=0;i{
if（st[i][0]==c）
break;
}
if（lflag[i]==0）
{
n=last[i][0]+1;
m=0;
do
{
if（st[i][m+1]=='\0'||st[i][m+1]=='|'）
{
if（zhongjie（st[i][m]））
{
last[i][n]=st[i][m];
n++;
}
else
{
if（zhongjie（st[i][m-1]））
{
last[i][n]=st[i][m-1];
n++;
}
if（st[i][m]!
=c）
{
lastvt（st[i][m]）;
for（j=0;j{
if（st[j][0]==st[i][m]）
break;
}
for（k=0;k{
intt;
for（t=0;t{
if（last[i][t]==last[j][k+1]）
break;
}
if（t==n）
{
last[i][n]=last[j][k+1];
n++;
}
}
}
}
}
m++;
}while（st[i][m]!
='\0'）;
last[i][n]='\0';
last[i][0]=--n;
lflag[i]=1;
}
}
intdeal（）//对输入串的分析
{
inti,j;
intx,y;
intz;//输入串的长度
k=1;
s[k]='#';//栈置初值
for（i=0;input[i]!
='\0';i++）;//计算输入串的长度
z=i--;
i=0;
while（（a=input[i]）!
='\0'）
{
if（zhongjie（s[k]））
j=k;
else
j=k-1;
x=xiabiao（s[j]）;
y=xiabiao（a）;
if（data[x][y]=='>'）
{
out（1,k,s）;
printf（"%c",a）;
out（i+1,z,input）;
printf（"归约\n"）;
do
{
q=s[j];
if（zhongjie（s[j-1]））
j=j-1;
elsej=j-2;
x=xiabiao（s[j]）;
y=xiabiao（q）;
}while（data[x][y]!
='<'）;
intm,n,N;
for（m=j+1;m<=k;m++）
{
for（N=0;Nfor（n=1;string[N][n]!
='\0';n++）
{
if（!
zhongjie（s[m]）&&!
zhongjie（string[N][n]））
{
if（zhongjie（s[m+1]）&&zhongjie（string[N][n+1]）
&&s[m+1]==string[N][n+1]）
{
s[j+1]=string[N][0];
break;
}
}
else
if（zhongjie（s[m]））
if（s[m]==string[N][n]）
{
s[j+1]=string[N][0];
break;
}
}
}
k=j+1;
if（k==2&&a=='#'）
{
out（1,k,s）;
printf（"%c",a）;
out（i+1,z,input）;
printf（"结束\n"）;
printf（"输入串符合文法的定义！
\n"）;
return1;//输入串符合文法的定义
}
}
else
if（data[x][y]=='<'||data[x][y]=='='）
{//移进
out（1,k,s）;
printf（"%c",a）;
out（i+1,z,input）;
printf（"移进\n"）;
k++;
s[k]=a;
i++;
}
else
{
printf（"\nflase"）;
return0;
}
}
printf（"\nflase"）;
return0;
}
voidout（intj,intk,char*s）
{
intn=0;
inti;
for（i=j;i<=k;i++）
{
printf（"%c",s[i]）;
n++;
}
for（;n<15;n++）
{
printf（""）;
}
}
intxiabiao（charc）//求字符c在算符优先关系表中的下标
{
inti;
for（i=0;lable[i]!
='\0';i++）
{
if（c==lable[i]）
returni;
}
return-1;
}
intzhongjie（charc）//判断字符c是否是终结符
{
inti;
for（i=0;lable[i]!
='\0';i++）
{
if（c==lable[i]）
return1;
}
return0;
}
四．程序测试
当输入文法首字母不是终结符的情况时，程序提示不是算符文法
图4-1判断不是算符文法测试
当输入文法分析串没有“#”结束时，分析失败
图4-2分析失败测试
当输入文法分析串以“#”结束时，分析成功
图4-3分析成功测试
五、实验总结
经过学习实现了算符优先算法，能够对输入的符号串进行算符优先分析，并且能够处理分析过程中遇到的错误。
经过这次课程设计的练习，我感觉自己的编程能力得到了很好的锻炼，是一次很好的实践活动，对以后的学习也有很大的帮助。
指导教师签字：
年月日
升级会员 