语法制导四元式生成器

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

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

3、0。FIRST(F)=(,i b各非终结符的FOLLOW集合为：。FOLLOW(E) =),# FOLLOW(G) =), #b FOLLOW(T)=(+,), #FOLI_OW(S)=+,), #FOLLOW(F) =*,+, ) ,#各产生式的SELECT集合为：。SELECT (E-TG)=(, iSEI_ECT(G-+TG)=+。SELECT (G 一 “)=),#。SELECT (T-FS) = (,i SELECT (S-*FS)= *SELECT (S-“)=+,),#SELECT (F-E) =(S E LECT(F-i)=i因为：SELEC T (G-+T G)ASE LEC

4、T (G-。)= +A),#= 0SELECT(S-*FS) ASELECT (S-0) = 大 D+,),#= 0SELECT (F-E)ASELECT (F-i)=iA (= 0 所以文法是LL(1)文法。二、构造预测分析表i+*()-#ETGTG-EG+TG八人TFSFSS0*FS八人Fi(E)三、程序开始预测试的算术表达式：4+(-4. 6 7e-10)大(-7. 89)+5 # 分析后：i + (-i)大(-i) + i#写入文件中。边分析边编织逆波兰式，用数组stackl存放。1.存入9个文法产生式： E-TG E2-E G-+TG G2- T-FS S-* F S S2- F-i

5、F 2-(E)存入预测分析表格(如二)利用 终结符数组：vt;非终结符数组:vn ；预测分析表table;分析栈stack;等等，对待分 析串str2进行分析，并将分许过程存入op.txt中。具体代码如下：#include# i nclude#include#include char str220=0；/存放识别后的字符串 “i+(i)*(-i) + i#”F ILE *op; 。/存储算术表达式的文件 “a+(-4. 67e1 0)*(-7. 89)+b#”FILE *fp;。 /存储分析过程的文件char vt 7= 、， + *,(,),-,#;/终结符char vn5=E,G,T,S,

6、F；。非终结符typede f struct type产生式类型定义o char l eft;非终结符。cha r right 5；。产生式右边字符type;type E,E1,G,G1,T,S,S1,F,F1；。/8 个产生式t ype table77;。o 预分析表char stack30 = 0； o o /分析栈char stack130 = 0； o存储逆波兰式的i nt s=1,st=0； o o o /s-栈顶，st-当前需分析字符 void analy1(char str1) o o / /分析二i + (-i)*(-i)+i#o int i = 0,j = 0, p = 0,

