4、语法制导四元式(算术表达式)生成器.doc
《4、语法制导四元式(算术表达式)生成器.doc》由会员分享，可在线阅读，更多相关《4、语法制导四元式(算术表达式)生成器.doc（10页珍藏版）》请在冰点文库上搜索。
辽宁师范大学计算机与信息技术学院
综合性实验报告
课程名称：
编译技术
实验题目：
语法制导四元式（算术表达式）生成器
学生姓名：
专业：
计算机科学与技术
学号：
实验日期：
2015.06.05
【实验目的】
1.理解语法分析器原理、语法制导翻译的过程实质。
2.学会将语法分析所识别的语法成分变换为中间代码形式中的逆波兰记号形式的语义分析方法，编程实现在对一个算术表达式进行语法分析过程的基础上进行语义分析。
【实验内容】
1.输入算术表达式源语言形式，输出语法分析过程（输入流变化过程）和四元式序列。
2.对于一个给定的算术表达式，首先通过词法分析过程识别出各类语法成分输出至文件中，然后采用预测分析的方法对其进行分析和语法检查，并给出具体的分析过程，包括分析步骤、分析栈、剩余符号以及所用的产生式。
在此基础上，向文法中插入语义动作，在语法分析过程中遇到语义动作就做相应的翻译工作，最终将结果（算术表达式的逆波兰式）输出到源文件中。
【实验过程】
一、判断文法是否为LL
（1）文法
（1）E->E+E
（2）E->E*E
（3）E->i|-E
由于此文法含左递归，消除左递归，确定算法优先次序，使文法变为：
（1）E->TG
（2）G->+TG|^
（3）T->FS
（4）S->*FS|^
（5）F->i|-E
1.可推出^的非终结符表为：
E
G
T
S
F
否
是
否
是
否
2.各非终结符的FIRST集合如下：
FIRST（E）={（,i}
FIRST（G）={+,∅}
FIRST（T）={（,i}
FIRST（S）={*,∅}
FIRST（F）={（,i}
3.各非终结符的FOLLOW集合为：
FOLLOW（E）={）,#}
FOLLOW（G）={）,#}
FOLLOW（T）={+,）,#}
FOLLOW（S）={+,）,#}
FOLLOW（F）={*,+,）,#}
4.各产生式的SELECT集合为：
SELECT（E->TG）={（,i}
SELECT（G->+TG）={+}
SELECT（G->^）={）,#}
SELECT（T->FS）={（,i}
SELECT（S->*FS）={*}
SELECT（S->^）={+,）,#}
SELECT（F->-E）={（}
SELECT（F->i）={i}
5.因为：
SELECT（G->+TG）∩SELECT（G->∅）={+}∩{）,#}=∅
SELECT（S->*FS）∩SELECT（S->∅）={*}∩{+,）,#}=∅
SELECT（F->-E）∩SELECT（F->i）={i}∩{（}=∅
所以文法是LL
（1）文法。
二、构造预测分析表
i
+
*
（
）
-
#
E
TG
TG
-E
G
+TG
^
^
T
FS
FS
S
∅
*FS
^
^
F
i
（E）
三、程序开始
1.预测试的算术表达式：
4+（-4.67e-10）*（-7.89）+5#
分析后：
i+（-i）*（-i）+i# 写入文件中。
边分析边编织逆波兰式，用数组stack1存放。
1.存入9个文法产生式：
E->TG
E2->-E
G->+TG
G2->^
T->FS
S->*FS
S2->^
F->i
F2->（E）
2.存入预测分析表格（如二）
3.利用终结符数组：
vt；非终结符数组：
vn；预测分析表table；分析栈stack；等等，对待分析串str2进行分析，并将分许过程存入op.txt中。
具体代码如下：
#include
#include
#include
#include
charstr2[20]={0}; //存放识别后的字符串“i+（-i）*（-i）+i#”
FILE*op; //存储算术表达式的文件“a+（-4.67e-10）*（-7.89）+b#”
FILE*fp; //存储分析过程的文件
charvt[7]={'i','+','*','（','）','-','#'};//终结符
charvn[5]={'E','G','T','S','F'}; //非终结符
typedefstructtype{//产生式类型定义
charleft;//非终结符
charright[5]; //产生式右边字符
}type;
typeE,E1,G,G1,T,S,S1,F,F1; //8个产生式
typetable[7][7]; //预分析表
charstack[30]={0}; //分析栈
charstack1[30]={0}; //存储逆波兰式的
ints=-1,st=0; //s->栈顶，st->当前需分析字符
voidanaly1（charstr1[]）{ //分析=>i+（-i）*（-i）+i#
inti=0,j=0,p=0,q=0;
chars[30]={0}; //辅助堆栈
while（str1[i]!
='#'）{
switch（str1[i]）{
case'a':
str2[j++]='i';stack1[q++]='a';break;
case'b':
str2[j++]='i';
stack1[q++]=s[p-2];
stack1[q++]=s[--p];s[p--]='\0';s[p]='\0';
stack1[q++]='b';
break;
case'+':
s[p++]='+'; str2[j++]='+';break;
case'*':
stack1[q++]=s[--p];
s[p]='\0';
str2[j++]='*';
s[p++]='*';
break;
case'（':
str2[j++]='（';break;
case'）':
stack1[q++]=s[--p];s[p]='\0';
stack1[q++]='b';
str2[j++]='）';break;
case'-':
s[p++]='@';
if（str2[j-1]=='i'）break;
else str2[j++]='-';
break;
case'.':
stack1[q++]='.';
if（str2[j-1]=='i'）break;
elsestr2[j++]='i';
break;
case'0':
stack1[q++]='0';
if（str2[j-1]=='i'）break;
elsestr2[j++]='i';
break;
case'1':
stack1[q++]='1';
if（str2[j-1]=='i'）break;
elsestr2[j++]='i';
break;
case'2':
stack1[q++]='2';
if（str2[j-1]=='i'）break;
elsestr2[j++]='i';
break;
case'3':
stack1[q++]='3';
if（str2[j-1]=='i'）break;
elsestr2[j++]='i';
break;
case'4':
stack1[q++]='4';
if（str2[j-1]=='i'）break;
elsestr2[j++]='i';
break;
case'5':
stack1[q++]='5';
if（str2[j-1]=='i'）break;
elsestr2[j++]='i';
break;
case'6':
stack1[q++]='6';
if（str2[j-1]=='i'）break;
elsestr2[j++]='i';
break;
case'7':
stack1[q++]='7';
if（str2[j-1]=='i'）break;
elsestr2[j++]='i';
break;
case'8':
stack1[q++]='8';
if（str2[j-1]=='i'）break;
elsestr2[j++]='i';
break;
case'9':
stack1[q++]='9';
if（str2[j-1]=='i'）break;
elsestr2[j++]='i';
break;
case'e':
stack1[q++]=s[--p];s[p]='\0';
if（str2[j-1]=='i'）{
s[p++]='e';
break;
}
elsestr2[j++]='i';
break;
}
i++;
}
stack1[q++]=s[--p];s[p]='\0';
str2[j]='#';
}
voidstore（）{ //将8个产生式存入
printf（"产生式：
\n"）;
E.left='E';
strcpy（E.right,"TG"）;
printf（"%c->%s\n",E.left,E.right）;
E1.left='E';
strcpy（E1.right,"-E"）;
printf（"%c->%s\n",E1.left,E1.right）;
G.left='G';
strcpy（G.right,"+TG"）;
printf（"%c->%s\n",G.left,G.right）;
G1.left='G';
strcpy（G1.right,"^"）;
printf（"%c->%s\n",G1.left,G1.right）;
T.left='T';
strcpy（T.right,"FS"）;
printf（"%c->%s\n",T.left,T.right）;
S.left='S';
strcpy（S.right,"*FS"）;
printf（"%c->%s\n",S.left,S.right）;
S1.left='S';
strcpy（S1.right,"^"）;
printf（"%c->%s\n",S1.left,S1.right）;
F.left='F';
strcpy（F.right,"i"）;
printf（"%c->%s\n",F.left,F.right）;
F1.left='F';
strcpy（F1.right,"（E）"）;
printf（"%c->%s\n\n",F1.left,F1.right）;
}
intlength（chara[]）{ //求数组长度
inti,l=0;
for（i=0;i<5;i++）
if（a[i]!
='\0'）l++;
returnl;
}
voidtables（）{ //建立分析表
inti,j;
for（i=0;i<=4;i++） //初始化分析表
for（j=0;j<=6;j++）
table[i][j].left='N'; //表内所有left置‘N’
table[0][5]=E1;table[0][0]=table[0][3]=E; //存入文法
table[1][1]=G;table[1][4]=table[1][6]=G1;
table[2][0]=T;table[2][3]=T;
table[3][2]=S;table[3][1]=table[3][4]=table[3][6]=S1;
table[4][0]=F;table[4][3]=F1;
printf（"表达式文法的预测分析表：
\n"）;
printf（"\t"）;
for（i=0;i<7;i++）printf（"%c\t",vt[i]）;
printf（"\n"）;
for（i=0;i<5;i++）{
printf（"%c\t",vn[i]）;
for（j=0;j<7;j++）
printf（"%s\t",table[i][j].right）;
printf（"\n"）;
}
printf（"\n"）;
}
voidwrite（charstr[]）{ //将字符串写入文件fp
fputs（str,fp）;
}
voidfun（inth,intl）{ //将推导所用产生式倒序存入分析栈中
inti=length（table[h][l].right）-1;
s--;
for（i;i>-1;i--）
stack[++s]=table[h][l].right[i]; //产生式逆序入栈
if（stack[s]=='^'）
stack[s--]='\0';
fputc（table[h][l].left,fp）;
write（"->"）;
write（table[h][l].right）;
write（"\n"）;
}
voidprint（intn）{ //写入文件
fprintf（fp,"%d\t\t",n++）; //步骤
fprintf（fp,"%s\t\t",stack）; //分析栈
fprintf（fp,"%s\t\t",str2）; //剩余输入串
}
voidanaly2（）{
inti,j,n=0,finish=0,h,l;
charX,a;
store（）; //产生式
tables（）; //预测分析表格
write（"********************分析如下********************\n"）;
write（"步骤\t\t分析栈\t\t剩余字符\t\t所用产生式\n"）;
stack[++s]='#'; //#入栈
stack[++s]='E'; //E入栈
a=str2[st]; //当前剩余串最左字符
while（s>-1）{
X=stack[s]; //栈顶字符
print（++n）;
for（i=0;i<5;i++）{
if（X==vn[i]）{ //栈顶为非终结符时EGTSF
h=i; //行号
for（j=0;j<7;j++）{
if（a==vt[j]）{
l=j; //列号
break;
}
}
if（table[h][j].left!
='N'）{ //不空时
fun（h,l）;
}
}
}
for（i=0;i<7;i++）{ //栈顶为终结符时i+*（）-#
if（X==vt[i]）{
stack[s--]='\0';
str2[st++]='';
a=str2[st]; //当前剩余串最左字符
fputc（X,fp）;
if（X=='#'） write（"接受\n"）;
elsewrite（"匹配\n"）;
}
}
}
}
voidmain（）{
charstr1[300]={0}; //预分析算术表达式a+（-4.67e-10）*（-7.89）+b#
charh[]="\n";
fp=fopen（"H:
fp.txt","r"）;
fgets（str1,300,fp）; //fgets读取一行fgetc读取一个字符fread想要的长度
fclose（fp）;
analy1（str1）;
fp=fopen（"H:
fp.txt","a"）; //不会覆盖原数据
fwrite（h,sizeof（h）,1,fp）; //换行
fwrite（stack1,sizeof（stack1）,1,fp）; //写入逆波兰式
fclose（fp）;
printf（"分析得到的符号串：
%s\n\n",str2）;
op=fopen（"H:
op.txt","w"）;
fputs（str2,fp）; //写入i+（-i）*（-i）+i#
write（"\n"）;
analy2（）;
fclose（op）;
}
四、运行结果截屏：
源文件：
屏幕输出：
分析过程：
运行后的源文件：
【实验结果分析】
升级会员 