编译原理实验报告四.docx

编译原理实验报告四.docx

《编译原理实验报告四.docx》由会员分享，可在线阅读，更多相关《编译原理实验报告四.docx（16页珍藏版）》请在冰点文库上搜索。

编译原理实验报告四

编译原理实验报告

题目表达式语法分析程序的构造

学院

专业

班级

学号

学生姓名

指导教师

西安思源学院教务处制

二〇一年

实验四表达式语法分析程序的构造

1、实验目的

1掌握C++语言编译的语法分析程序

2分别掌握LL

（1）、算符优先、LR等语法分析方法的构造。

2、实验环境

MicrosoftVisualC++6.0

3、实验内容

给定某一文法，试构造其简单优先矩阵（或LL

（1）矩阵），并编制程序。

给出相应句子的语法分析过程，判其正确性。

例如：

给定文法G：

E→TE1

E1→+TE1／ε

T→FT1

T1→*F／ε

F→id／（E）

（1）先构造其SELECT集合，判定其是否为LL

（1）文法

（2）是则构造其分析表

（3）给出句子id+id*id$的语法分析过程

4、设计说明

LL

（1）：

#include

#include

typedefintdatatype;

chara[N3]={'$','E'};

charc[N4]={'$','z','*','z','+','z'};

char*B[N1][N2]={

"","z","+","*","（","）","$",

"E","xT","","","xT","","",

"x","","xT+","","","","",

"T","yF","","","yF","","",

"y","","","yF*","","","",

"F","z","","","）E（","","",

};

voidFXB（）

{

inti,j;

cout<<"分析表为:

"<

for（i=0;i

{

for（j=0;j

{cout<

cout<

voidWF（）

{ints;

char*w[5]={"E->TE'","E'->TE'/e","T->FT'","T'->*F/e","F->（E）/id"};

cout<<"文法为:

"<

for（s=0;s<5;s++）

{cout<

}

voidSELECT（）

{

cout<<"SELECT集合为:

"<

cout<<"1.select（E->TE'）=FIRST（TE'）={（,id}"<

cout<<"2.select（E'->+TE'）=FIRST（+TE'）={+}"<

cout<<"3.select（E'->e）=FIRST（E）UFOLLOW（E'）-{e}={$,）}"<

cout<<"4.select（T->FT'）={（,id}"<

cout<<"5.select（T'->*F）={*}"<

cout<<"6.select（T'->e）={+,）,$}"<

cout<<"7.select（F->（E））={（}"<

cout<<"8.select（F->id）={id}"<

cout<<"为LL

（1）文法"<

}

voidshowa（）

{inti;

cout<<"分析栈为:

"<

for（i=0;i

{if（a[i]!

=0）cout<

cout<

voidshowb（）

{intj;

cout<<"输入流为:

"<

for（j=0;j

{if（c[j]!

=NULL）cout<

cout<

}

voidFX（）

{

cout<<"分析如下:

"<

showa（）;showb（）;

inti,j,m,n;

i=I（）;j=J（）;m=M（）;n=N（）;

while（a[m]!

='$'）

{

if（（a[m]!

=c[n]）&&（B[i][j]!

=NULL））

{

a[m]=B[i][j][0];

a[m+1]=B[i][j][1];

a[m+2]=B[i][j][2];

showa（）;showb（）;m=M（）;n=N（）;

if（a[m]==c[n]）{}

else{m=M（）;n=N（）;i=I（）;j=J（）;}

}

elseif（a[m]==c[n]）

{a[m]=NULL;c[n]=NULL;showa（）;showb（）;

m=M（）;n=N（）;i=I（）;j=J（）;}

}

}

voidmain（）

{WF（）;SELECT（）;FXB（）;FX（）;}

算符优先：

voidmain（）

{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集

for（i=0;i

{printf（"%c:

",st[i][0]）;

for（j=0;j

{printf（"%c",first[i][j+1]）;}

printf（"\n"）;

}

printf（"每个非终结符的LASTVT集为：

\n"）;//输出每个非终结符的LASTVT集

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（）;

}

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;N

for（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;

}

SLR

（1）：

voidmain（）{

stringa[12][9]={{"s5","e","e","s4","e","e","1","2","3"},

{"e","s6","e","e","e","ACC","e","e","e"},

{"e","r2","s7","e","r2","r2","e","e","e"},

{"e","r4","r4","e","r4","r4","e","e","e"},

{"s5","e","e","s4","e","e","8","2","3"},

{"e","r6","r6","e","r6","r6","e","e","e"},

{"s5","e","e","s4","e","e","e","9","3"},

{"s5","e","e","s4","e","e","e","e","a"},

{"e","s6","e","e","sb","e","e","e","e"},

{"e","r1","s7","e","r1","r1","e","e","e"},

{"e","r3","r3","e","r3","r3","e","e","e"},

{"e","r5","r5","e","r5","r5","e","e","e"}};

strings[7]={"","E6","E2","T6","T2","F6","F2"};

charc,cc;

stringmyss="";

intflag=0;//看数字或标示符是否结束

listss,ll;

list:

:

iteratormyit;

cout<<"请输入要分析的表达式:

"<

while（（c=getchar（））!

='\n'）{

flag=0;

while（isdigit（c）||isalpha（c））{

flag=1;c=getchar（）;}

if（flag）ss.push_back（'I'）;

if（c=='\n'）break;

ss.push_back（c）;

}

ss.push_back（'$'）;ll.push_back（'$'）;ll.push_back（'0'）;

while

（1）{

if（get（ss.front（））!

=-1）//输入栈

myss=a[getI（ll.back（））][get（ss.front（））];

else{cout<<"错误！

"<

if（myss.at（0）=='s'）{

ll.push_back（ss.front（））;//i进入

ss.pop_front（）;//将I删除

ll.push_back（myss.at

（1））;//5进入

}

elseif（myss.at（0）=='r'）{

for（inti=0;i

（1）-48].at

（1）-48;i++）

ll.pop_back（）;//出栈n位

cc=ll.back（）;//保存当前状态

ll.push_back（s[myss.at

（1）-48].at（0））;//大写字母

ll.push_back（a[getI（cc）][get（ll.back（））].at（0））;

}

elseif（myss.at（0）=='e'）{

cout<<"错误！

"<

elseif（myss.at（0）=='A'）{

cout<<"匹配成功！

"<

for（myss="",myit=ll.begin（）;myit!

=ll.end（）;myit++）

myss+=*myit;

cout<

for（myss="",myit=ss.begin（）;myit!

=ss.end（）;myit++）

myss+=*myit;

cout<

cout<

}

cout<<"分析完毕！

"<

}

运行结果:

输入流：

算符优先：

5、实验总结

通过编写算法，对三种方法都有了更好的了解，对编译原理这门课也有了更清晰的认识。