語法制導(dǎo)四元式生成器

1、遼寧師范大學(xué)計(jì)算機(jī)與信息技術(shù)學(xué)院綜合性實(shí)驗(yàn)報(bào)告課程名稱:編譯技術(shù)實(shí)驗(yàn)題目：語法制導(dǎo)四元式（算術(shù)表達(dá)式）生成器學(xué)生姓名:專業(yè)： 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)號(hào)： 實(shí)驗(yàn)日期：2015.06. 05【實(shí)驗(yàn)?zāi)康摹坷斫庹Z法分析器原理、語法制導(dǎo)翻譯的過程實(shí)質(zhì)。學(xué)會(huì)將語法分析所識(shí)別的語法成分變換為中間代碼形式中的逆波蘭記號(hào)形式的語義分析方法， 編程實(shí)現(xiàn)在對(duì)一個(gè)算術(shù)表達(dá)式進(jìn)行語法分析過程的基礎(chǔ)上進(jìn)行語義分析。【實(shí)驗(yàn)內(nèi)容】輸入算術(shù)表達(dá)式源語言形式，輸出語法分析過程(輸入流變化過程)和四元式序列。對(duì)于一個(gè)給定的算術(shù)表達(dá)式，首先通過詞法分析過程識(shí)別出各類語法成分輸出至文件中，然后 采用預(yù)測分析的方法對(duì)其進(jìn)行分析和語法檢查，并

2、給出具體的分析過程,包括分析步驟、分析 棧、剩余符號(hào)以及所用的產(chǎn)生式。在此基礎(chǔ)上，向文法中插入語義動(dòng)作，在語法分析過程中遇 到語義動(dòng)作就做相應(yīng)的翻譯工作，最終將結(jié)果(算術(shù)表達(dá)式的逆波蘭式)輸出到源文件中?！緦?shí)驗(yàn)過程】一、判斷文法是否為LL (1)文法EE + EE-E*EE-i|E由于此文法含左遞歸，消除左遞歸，確定算法優(yōu)先次序，使文法變?yōu)椋篍-TGG-+TG IT-FSS-*FS| 人F-i|E可推出人的非終結(jié)符表為：EGTSF否是否是否各非終結(jié)符的F I RST集合如下:FIRST (E)=(, i。F IRST(G)=+, 0 F IRST(T) = (,i FIRST (S)= (*,

3、0。FIRST(F)=(,i b各非終結(jié)符的FOLLOW集合為：。FOLLOW(E) =),# FOLLOW(G) =), #b FOLLOW(T)=(+,), #FOLI_OW(S)=+,), #FOLLOW(F) =*,+, ) ,#各產(chǎn)生式的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因?yàn)椋篠ELEC 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)文法。二、構(gòu)造預(yù)測分析表i+*()-#ETGTG-EG+TG八人TFSFSS0*FS八人Fi(E)三、程序開始預(yù)測試的算術(shù)表達(dá)式：4+(-4. 6 7e-10)大(-7. 89)+5 # 分析后：i + (-i)大(-i) + i#寫入文件中。邊分析邊編織逆波蘭式，用數(shù)組stackl存放。1.存入9個(gè)文法產(chǎn)生式： E-TG E2-E G-+TG G2- T-FS S-* F S S2- F-i

5、F 2-(E)存入預(yù)測分析表格(如二)利用 終結(jié)符數(shù)組：vt;非終結(jié)符數(shù)組:vn ；預(yù)測分析表table;分析棧stack;等等，對(duì)待分 析串str2進(jìn)行分析，并將分許過程存入op.txt中。具體代碼如下：#include# i nclude#include#include char str220=0；/存放識(shí)別后的字符串 “i+(i)*(-i) + i#”F ILE *op; 。/存儲(chǔ)算術(shù)表達(dá)式的文件 “a+(-4. 67e1 0)*(-7. 89)+b#”FILE *fp;。 /存儲(chǔ)分析過程的文件char vt 7= 、， + *,(,),-,#;/終結(jié)符char vn5=E,G,T,S,

6、F；。非終結(jié)符typede f struct type產(chǎn)生式類型定義o char l eft;非終結(jié)符。cha r right 5；。產(chǎn)生式右邊字符type;type E,E1,G,G1,T,S,S1,F,F1；。/8 個(gè)產(chǎn)生式t ype table77;。o 預(yù)分析表char stack30 = 0； o o /分析棧char stack130 = 0； o存儲(chǔ)逆波蘭式的i nt s=1,st=0； o o o /s-棧頂，st-當(dāng)前需分析字符 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個(gè)產(chǎn)生式存入 printf (產(chǎn)生式：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 /求數(shù)組長度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 表內(nèi)所有 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 (表達(dá)式文法的預(yù)測分析表：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；產(chǎn)生式逆序入棧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(); /產(chǎn)生式o tables() ;/預(yù)測分析表格wr ite(*大*分析如下大大*大大*大*大n) write (步驟tt分析棧tt剩余字符tt所用產(chǎn)生式n);stack+ + s =#;o /# 入棧st ack +s = E ; o /E入棧o a=str2st; o /當(dāng)前剩余串最左字符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/棧頂為非終結(jié)符時(shí)E GT S Fo h=i;o o o /行號(hào)o o o for(j=0;j7;j+)i f(a=vt j)ooo l=j;o o /列號(hào) break;oooooooif(tableh j.left! = N)/不空時(shí)fun(h,l);55 5 5 5 for(i=0；i TGE-EG-+TGG-AT-FSS-*FSS-AF-iF-XE表達(dá)式文法的預(yù)測分析表：-A.-A.-Ett4AEGTSFi+TG+TGFS入i*FSTGFSPressanv key to continu

19、e分析過程:制牛舊第輯(E)格式回查春幫助(H)op.txt -記事本i+-l)*(-1)+1#欄弋*麻*幸導(dǎo)坪*乎分析如下*杪*專*導(dǎo) 步驟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