7、 q=0;char s30 = 0； o o 辅助堆栈while(st r1i!=#)s w itch(str1i)cas e a： str2j+ = i； stac k1 q+= a; break;o o case b :str2 j+=i ;o o st a ck1q+=s p-2;ostack1 q+ =s p;sp-= 0 ;sp = 0;o st a ck1q+ + = b;obreak；o case + : sp + = + ； o str2 j+ = + ;break;o o cas e *:stack 1 q + = s -p；os p =0;o o str2j+ = *;o

8、o o s p+=大;o o o break;oocase (:str2 j+ = ( ； break; o c ase ):sta ck1 q +=s- p；sp = 。； o o stack1q+ = b;o o str2j+ = );break;o case -:sp += ；o o o o if(str2j-1 = i)break;o o o e I seo s t r2j+ =-；o b r eak;cas e .:sta c k1q+ =.;o if(str2j-1=i)break;o else str2j + = i;o o break；o o cas e O:stack1q+=

9、 0;o oif(str2j-1= = i)break;o oelse str2 j+ = i； o o oo o break;o cas e 1:stack1 q + =1；oo o i f(str2j- l= = i )break;oo o o e I se str2 j+ = i;o o o oo o o o break;o o case 2：stack1q+ = 2;o o o i f(str2j-1=i)break；o o o o o e I se st r 2j+ =i；ooo obreak;o case 3:o stack1q+ = 3;o o if(st r2j 1=i) b

10、reak;o o else str2 j +=i; o o o break;o cas e 4: s t ack 1 q+ =4;o oo i f(str2j-1=i)break；o else str2j + =i；o o o break;o o case 5： o st a ck1q+ = 5;o o o o if(str2j-1 =i )break;o o else str2j + = i;o o oo o o break;o c ase 6: st ack1q+ =6;o oo if(str 2j 1 = =i) b reak；o o o e I se str 2j+= i; o o o

11、o o o break；ocase 7:st ack1q+ = 7;o if (str 2j1 = = i)bre a k;o o o else s t r2j+ = i;o o oo o o o o break；o o case 8 :stack1q+ + =8;o o o o if(str2j-l =i ) break;o o else str2 j+=i;。oo o b r eak;o case 9：ostack1q+ + =9;o o if (str2jT = i)break;o o o e l se str2j+ = i; ooo o break;case e: sta ck1q+

12、=s p ； sp = 0o oif(st r2j-1=i )(oosp+=e；oo oobreak;ooo o else str2j + =i；ooobr eak；o o i+；o o stack1q+=sp ;sp =0；o str2j=#;void store() (o 将8个产生式存入 printf (产生式：n)； E.left=E;o strc py(E.r i ght, TG);o printf (%c %sn,E. left,E.right);E1.le ft=E;strcpy(E1.right,-E);o printf(%c%sn, E1.left,E1.rig ht);o

13、G.left=G;o strcpy(G.right,+T G);o p rintf( %c-% sn,G.left,G.right)；o G1.l eft=G;o strcpy(G1. r ight, );o printf (%c-%sn, G1. left,G1.right);T.left=T ；str cpy(T. ri ght,FS);printf (%c-%s n,T. left,T.right);o S.left=S;str c py(S. r i ght,*FS );o printf (%c %sn,S. left, S.right);S l.left=S ;o str cpy(S

14、1.right, );o printf ( %c-%sn,S1. I eft, SI.rig ht)；F.left=F;o str c py (F.right,i );printf(%c-%sn,F.left,F.rig ht);o F1.left=F；strcpy(F1.right,(E);print f (% c%s nn , F1.left,F1.right);i nt leng t h(cha r a ) o /求数组长度int i ,l =0；o for(i=O;i5；i+)o o if(a i ! = 0)l+;o ret urn l;void tables()o o /建立分析表

15、int i,j;for(i=0;i=4;i+)o o /初始化分析表o o for(j=0;jV=6;j+)tabI eij. left=N ;o 表内所有 left 置 NtabIe05=E1; table00=tabl e 0 3 = E; o /存入文法o table1l=G; table14=table16=G1；o table 2O=T; tab I e 2 3 =T;o table 32 =S; table3 1=tab Ie3 4=tab le36=S 1；o table40=F; tabIe 4 3=F1;printf (表达式文法的预测分析表：n);printf( t);fo

16、r( i=0;i7;i +) pri ntf(%ct,vti);printf (n);for(i=0； i5；i+) o o pr intf (%ct,vni);for (j=0； j-1; i -)stack+s=tablehl.righti；产生式逆序入栈i f(sta ck s = = )o o s tacks- = 0 ;o fputc (tablehl. left,fp);write(-);write (tablehl.right)；write( n);void print(int n )写入文件o fprintf (fp,%dtt, n+);o/步骤fprintf (f p ,%s

17、t t”,s tac k ); o / 分析栈fprintf(fp,%s t t, str 2) ； o o / 剩余输入串 void analy2() o int i,j,n=O,finish=O,h,l;o char X, a ;o store(); /产生式o tables() ;/预测分析表格wr ite(*大*分析如下大大*大大*大*大n) write (步骤tt分析栈tt剩余字符tt所用产生式n);stack+ + s =#;o /# 入栈st ack +s = E ; o /E入栈o a=str2st; o /当前剩余串最左字符wh i le( s -1) o X=stack s

18、; o 栈顶字符o print(+n)for(i = O； i5;i+) o i f(X=vn i) o/栈顶为非终结符时E GT S Fo h=i;o o o /行号o o o for(j=0;j7;j+)i f(a=vt j)ooo l=j;o o /列号 break;oooooooif(tableh j.left! = N)/不空时fun(h,l);55 5 5 5 for(i=0；i TGE-EG-+TGG-AT-FSS-*FSS-AF-iF-XE表达式文法的预测分析表：-A.-A.-Ett4AEGTSFi+TG+TGFS入i*FSTGFSPressanv key to continu

19、e分析过程:制牛旧第辑(E)格式回查春帮助(H)op.txt -记事本i+-l)*(-1)+1#栏弋*麻*幸导坪*乎分析如下*杪*专*导 步骤1201234567890123456789012111111111122222222223333 4 5 6 7g3 3 3 3 3 3=t=t=t=t=-. 分析笏#E #GT #GSF #GSi #GS #G #GT+ #GT #GSF #GS)E( #GS)E #GS)E- #GS)E #GS)GT #GS)GSF #GS)GSi #GS)GS #GS)G #GS) #GS #GSF 布 #GSF #GS)E( #GS)E #GS)E- #GS)E 料S)GT #GS