语法制导四元式算术表达式生成器.docx
《语法制导四元式算术表达式生成器.docx》由会员分享，可在线阅读，更多相关《语法制导四元式算术表达式生成器.docx（16页珍藏版）》请在冰点文库上搜索。
语法制导四元式算术表达式生成器
辽宁师范大学计算机与信息技术学院
综合性实验报告
课程名称:
编译技术
实验题目：
语法制导四元式（算术表达式）生成器
学生姓名:
专业：
计算机科学与技术
学号：
实验日期：
２01５.06．0５
【实验目的】
1.理解语法分析器原理、语法制导翻译的过程实质。
2.学会将语法分析所识别的语法成分变换为中间代码形式中的逆波兰记号形式的语义分析方法,编程实现在对一个算术表达式进行语法分析过程的基础上进行语义分析。
【实验内容】
1.输入算术表达式源语言形式，输出语法分析过程（输入流变化过程）和四元式序列。
2.对于一个给定的算术表达式,首先通过词法分析过程识别出各类语法成分输出至文件中,然后采用预测分析的方法对其进行分析和语法检查，并给出具体的分析过程,包括分析步骤、分析栈、剩余符号以及所用的产生式。
在此基础上，向文法中插入语义动作，在语法分析过程中遇到语义动作就做相应的翻译工作,最终将结果（算术表达式的逆波兰式）输出到源文件中。
【实验过程】
一、判断文法是否为LL
（1）文法
（1）E－＞Ｅ＋Ｅ
（２）E－>E*E
（3）E->i|－E
由于此文法含左递归，消除左递归,确定算法优先次序,使文法变为：
（1）E->TG
（２）G->+TG｜＾
（3）T-＞FS
（4）S->*FS|＾
（5）F->i|－E
1.可推出＾的非终结符表为:
Ｅ
G
T
S
F
否
是
否
是
否
2.各非终结符的FＩRST集合如下:
FIRST（Ｅ）={（，i}
ﻩＦIRST（Ｇ）={+,∅}
ＦIRＳT（T）＝{（,i}
FIRSＴ（S）=｛*， ∅}
ﻩFIRST（Ｆ）={（,ｉ}
ﻩ
3.各非终结符的FOLＬOＷ集合为：
ﻩFOＬLOW（E）={）,#}
FＯLLＯW（G）={）,＃}
ﻩFOLLOＷ（Ｔ）=｛+,）,＃}
ﻩＦOLＬOW（S）={+,）,＃}
FOLLOW（F）={*,+,）,#}
4．各产生式的SELECT集合为：
ﻩSELECＴ（E->TG）=｛（，i}
SＥＬＥCT（G->+TG）={+}
ﻩSELECT（G－>^）={），＃}
ﻩSEＬECT（T－>FS）={（,i}
ﻩSELＥCＴ（Ｓ->*FＳ）=｛*}
ＳELEＣT（S-＞^）=｛+,）,#}
SELECT（F->-E）={（}
SＥLECT（F->i）=｛i｝
5.因为:
SELECＴ（Ｇ->+TＧ）∩SＥLECT（G-＞∅）＝{+}∩{）,＃}=∅
SELECT（S-＞*ＦS）∩ＳＥLECT（S->∅） ＝{＊}∩{＋，），＃｝ =∅
SELECT（F->－E）∩SＥLECＴ（Ｆ->ｉ）={ｉ}∩{（}=∅
所以文法是LL
（1）文法。
二、构造预测分析表
i
+
*
（
）
-
#
E
ＴG
TG
－E
G
+TG
^
^
T
ＦS
FS
S
∅
*ＦＳ
^
＾
F
i
（E）
三、程序开始
1.预测试的算术表达式:
4+（-4.６７e-10）＊（-7．89）+5＃
ﻩ 分析后：
i+（-i）＊（-i）+i#写入文件中。
边分析边编织逆波兰式，用数组sｔack1存放。
1.存入９个文法产生式:
Ｅ-＞TG
E２－>－E
G->+ＴG
G２－＞＾
T-＞ＦS
S->*ＦS
S２->^
Ｆ->i
Ｆ2->（E）
2.存入预测分析表格（如二）
3.利用 终结符数组：
vｔ;非终结符数组:
vn；预测分析表tabｌe;分析栈stack;等等，对待分析串ｓtr２进行分析，并将分许过程存入op．ｔxt中。
具体代码如下：
#include
#ｉncludｅ＜malloc.h>
#iｎｃlude<ｓtring.h>
#incluｄe
cｈarsｔr２[20］={０｝；ﻩﻩ//存放识别后的字符串“ｉ+（－i）*（-i）+i#”
ＦILE*op;ﻩﻩ／/存储算术表达式的文件“a+（-4．67e－１0）*（-7.８9）+ｂ#”
FIＬE*ｆp;ﻩﻩﻩ//存储分析过程的文件
chaｒvｔ[7]=｛＇i＇,'+',＇*＇,'（','）','-'，'#'}; //终结符
char vｎ[５]=｛＇Ｅ','G','T＇,＇Ｓ',＇Ｆ'}；ﻩ//非终结符
typedeｆstructtype{//产生式类型定义
ﻩｃｈaｒlｅft; //非终结符
ﻩchaｒriｇhｔ[５］；ﻩ//产生式右边字符
｝type;
typｅE,Ｅ１,G,Ｇ１,T，Ｓ，S1,Ｆ,F1；ﻩ／/8个产生式
ｔypetaｂlｅ[7][7];ﻩﻩﻩﻩ//预分析表
char sｔack[3０]＝{0}；ﻩﻩ/／分析栈
cｈaｒｓtacｋ1[30]={0}；ﻩ//存储逆波兰式的
iｎt s=－１,sｔ=0；ﻩﻩﻩ/／ｓ-＞栈顶，ｓt->当前需分析字符
ｖoiｄaｎalｙ１（charstr1[]）｛ﻩﻩ／/分析=＞i+（-i）*（-ｉ）＋i#
ﻩint i=０,j=０，p＝0，q=0;
chａrs[30]＝{0}；ﻩﻩ//辅助堆栈
ｗhile（stｒ1[i]!
=＇＃＇）{
sｗitch（ｓｔｒ1[i]）{
casｅ'a'：
stｒ2[j++］='ｉ'；stacｋ１[q++]=＇ａ'; break;
ﻩﻩcase'b＇:
str2［j++]='i＇;
ﻩﻩ stａck1[q++]=s［p-2];
ﻩstack1［q＋+]＝s［-－p];s[p--]=＇\０＇;s[p]＝'\0';
ﻩ stａck1[ｑ＋＋]='b';
ﻩｂreak；
ﻩcase '+'：
s[ｐ++]='＋'；ﻩｓtr２[j++]＝'＋＇;break;
ﻩﻩcasｅ'*':
stack１[ｑ+＋]＝ｓ[--p]；
ﻩs［p］='\0';
ﻩﻩｓｔr2[j++]＝'*';
ﻩﻩﻩs［p++]='＊';
ﻩﻩﻩbreaｋ;
ﻩﻩcａsｅ'（':
sｔr２[j++]='（＇；bｒeａk;
ﻩｃase '）':
stａck1[ｑ++]=s[--ｐ］；ｓ[p]＝'\０'；
ﻩﻩ stack1[q++]='b';
ﻩﻩstr2[j++]＝'）';bｒeaｋ;
ﻩcase '-':
s[ｐ++]=＇@＇；
ﻩﻩﻩﻩif（ｓtr2[j-1]=='i'）ｂreak;
ﻩﻩﻩeｌseﻩsｔr2[j++］=＇-'；
ﻩbｒeak;
casｅ '.':
staｃk1[q++］='.';
ﻩif（ｓｔr2[j-１]＝='i'）break;
ﻩelse str2[j＋+]＝'i';
ﻩﻩbreaｋ；
ﻩﻩcasｅ＇０':
stａck1[q++]=＇0';
ﻩﻩｉf（str2[j-1］＝＝'i'）bｒeak;
ﻩﻩelｓe sｔr２[j+＋]='ｉ'；ﻩﻩﻩ
ﻩﻩbrｅak;
ﻩcasｅ'１＇:
stack1[ｑ++］='1'；
ﻩﻩﻩｉf（str２［j-１］＝＝'i＇）break;
ﻩﻩﻩﻩeｌsestr2[ｊ＋+]='i';ﻩﻩﻩﻩ
ﻩﻩﻩﻩ bｒeak;
ﻩﻩcａsｅ'2'：
ｓｔａcｋ1[q＋+]＝'2＇;
ﻩﻩﻩｉf（str2[ｊ-1]=='i'）bｒｅak；
ﻩﻩﻩﻩﻩ eｌse stｒ2[j＋+］='ｉ'；
ﻩﻩ
ﻩﻩｂrｅak;
ﻩcaｓe'3':
ﻩｓtａｃk1[q+＋]='3';
ﻩﻩif（stｒ2[j－1]＝='i'）ｂreａk;
ﻩﻩelsestr2［ｊ++］＝＇i＇;ﻩ
ﻩﻩ ｂｒeak;
ﻩcasｅ'4':
sｔack１[ｑ++］=＇4';
ﻩﻩﻩｉf（ｓtｒ2[j-1]=='i'）brｅak；
ﻩelｓestｒ2[ｊ++]＝＇i'；
ﻩﻩﻩbreak;
ﻩﻩcaｓe＇５'：
ﻩstａck1[q++]='5';
ﻩﻩﻩﻩif（str2[j-1］=='ｉ＇）break;
ﻩﻩelｓestｒ2[j＋+]='i';ﻩﻩﻩ
ﻩﻩﻩbreak;
ﻩｃase'6':
stａck1[q＋+］='６＇;
ﻩﻩﻩif（str２［j－1]=＝＇ｉ'）ｂreak；
ﻩﻩﻩeｌsestｒ2[ｊ＋+]=＇ｉ';ﻩﻩﻩ
ﻩﻩﻩbreak；ﻩ
cａｓe'7':
sｔack1[q++]='7';
ﻩｉｆ（str２[j－１]=＝'i'）breａk;
ﻩﻩﻩ elｓｅsｔr2[j++］=＇i＇;ﻩﻩﻩ
ﻩﻩﻩﻩﻩbｒeａｋ；
ﻩﻩcaｓe'8'：
sｔaｃk1[q＋＋］＝'8＇;
ﻩﻩﻩﻩif（ｓｔr２[ｊ-１］=='i＇）brｅak;
ﻩﻩ ｅｌsｅｓｔr2［j＋+]=＇ｉ＇;ﻩ
ﻩﻩﻩ bｒeak;
ﻩcase'９＇:
ﻩ stack1[q+＋]＝＇9＇;
ﻩﻩif（ｓtr２[j-１]=='i'）breaｋ;
ﻩﻩﻩ eｌseｓtｒ2[j++]='i';ﻩﻩ
ﻩﻩbrｅaｋ;
cａｓe'ｅ':
ｓｔａck1[ｑ++］=s[－-ｐ]；s[p]='\0';
ﻩﻩif（stｒ２[ｊ-1]＝='i＇）{
ﻩﻩ s[ｐ++］='e'；ﻩ
ﻩﻩﻩbrｅaｋ;
ﻩﻩ}
ﻩﻩelseｓtｒ2［ｊ++]＝＇i'；
ﻩﻩﻩｂｒeak；
ﻩ}
ﻩi++；
ﻩ}
ﻩｓｔaｃk1[q++］＝s[-－p］;ｓ[ｐ］='＼0'；
ﻩstr2[j]=＇＃';
}
voidstore（）｛ﻩ//将8个产生式存入
printｆ（"产生式：
\n"）；
E.left='E';
ﻩstrcｐy（Ｅ.rｉght，＂TG"）;
ﻩprintｆ（"%c－>%s\n",E．lｅft,E.righｔ）;
E1.leｆｔ='E';
strcpy（E1.riｇｈt,"-E"）;
ﻩpｒintf（"％ｃ－>％s\n"，E1.left，Ｅ1.ｒｉｇht）;
ﻩG.left='G';
ﻩsｔrｃｐy（G.right,"+TＧ＂）;
ﻩｐrintf（＂%c-＞%ｓ\n",G.leｆｔ,G.right）；
ﻩG1.lｅft='G';
ﻩstrcpy（G1.ｒight，"^"）;
ﻩpriｎｔf（"%c->%s\n",Ｇ１.ｌeｆt,G1.right）;
T.left＝＇Ｔ＇；
strｃpｙ（T.ｒｉght,"FS"）;
ｐrｉｎtf（＂％c->%s＼n",T．left,T.right）;
ﻩS.lｅft='S';
strｃpy（S．rｉght,"*FS＂）;
ﻩprｉnｔｆ（"%c－>％s＼n",S.ｌｅft，S.right）;
S１.left='Ｓ';
ﻩstrｃｐｙ（S1.ｒigｈt,"＾"）;
ﻩpｒｉｎtf（＂%c->％s\n",S1.ｌeft,Ｓ1.rｉｇht）；
F.left='F';
ﻩstrｃpy（F.riｇｈｔ,"i＂）;
printf（"％c->%s\n",F.lefｔ,F.rｉｇht）;
ﻩF1.lｅft＝＇Ｆ＇;
ｓtrcpｙ（F１.riｇht,"（Ｅ）"）;
printｆ（"%ｃ－>％ｓ\n\n＂，F１.lｅft,F1.riｇｈt）;
}
ｉntlengｔh（chaｒ a［］）{ﻩ／/求数组长度
intｉ,l＝0；
ﻩfor（ｉ=０;ｉ<5；ｉ＋＋）
ﻩﻩif（ａ[i］!
＝'＼0'） l＋+;
ﻩｒeｔurnl;
}
voidｔables（）{ﻩﻩ//建立分析表
inｔ i,j;
for（ｉ＝0;i<=４;i++）ﻩﻩ//初始化分析表
ﻩﻩfoｒ（j=0;j＜＝6;ｊ+＋）
taｂｌe[i][j]．lｅｆt='Ｎ＇;ﻩ//表内所有lｅｆt置‘N’
tａbｌe[0][5]＝E1;ｔable[0][0]=tａblｅ[0]［3]=Ｅ;ﻩ／/存入文法
ﻩtablｅ［1][１］＝Ｇ;table[1][４]=ｔablｅ[1][6]=G1；
ﻩtable［2][０］＝T;ｔａbｌe［2］[3]＝T;
ﻩtaｂlｅ[3][2］=S;ｔable[3］[1]=tａbｌｅ［3］[4]=tａｂle[3][6]=S１；
ﻩtａｂlｅ[4][0］=F;ｔaｂｌｅ[4］[3]=F1;
printｆ（"表达式文法的预测分析表：
＼n"）;
pｒｉntf（" ＼ｔ"）;
ｆor（ｉ＝0;i<7;i＋+） priｎtf（"%c\t"，ｖｔ［i］）;
priｎｔｆ（"\n"）;
for（i=0；i<5；ｉ++）{
ﻩﻩpｒinｔf（＂%c＼t",vn[i］）;
fｏr（ｊ=0；j<7;j++）
ﻩﻩprintf（"%ｓ\t",ｔabｌe［i][j].rigｈt）；
ﻩﻩﻩpriｎｔf（＂\n"）;
ﻩﻩ}
pｒinｔf（"＼n＂）；
}
ｖoid wｒiｔe（charstｒ［]）{ﻩ//将字符串写入文件fｐ
ﻩfpｕｔs（ｓtｒ,fp）;
}
voidｆuｎ（inｔｈ,intl）{ﻩﻩ／/将推导所用产生式倒序存入分析栈中
inｔi=length（tablｅ[h］[l]．right）-１;ﻩ
ﻩs－－;
ﻩfor（ｉ; ｉ＞-1;ｉ--）
ｓtack［++s]=table[ｈ][l]．rｉghｔ［i］；//产生式逆序入栈
ｉf（staｃｋ[s]=＝'^'）
ﻩﻩｓtack[s--]='\0＇;
ﻩfpｕtｃ（table[h][l]．leｆt,fp）;
wｒite（"->"）;
ｗrite（tａblｅ[h][l].rigｈt）；
wｒite（"\ｎ＂）;
｝
voidprint（intｎ）{//写入文件
ﻩfprintf（fp,"%d＼t\t",ｎ＋＋）;ﻩ／/步骤
ｆｐrintｆ（fｐ,"%s\t\ｔ＂，ｓtacｋ）;ﻩ/／分析栈
ｆprintｆ（ｆp,＂％s\ｔ\t"，str２）；ﻩﻩ/／剩余输入串
}
voidanaly2（）｛
ﻩinti,j,n=０,fｉnｉsh＝０,ｈ,l;
ﻩcｈａr X,ａ;
ﻩｓtoｒｅ（）;//产生式
ﻩtables（）;//预测分析表格
ｗｒite（"*＊****＊**＊**＊*****＊*分析如下＊＊**＊＊****＊*＊****＊*＊\n"）;
wｒiｔｅ（"步骤\t\t分析栈＼ｔ＼t剩余字符＼t\t所用产生式＼n"）;
stack[+＋s］=＇＃';ﻩ//＃入栈
stａck［++s]='Ｅ';ﻩ／/Ｅ入栈
ﻩa=sｔr２[ｓt];ﻩ//当前剩余串最左字符
whｉlｅ（ｓ>-1）｛
ﻩX=stack［s］;ﻩ//栈顶字符
ﻩpｒｉｎt（++ｎ）;
for（i=０；i<5;i＋＋）｛
ﻩｉf（X==vn［i]）｛ﻩ//栈顶为非终结符时E Ｇ TS Ｆ
ﻩh=ｉ;ﻩﻩﻩ//行号
ﻩﻩﻩfor（j=0;j<7;j+＋）{
ﻩﻩﻩｉf（a==vt［j]）{
ﻩﻩﻩｌ=j;ﻩﻩ//列号
ﻩﻩbreak;
ﻩﻩﻩ}
ﻩ}ﻩﻩﻩﻩﻩﻩﻩ
ﻩｉf（ｔable[h]［j］．ｌｅft!
='N'）{//不空时
ﻩfun（h,l）;
ﻩ}
ﻩﻩ}
ﻩﻩ}
ﻩfor（i=0；ｉ<7;i++）{ﻩ//栈顶为终结符时i +* （）-#
ﻩif（X＝=vｔ[i]）｛
ﻩstack［s--]＝'\0';
ﻩstr2[sｔ＋＋]='';
ﻩa=stｒ2［ｓt];ﻩ//当前剩余串最左字符
ﻩｆputc（X,fｐ）;
ﻩﻩﻩif（X=＝'#＇）ﻩwrite（"接受\n"）;
elsewrｉｔｅ（"匹配＼n"）；
ﻩ}
ﻩ｝
ﻩ}
}
voiｄｍain（）{
ﻩcｈａrstr1[3０0］＝{0}；ﻩﻩ//预分析算术表达式a+（-4.６7e-１0）＊（-7．89）+ｂ#
ｃharh［]＝"\n＂;
fp=ｆopen（"H：
ｆｐ.txt＂,＂r"）;
ﻩｆgｅts（str1,３０0，fp）；//fgets读取一行fgetc读取一个字符frｅad想要的长度
fclｏsｅ（ｆｐ）;
ﻩaｎaｌy１（sｔr1）;
ﻩｆp=foｐen（"Ｈ:
ｆp.txt","a"）;／/不会覆盖原数据
ﻩfｗriｔe（ｈ,sｉzeof（ｈ）,1，fp）;//换行
ﻩfwrite（ｓtaｃk1,sizｅof（sｔack1）,1,ｆp）；//写入逆波兰式
ﻩfclose（ｆｐ）；
ﻩpｒiｎｔf（"分析得到的符号串：
%s＼n\n",str2）;
op=fopen（"H:
op.ｔxｔ","w＂）;
fputs（str2,fp）；ﻩ／/写入i+（-i）*（-ｉ）+i#
ﻩwrｉtｅ（"\ｎ"）;
ﻩａｎaly2（）;
fclosｅ（op）;
}
四、运行结果截屏:
源文件：
屏幕输出：
分析过程：
运行后的源文件:
【实验结果分析】
升级会员 