实验二编译原理语法分析算符优先.docx
《实验二编译原理语法分析算符优先.docx》由会员分享,可在线阅读,更多相关《实验二编译原理语法分析算符优先.docx(20页珍藏版)》请在冰点文库上搜索。
实验二编译原理语法分析算符优先
实验二语法分析
算符优先分析程序
一.实验要求
⑴选择最有代表性的语法分析方法算符优先法;
⑵选择对各种常见程序语言都用的语法结构,如赋值语句(尤指表达式)作为分析对象,并且与所选语法分析方法要比较贴切。
⑶实习时间为6学时。
二.实验内容及要求
(1)根据给定文法,先求出FirstVt和LastVt集合,构造算符优先关系表(要求算符优先关系表输出到屏幕或者输出到文件);
(2)根据算法和优先关系表分析给定表达式是否是该文法识别的正确的算术表达式(要求输出归约过程)
(3)给定表达式文法为:
G(E’):
E’→#E#
E→E+T|T
T→T*F|F
F→(E)|i
(4)分析的句子为:
(i+i)*i和i+i)*i
三.实验代码
#include"stdafx.h"
#include"stdio.h"
#include"stdlib.h"
#include"iostream.h"
intk;
chara;
intj;
charq;
intr;
intr1;
charst[10][30];
chardata[20][20];
chars[100];
charlable[20];
charinput[100];
charstring[20][10];
charfirst[10][10];
charlast[10][10];
intfflag[10]={0};
intlflag[10]={0};
intdeal();
intzhongjie(charc);
intxiabiao(charc);
voidout(intj,intk,char*s);
voidfirstvt(charc);
voidlastvt(charc);
voidtable();
voidmain()
{
inti,j,k=0;
printf("请输入文法规则数:
");
scanf("%d",&r);
printf("请输入文法规则:
\n");
for(i=0;i{
scanf("%s",st[i]);
first[i][0]=0;
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();
//输出每个非终结符的FIRSTVT集
printf("每个非终结符的FIRSTVT集为:
\n");for(i=0;i{
printf("%c:
",st[i][0]);
for(j=0;j{
printf("%c",first[i][j+1]);
}
printf("\n");
}
//输出每个非终结符的LASTVT集
printf("每个非终结符的LASTVT集为:
\n");for(i=0;i{
printf("%c:
",st[i][0]);
for(j=0;j{
printf("%c",last[i][j+1]);
}
printf("\n");
}
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();
}
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]);
lastvt(st[i][0]);
}
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;iprintf("%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]='=';
}
//求FIRSTVT集
voidfirstvt(charc){
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;
}
}
//求LASTVT集
{
voidlastvt(charc)
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("");
}
}
//判断字符c是否是终极符
intzhongjie(charc)
{
inti;
for(i=0;lable[i]!
='\0';i++)
{
if(c==lable[i])
return1;
}
return0;
}
//求字符c在算符优先关系表中的下标
{
intxiabiao(charc)
inti;
for(i=0;lable[i]!
='\0';i++)
{
if(c==lable[i])
returni;
}
return-1;
}
四、实验结果
输入串为#(i+i)/i#存放于Read.txt文件中
五、实验总结
经过此次试验对算符优先分析的原理有了深入的理解,熟悉了算符分析的过程,掌握了算符优先分析的有关处理,能够使用一种高级语言构造算符优先的语法分析器。
对算符优先分析的相关知识有了更加深入的了解和掌握。