語法實(shí)驗(yàn)報(bào)告

1、編譯原理實(shí)驗(yàn)報(bào)告題目:語法分析學(xué)生姓名：班 級(jí)：學(xué) 號(hào)：指導(dǎo)教師： -成 績(jī)： 西安郵電大學(xué)計(jì)算機(jī)學(xué)院2015 年5 月28日一：實(shí)驗(yàn)?zāi)康恼莆找环N語法分析規(guī)則，并且能夠動(dòng)態(tài)的生成算符優(yōu)先表或預(yù)測(cè)分析表。二：實(shí)驗(yàn)要求（一）對(duì)于如下的文法，試編寫調(diào)試一個(gè)語法分析程序：E t E+T | TT t T*F | FF t pF| PPt （ E ） | i要求和提示：（ 1）可選擇一種你感興趣的語法分析方法（ LL（1） 、算符優(yōu)先、遞歸下降、 SLR（1）等）作為編制語法分析程序的依據(jù)。（ 2）對(duì)于所選定的分析方法， 如有需要， 應(yīng)選擇一種合適的數(shù)據(jù)結(jié)構(gòu)， 以構(gòu)造所給文法的機(jī)內(nèi)表示。（ 3）能進(jìn)行分

2、析過程模擬。 如輸入一個(gè)句子， 能輸出與句子對(duì)應(yīng)的語法樹， 能對(duì)語法樹生成過程進(jìn)行模擬；能夠輸出分析過程每一步符號(hào)棧的變化情況。（二）First 集和 Follow 集生成算法模擬【問題描述】設(shè)計(jì)一個(gè)由給定文法生成 First 集和 Follow 集并進(jìn)行簡(jiǎn)化的算法動(dòng)態(tài)模擬。（算法參見教材 ）【基本要求】動(dòng)態(tài)模擬算法的基本功能是：1）輸入一個(gè)文法 G；2）輸出由文法 G 構(gòu)造 FIRST 集的算法；3）輸出 First 集；4）輸出由文法 G 構(gòu)造 FOLLOW 集的算法；5）輸出 FOLLOW 集。測(cè)試數(shù)據(jù)】輸入文法：E-TEE-+TE | T-FTT-*FT | F-（E）|i（三）Fir

3、stVT 集和 LastVT 集生成算法模擬【問題描述】設(shè)計(jì)一個(gè)由給定文法生成 FirstVT 集和 LastVT 集的算法動(dòng)態(tài)模擬。 （算法參見教材 P90 92FirstVT 和 LastVT 的構(gòu)造算法 ）【基本要求】動(dòng)態(tài)模擬算法的基本功能是：（ 1） 輸入一個(gè)文法 G；（2） 輸出由文法 G 構(gòu)造 FIRSTVT 集的算法；（ 3） 輸出 FirstVT 集；（4）輸出由文法 G 構(gòu)造 LastVT 集的算法；（ 5）輸出 LastVT 集?！緶y(cè)試數(shù)據(jù)】 輸入文法： E-TEE-+TE | T-FTT-*FT | F-（E）|i三：實(shí)驗(yàn)內(nèi)容完成實(shí)驗(yàn)一和選作題的第二個(gè)四：采用的數(shù)據(jù)結(jié)構(gòu)在

4、第二個(gè)實(shí)驗(yàn)的時(shí)候要用到棧，來存放一些信息，這里采用鏈表來構(gòu)建棧。struct nodechar ch2;struct node *next;/ / 棧頂指針static struct node *stack=NULL;五：算法描述實(shí)驗(yàn)（一）：采用 yacc 語法分析程序自動(dòng)的幫助完成一系列的分析工作，自己只需要編寫完 整的（ .y ）代碼，描述清楚所要實(shí)現(xiàn)的文法，并且要自己處理，文法中存在的沖突問題，解 決辦法按照標(biāo)準(zhǔn)要求寫明。實(shí)驗(yàn)（ 3）：FIRSTVT 算法思想 :設(shè)置一個(gè) int 型數(shù)組，行號(hào)對(duì)應(yīng)為非終結(jié)符，列號(hào)對(duì)應(yīng)為終結(jié)符。 將數(shù)組元素全部初始化為 0.a. 對(duì)于每個(gè)產(chǎn)生式尋找滿足形如

