4语法制导四元式算术表达式生成器

1、辽宁师范大学计算机与信息技术学院综合性实验报告课程名称： 编译技术 实验题目：语法制导四元式（算术表达式）生成器 学生姓名： 专业： 计算机科学与技术 学号： 实验日期： 2015.06.05 【实验目的】 1. 理解语法分析器原理、语法制导翻译的过程实质。2. 学会将语法分析所识别的语法成分变换为中间代码形式中的逆波兰记号形式的语义分析方法，编程实现在对一个算术表达式进行语法分析过程的基础上进行语义分析。 【实验内容】 1. 输入算术表达式源语言形式，输出语法分析过程（输入流变化过程）和四元式序列。2. 对于一个给定的算术表达式，首先通过词法分析过程识别出各类语法成分输出至文件中，然后采用预

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|-E1.可推出的非终结符表为：EGTSF否是否是否2.各非终

3、结符的FIRST集合如下：FIRST(E)=(,iFIRST(G)=+, FIRST(T)=(,iFIRST(S)=*, FIRST(F)=(,i3.各非终结符的FOLLOW集合为：FOLLOW(E)=),#FOLLOW(G)=),#FOLLOW(T)=+,),#FOLLOW(S)=+,),#FOLLOW(F)=*,+,),#4.各产生式的SELECT集合为：SELECT(E->TG)=(,iSELECT(G->+TG)=+SELECT(G->)=),#SELECT(T->FS)=(,iSELECT(S->*FS)=*SELECT(S->)=+,),#SEL

4、ECT(F->-E)=(SELECT(F->i)=i5.因为：SELECT(G->+TG)SELECT(G->) = +),# = SELECT(S->*FS)SELECT(S->) = *+,),# = SELECT(F->-E)SELECT(F->i) = i( = 所以文法是LL（1）文法。二、构造预测分析表i+*()-#ETGTG-EG+TGTFSFSS*FSFi（E）三、程序开始1.预测试的算术表达式：4+(-4.67e-10)*(-7.89)+5# 分析后：i+(-i)*(-i)+i#写入文件中。边分析边编织逆波兰式，用数组stack

5、1存放。1. 存入9个文法产生式：E->TGE2->-EG->+TGG2->T->FSS->*FSS2->F->iF2->(E)2. 存入预测分析表格（如二）3. 利用 终结符数组：vt；非终结符数组：vn；预测分析表table；分析栈stack；等等，对待分析串str2进行分析，并将分许过程存入op.txt中。具体代码如下：#include<stdio.h>#include<malloc.h>#include<string.h>#include <ctype.h>char str220=0;

6、/存放识别后的字符串“i+(-i)*(-i)+i#”FILE *op;/存储算术表达式的文件“a+(-4.67e-10)*(-7.89)+b#”FILE *fp;/存储分析过程的文件char vt7='i','+','*','(',')','-','#' /终结符char vn5='E','G','T','S','F'/非终结符typedef struct type /产生式类型定义char left;

7、/非终结符char right5; /产生式右边字符 type;type E,E1,G,G1,T,S,S1,F,F1;/8个产生式type table77;/预分析表char stack30=0;/分析栈char stack130=0;/存储逆波兰式的int s=-1,st=0;/s->栈顶，st->当前需分析字符void analy1(char str1)/分析=>i+(-i)*(-i)+i#int i=0,j=0,p=0,q=0;char s30=0;/辅助堆栈while(str1i!='#')switch(str1i)case 'a':s

8、tr2j+='i'stack1q+='a' break;case 'b':str2j+='i' stack1q+=sp-2; stack1q+=s-p;sp-='0'sp='0' stack1q+='b' break;case '+':sp+='+'str2j+='+'break;case '*':stack1q+=s-p;sp='0'str2j+='*'sp+='*'br

9、eak;case '(':str2j+='('break;case ')':stack1q+=s-p;sp='0' stack1q+='b' str2j+=')'break;case '-':sp+='' if(str2j-1='i')break; elsestr2j+='-' break;case '.':stack1q+='.'if(str2j-1='i')break;else str

10、2j+='i'break;case '0':stack1q+='0'if(str2j-1='i')break;else str2j+='i'break;case '1':stack1q+='1'if(str2j-1='i')break;else str2j+='i' break;case '2':stack1q+='2'if(str2j-1='i')break; else str2j+='i

11、9;break;case '3': stack1q+='3'if(str2j-1='i')break; else str2j+='i' break;case '4': stack1q+='4'if(str2j-1='i')break; else str2j+='i' break;case '5':stack1q+='5'if(str2j-1='i')break; else str2j+='i'break;

12、case '6': stack1q+='6'if(str2j-1='i')break; else str2j+='i' break;case '7':stack1q+='7'if(str2j-1='i')break; else str2j+='i' break;case '8': stack1q+='8'if(str2j-1='i')break; else str2j+='i' break;case &#

13、39;9': stack1q+='9'if(str2j-1='i')break; else str2j+='i' break;case 'e':stack1q+=s-p;sp='0'if(str2j-1='i') sp+='e' break; else str2j+='i' break;i+;stack1q+=s-p;sp='0'str2j='#'void store()/将8个产生式存入printf("产生式：n&q

14、uot;);E.left='E'strcpy(E.right,"TG");printf("%c->%sn",E.left,E.right);E1.left='E'strcpy(E1.right,"-E");printf("%c->%sn",E1.left,E1.right);G.left='G'strcpy(G.right,"+TG");printf("%c->%sn",G.left,G.right);G1.l

15、eft='G'strcpy(G1.right,"");printf("%c->%sn",G1.left,G1.right);T.left='T'strcpy(T.right,"FS");printf("%c->%sn",T.left,T.right);S.left='S'strcpy(S.right,"*FS");printf("%c->%sn",S.left,S.right);S1.left='S&#

16、39;strcpy(S1.right,"");printf("%c->%sn",S1.left,S1.right);F.left='F'strcpy(F.right,"i");printf("%c->%sn",F.left,F.right);F1.left='F'strcpy(F1.right,"(E)");printf("%c->%snn",F1.left,F1.right);int length(char a)/求数组长度

17、int i,l=0;for(i=0;i<5;i+)if(ai!='0') l+;return l;void tables()/建立分析表int i,j;for(i=0;i<=4;i+)/初始化分析表for(j=0;j<=6;j+)tableij.left='N'/表内所有left置Ntable05=E1; table00=table03=E; /存入文法table11=G; table14=table16=G1; table20=T; table23=T;table32=S; table31=table34=table36=S1; table4

18、0=F; table43=F1;printf("表达式文法的预测分析表：n");printf(" t");for(i=0;i<7;i+) printf("%ct",vti);printf("n");for(i=0;i<5;i+)printf("%ct",vni);for(j=0;j<7;j+)printf("%st",tableij.right);printf("n");printf("n");void write(c

19、har str)/将字符串写入文件fpfputs(str,fp);void fun(int h,int l)/将推导所用产生式倒序存入分析栈中int i=length(tablehl.right)-1;s-;for(i; i>-1; i- )stack+s=tablehl.righti;/产生式逆序入栈if(stacks='')stacks-='0'fputc(tablehl.left,fp);write("->");write(tablehl.right);write("n");void print(int

20、n)/写入文件fprintf(fp,"%dtt",n+);/步骤fprintf(fp,"%stt",stack);/分析栈fprintf(fp,"%stt",str2);/剩余输入串void analy2()int i,j,n=0,finish=0,h,l;char X,a;store();/产生式tables();/预测分析表格write("*分析如下*n");write("步骤tt分析栈tt剩余字符tt所用产生式n");stack+s='#'/#入栈stack+s='E'/E入栈a=str2st;/当前剩余串最左字符while(s>-1)X=stacks;/栈顶字符print(+n);for(i=0;i<5;i+)if(X=vni)/栈顶为非终结符时E G T S Fh=i;/行号for(j=0;j<7;j+)if(a=vtj)l=j;/列号break;if(tablehj.left!='N')/不空时fun(h,l);for(i=0;i<7;i+)/栈顶为终结