4、语法制导四元式生成器

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

2、语法检查，并给出具体的分析过程，包括分析步骤、分析栈、剩余符号以及所用的产生式。在此基础上，向文法中插入语义动作，在语法分析过程中遇 到语义动作就做相应的 翻译工作，最终将结果(算术表达式的 逆波兰式)输出到源文件中。【实验过程】一、判断文法是否为LL(1)文法E->E+E(2) E->E*E(3) E->i|-E由于此文法含左递归，消除左递归，确定算法优先次序，使文法变为：E->TG(2) G->+TGF(3) T->FS(4) S->*FSF(5) F->i|-E1. 可推出八的非终结符表为：EGTSF否是否是否2. 各非终结符的FIRST集

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

4、(F->-E)=(SELECT(F->i)=i5. 因为：SELECT(G->+TG7 SELECT(G->) = + n ),#=SELECT(S->*FS)A SELECT(S->) = * n +,),#= SELECT(F->-E)n SELECT(F->i) = i n ( =?所以文法是LL (1)文法。二、构造预测分析表i+*()-#ETGTG-EG+TGAATFSFSS?*FSAAFi(E)、程序开始1. 预测试的算术表达式：4+(-4.67e-10)*(-7.89)+5#分析后：i+(-i)*(-i)+i#写入文件中。边分析边编

5、织逆波兰式，用数组stack1存放。1. 存入9个文法产生式：E->TGE2->-EG->+TGG2->aT->FSS->*FSS2->aF->iF2->(E)2. 存入预测分析表格(如二)3. 利用终结符数组：vt ;非终结符数组：vn；预测分析表table ;分析栈stack ;等等，对待分 析串str2进行分析，并将分许过程存入 op.txt中。具体代码如下：#in clude<stdio.h> #in clude<malloc.h> #i ncludevstri ng.h>#include <ct

6、ype.h> char str220=0; FILE *op;FILE *fp;/ 存放识别后的字符串“ i+(-i)*(-i)+i# ”/ 存储算术表达式的文件“ a+(-4.67e-10)*(-7.89)+b# ”/ 存储分析过程的文件char vt7='i','+','*','(',')','-','#' /char vn5='E','G','T','S','F'终结符 / 非终结符typed

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

8、1i)/ 分析 =>i+(-i)*(-i)+i#/ 辅助堆栈case 'a':str2j+='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;

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

10、#39;.' if(str2j-1='i')break; else str2j+='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&#

11、39; if(str2j-1='i')break; else str2j+='i'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'

12、if(str2j-1='i')break; else str2j+='i' break;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(s

13、tr2j-1='i')break; else str2j+='i' break;case '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='

14、;0' str2j='#'void store() / 将 8 个产生式存入 printf(" 产生式： n");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' strcp

15、y(G.right,"+TG");printf("%c->%sn",G.left,G.right);G1.left='G'strcpy(G1.right,w); 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&q

16、uot;); printf("%c->%sn",S.left,S.right);S1.left='S'strcpy(S1.right,w); 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("

17、;%c->%snn",F1.left,F1.right);int length(char a)/ 求数组长度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 置 N'table05=E1; table00=table03=E; / 存入文法 table11=G; table14=t

18、able16=G1;table20=T; table23=T;table32=S; table31=table34=table36=S1;table40=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&

19、quot;,tableij.right);printf("n");printf("n");void write(char str) / 将字符串写入文件 fp fputs(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='A')stacks-='0'fputc(tablehl.lef

20、t,fp);write("->");write(tablehl.right);write("n");void print(int 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("f

21、*分析如下*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

22、(h,l); for(i=0;i<7;i+)/ 栈顶为终结符时 i + * ( ) - #if(X=vti)stacks-='0'str2st+=' 'a=str2st;/ 当前剩余串最左字符fputc(X,fp);if(X='#') write(" 接受 n"); else write(" 匹配 n");void main()char str1300=0; char h="n" fp=fopen("H:fp.txt","r"); fgets

23、(str1,300,fp); fclose(fp);想要的长度/ 预分析算术表达式 a+(-4.67e-10)*(-7.89)+b#/fgets 读取一行 fgetc 读取一个字符 fread/ 不会覆盖原数据analy1(str1);fp=fopen("H:fp.txt","a");/写入逆波兰式fwrite(h,sizeof(h),1,fp);/ 换行fwrite(stack1,sizeof(stack1),1,fp); fclose(fp);prin tf("分析得到的符号串：%snn",str2);op=fope n(&quo

24、t;H:op.txt","w");fputs(str2,fp);/ 写入 i+(-i)*(-i)+i#write("n");an aly2();fclose(op);四、运行结果截屏: 源文件：fp.txt - i己事本文件(F)韬恪式(O)奁宜(V)帮助H)戸+(7 67e-lC-7? 29) +U屏幕输出：" H:DebugttLexe'分析猖劃的符号串: m+i#lE->TGE->-EG->+TGIg->aT->FSS->*FSls->AF->iF-XE>表达式文法的预测分析表;i+Ei TG+普<TG-EG+TG4ATSPSA*FSFS-AAFi<E>Press any key to continue分析过程:op.txt -记爭本文件旧煽鸳(EJ 惜式Q宣看(V) 帮飾(H)广G S r