5、U-b或U-Vb的產(chǎn)生式，將對(duì)應(yīng)數(shù)組U,b的值置為1，并且將對(duì)應(yīng)的（非終結(jié)符，終結(jié)符）壓棧。b. 當(dāng)棧不為空的時(shí)候，出棧頂元素（非終結(jié)符，終結(jié)符），記為（Q a）。對(duì)每個(gè)產(chǎn)生式尋找滿足形為P-Q，的產(chǎn)生式，如果P,a=O時(shí)，將對(duì)應(yīng)元素 P，a 的值置為 1，并且壓棧。c. 直到棧為空時(shí)得到的二維數(shù)組為每行值對(duì)應(yīng)為 1 的終結(jié)符為該行非終結(jié)符 的 FIRSTVT集根據(jù)同樣的算法思想可以得到 LISTVT 集合。 優(yōu)先關(guān)系表的構(gòu)建思想：對(duì)于每個(gè)產(chǎn)生式 P-X1X2X3XN如果 Xi 和 Xi+1 都終結(jié)符在，則對(duì)應(yīng)的優(yōu)先關(guān)系為 =如果 Xi 和 Xi+2 都為終結(jié)符，并且 Xi+1 為非終結(jié)符，則

6、對(duì)應(yīng)的 Xi 和 Xi+2的優(yōu)先關(guān)系為 =如果Xi為終結(jié)符Xi+1為非終結(jié)符，則將 FIRSTVT(Xi+1 )中的每個(gè)元素 a, 置對(duì)應(yīng)XiXi+1.六：運(yùn)行結(jié)果hpEhp-u-neva： *-/byyl/F1rt* Q旦即1? 11皐H岬h巾“減四一專 cd tivyl/Ftrgt hp(hpLn9c! -/SyjiX nrst& “11 l.c 1-tMt 3.C3l.c i.ltXt 22-C- a.E 4hpfhp - Lencivoi /tnryl/first$F ERSm ：hpihp -L-ewMO! -/IwmI /ftrs-tS Ifli 電 flFCft51VT-：E=*

7、i*J*1.!lP( FCRSWUTt*,*) FCRSTVTjF-.I.C) FCRSWTip.-ft j FEesm；A=sLA5TWT；ALAETVT： LAETVT： LASTVT： LMTVT; I AETVT：e:心S 5 J) 居5X.l.tMt CS5.txt!.tKt- StACk l.Hehp#Q “ 網(wǎng)0:$*7/1+4ti 43 S 4H 1M7 爲(wèi)B(tài)ID0E1或TP-=-T*F*T*F ，TF- T- E-： 堆*E*Thphp Lenovo -/byylS (B+2J/S-1P-iP-E*TF-；T-：P-T*FTE-TTEP七：調(diào)試情況+*t()f.(E1FPAP

8、t 叫ElTFPAr( ETFFAPEETFPAJ ETFPA, J A-A：E0帆) ETFRAJ+*!(j +*t()rEETFFA,#ETFPA,# 慣先？t :EFI Pft,X 吒八叫I；甘止+*!()*1 ETFPk上在生成FIRST時(shí)換取不同的文法時(shí)，程序發(fā)生了死循環(huán)。在WINDOS下創(chuàng)建的文法文件每行結(jié)束時(shí)是以/r/n占用兩個(gè)字節(jié)，而在LINUX下?lián)Q行只占用一個(gè)In字節(jié)。八：設(shè)計(jì)技巧及體會(huì)設(shè)計(jì)技巧：對(duì)于文法中的 在寫如文件時(shí)，已經(jīng)做過一些處理，方便自己在以后的程序中的處理。體會(huì)：使用YACC，雖然開始時(shí)完全不了解，但是通過基本的學(xué)習(xí)，還是會(huì)一些使 用，這樣通過這個(gè)工具， 使自己

9、方便了自己的編寫程序，節(jié)約了好多時(shí)間，并且比自己獨(dú)立的去完成的更好，還是值得去學(xué)習(xí)和應(yīng)用的九：源程序清單Yacc程序II說明部分%#in clude#in clude void yyerror(char *msg)fprin tf(stderr,%s 出錯(cuò) n,msg);%toke n DIGIT定義一個(gè)終結(jié)符%left +-運(yùn)算符優(yōu)先順序%left * T%II語法規(guī)則line : e n printf（%dn,$）;e: e + t| e - t| tJ printf（ 使用產(chǎn)生式 E-E+T ）; printf（ 將 E+T 歸約為 En）; $=$1+$3; printf（ 使用產(chǎn)生式

10、 E-E-T ）; printf（ 將 E-T 歸約為 En）; $=$1-$3; printf（ 使用產(chǎn)生式 E-T）; printf（ 將 T 歸約為 En）;t :t * f printf（ 使用產(chǎn)生式 T-T*F ）; printf（ 將 T*F 歸約為 Tn）;$=$1*$3; | t / f printf（ 使用產(chǎn)生式 T-T*F ）; printf（ 將 T/F 歸約為 Tn）;$=$1/$3; | f printf（ 使用產(chǎn)生式 T-F ）;Jprintf（ 將 F 歸約為 Tn）;f :p A f printf（ 使用產(chǎn)生式 F-PAF ）; printf（ 將 PAF 歸約

11、為 Fn）; $=$1A$3;| p printf（ 使用產(chǎn)生式 F-P ）; printf（ 將 P 歸約為 Fn）;p : （ e ） printf（ 使用產(chǎn)生式 P-（E）,）;printf（將（E）歸約為 Pn）;$=$2; | DIGIT printf（ 使用產(chǎn)生式 P-i,）;printf（將 %d 歸約為 Pn,$1）;%/程序段int main（void）return yyparse（）;int yylex()int c;c=getchar();if(isdigit(c)yylval=c-0;return DIGIT;return c; 棧鏈表文件程序/#include#inc

12、ludestruct nodechar ch2;struct node *next;/棧頂指針static struct node *stack=NULL;/入棧int push(char a)struct node *p;p=(struct node *)malloc(sizeof(struct node);if(NULL=p)printf( 內(nèi)存申請(qǐng)失敗 !n);return 0;elsep-next=NULL;p-ch0=a0;p-ch1=a1;if(stack=NULL)stack=p;elsep-next=stack;stack=p; return 1;/出棧void pop(cha

13、r cha)struct node *p; p=stack-next; cha0=stack-ch0; cha1=stack-ch1; free(stack);stack=p;/判斷棧是否為空 int is_empty()if(stack=NULL)return 0;elsereturn 1;/打印棧中元素 void print_stack()int i;struct node *p;p=stack;while(p!=NULL)printf(%d %sn,i+,p-ch); p=p-next; 優(yōu)先表代碼 #include #include #include #include #include

14、stack_l.h #define MAX 10 /查找 int in_char(char a,char b) int len;int i;int key=0; len=strlen(a); for(i=0;ilen;i+)if(ai=b)key=1;break;return key;/返回字符串中，特定字符的位置int lookup_char(char a,char b)int i,k=MAX;for(i=0;istrlen(a);i+)if(ai=b)k=i;return k;void delete_n(char a)int len;int i=0;len=strlen(a);alen-1

15、=0;/以表格的形式輸出內(nèi)容void print_table(char a,char b,int *c)int i,j;printf(%5c, );for(i=0;istrlen(a);i+)printf(%8c,ai);printf(n);for(i=0;istrlen(b);i+)printf(%5c,bi);for(j=0;jstrlen(a);j+) printf(%8d,cij);printf(n);/以集合的形式輸出void print_set(char a,char b,int *c,int key)int i,j;int k;int number;char fi=FIRSTVT

16、,la=LASTVT; k=key;for(i=0;istrlen(a);i+)number=0;if(k=0)printf(%s:,fi);elseprintf(%s:,la);printf(%c=,ai); for(j=0;jstrlen(b);j+)if(cij=1 & number=0) printf(%c,bj); number+;else if(cij=1 & number!=0) i+;printf(,%c,bj); number+;printf(n);int main(void)int i=0,j=0,hang=0;FILE *fp;char cssMAXMAX;char zj

17、fMAX;char fzjfMAX;int zjfsize=0,fzjfsize=0;/ int *fvt,*lvt;extern struct node *stack; char zf2;char *yxb; fp=fopen(css.txt,r); if(NULL=fp)printf( 打開文件失?。?return 0;else/保存產(chǎn)生式/保存終結(jié)符/保存非終結(jié)符 終結(jié)符和非終結(jié)符的個(gè)數(shù)/保存一個(gè)非終結(jié)符和對(duì)應(yīng)的終結(jié)符/優(yōu)先表n);while(fgets(cssi,MAX,fp)!=NULL)/ 每次從文件中讀出一行但是包含一個(gè)換行符fclose(fp);hang=i;for(i=0;i

18、hang;i+)/ 除去換行標(biāo)志delete_n(cssi);for(i=0;ihang;i+)for(j=0;j continue;if(cssij=0)break;else if(isupper(cssij)/ 如果是大些字符，為非終結(jié)符if(in_char(fzjf,cssij)=0) fzjffzjfsize=cssij;fzjfsize+;elseif(in_char(zjf,cssij)=0)zjfzjfsize=cssij;zjfsize+;/用 malloc 創(chuàng)建二維數(shù)組 fvt=(int*)malloc(fzjfsize*sizeof(int *); lvt=(int*)ma

19、lloc(fzjfsize*sizeof(int *); yxb=(char*)malloc(zjfsize*sizeof(char *);for(i=0;ifzjfsize;i+)fvti=(int*)malloc(zjfsize*sizeof(int); lvti=(int*)malloc(zjfsize*sizeof(int);/初始化for(i=0;ifzjfsize;i+)for(j=0;jzjfsize;j+)fvtij=0;lvtij=0;for(i=0;izjfsize;i+) yxbi=(char*)malloc(zjfsize*sizeof(char);for(j=0;jb

20、. 和 U-Vb. 的初始 for(i=0;ihang;i+) for(j=0;jb.,zf0=cssi0; zf1=zjfj;fvtlookup_char(fzjf,cssi0)j=1; if(push(zf)=0)printf( 如棧失敗 1！ n);if( cssi4=zjfj & lookup_char(fzjf,cssi3)!=MAX) /滿足 U-Vbfvtlookup_char(fzjf,cssi0)j=1;zf0=cssi0; zf1=zjfj; if(push(zf)=0) printf( 入棧失敗 2！ n); /如果棧不為空 while(is_empty() pop(zf

21、);for(i=0;i.b 和 U-.bV 的初始int k; for(i=0;ihang;i+) k=strlen(cssi);for(j=0;jbzf0=cssi0;zf1=zjfj;lvtlookup_char(fzjf,cssi0)j=1;if(push(zf)=0)printf( 如棧失敗 1！ n);if( cssik-2=zjfj & lookup_char(fzjf,cssik-1)!=MAX)/滿足 U- bVlvtlookup_char(fzjf,cssi0)j=1;zf0=cssi0;zf1=zjfj;if(push(zf)=0)printf( 入棧失敗 2！ n);/如果棧不為空while(is_empty()pop(zf);for(i=0;ihang;i+)k=strlen(cssi);if(zf0=cssik-1) if(lvtlookup_char(fzjf,cssi0)lookup_char(zjf,zf1)=0) lvtlookup_char(fzjf,cssi0)lookup_char(zjf,zf1)=1; zf0=cssi0;if(push(zf)=0)printf( 入棧失敗 3!n