編譯原理語法分析實(shí)驗(yàn)報(bào)告

1、.編譯原理實(shí)驗(yàn)報(bào)告實(shí)驗(yàn)名稱：編寫語法分析程序 實(shí)驗(yàn)類型：設(shè)計(jì)性實(shí)驗(yàn) 指導(dǎo)教師：蔣 勇 專業(yè)班級(jí)：軟件工程1401 姓 名：* 學(xué) 號(hào)：* 實(shí)驗(yàn)地點(diǎn)：東六E座301 實(shí)驗(yàn)成績(jī)：_ 日期： 2016年5月17日實(shí)驗(yàn)一編寫詞法分析程序一、 實(shí)驗(yàn)?zāi)康模?. 設(shè)計(jì)、編寫、調(diào)試一個(gè)遞歸下降分析程序，實(shí)現(xiàn)對(duì)詞法分析程序提供的單詞序列進(jìn)行語法檢查和結(jié)構(gòu)分析。2. 掌握遞歸下降語法分析方法。3. 鞏固理論知識(shí)。二、 實(shí)驗(yàn)設(shè)計(jì)：1. 設(shè)計(jì)原理：1) 對(duì)于文法的每一個(gè)非終結(jié)符U的文法規(guī)則是一個(gè)識(shí)別U的過程定義，為每一個(gè)非終結(jié)符構(gòu)造子程序。2) 如果U的右部符號(hào)串只有一個(gè)候選式則從左到右依次構(gòu)造U的識(shí)別代碼。3) 如

2、果U的右部符號(hào)串有終結(jié)符號(hào)，則判斷輸入的符號(hào)是否匹配終結(jié)符號(hào)，如果相等，則讀入下一個(gè)符號(hào)；如果不相等，則有語法錯(cuò)誤，應(yīng)當(dāng)報(bào)錯(cuò)。4) 如果是非終結(jié)符號(hào)，則調(diào)用非終結(jié)符號(hào)的子程序即可。5) 如果U的右部有多個(gè)候選式，應(yīng)該根據(jù)每個(gè)候選式的第一個(gè)符號(hào)來確定該分支。6) 對(duì)于含有表達(dá)式的文法規(guī)則需要判斷輸入的符號(hào)是否在U的FOLLOW集里面。2. 設(shè)計(jì)方法：(1) 文法改造，消除二義性；(2) 對(duì)含有左遞歸或者左公因子的文法消除左遞歸，提取左公因子；(3) 求每一個(gè)右部符號(hào)串的FIRST集合，如果右部含有，則需要求出其產(chǎn)生式左部非終結(jié)符的FOLLOW集。判斷文法是否是LL（1）文法，若不是LL(1)文法

3、，說明文法的復(fù)雜性超過自頂向下方法的分析能力。(4) 根據(jù)改寫后的文法設(shè)計(jì)程序，依據(jù)設(shè)計(jì)原理構(gòu)造每一個(gè)非終結(jié)符的子程序。3. 設(shè)計(jì)過程：(1) 改寫文法、消除左遞歸（將左遞歸改為右遞歸）、提取左公因子；(2) 求出相應(yīng)的First集和Follow集；(3) 設(shè)計(jì)程序流程圖，設(shè)計(jì)程序；(4) 編寫程序；4. 框架思路，錯(cuò)誤信息輸出：對(duì)每一個(gè)非終結(jié)符構(gòu)造其子程序，設(shè)定一個(gè)返回值。如果語法分析有錯(cuò)則返回1，沒有錯(cuò)誤就返回0；對(duì)于錯(cuò)誤，在程序的相應(yīng)行數(shù)報(bào)錯(cuò)。各個(gè)非終結(jié)符之間依據(jù)文法規(guī)則調(diào)用。每次遇到終結(jié)符函數(shù)都判斷是否匹配當(dāng)前終結(jié)符號(hào)，如果不匹配則報(bào)錯(cuò)，返回1。如果匹配，則讀入下一個(gè)符號(hào)。三、 實(shí)驗(yàn)過

4、程(一) 本次實(shí)驗(yàn)的TEST語言語法規(guī)則：1) <program><declaration_list><statement_list>2) <declaration_list><declaration_list><declaration_stat> | 3) <declaration_stat>int ID;4) <statement_list><statement_list><statement>| 5) <statement> <if_stat>|

5、<while_stat>|<for_stat>|<read_stat> |<write_stat>|< compound_stat > |<expression_stat>6) <if_stat> if (<expr>) <statement >| if (<expr>) <statement >else < statement >7) <while_stat> while (<expression>) < stateme

6、nt >8) <for_stat> for (<expression><expression><expression>)<statement>9) <write_stat>write <expression>10) <read_stat>read ID;11)<compound_stat><statement_list>12)<expression_stat>< expression >|;13)< expression > ID=&

7、lt;bool_expr>|<bool_expr>14)<bool_expr><additive_expr> |< additive_expr >(>|<|>=|<=|=|!=)< additive_expr > 15)< additive_expr>< additive_expr>+<term>|< additive_expr>-<term>|< term > 16)< term >< term >*<

8、factor>|< term >/<factor>|< factor >17)< factor >(< expression >)|ID|NUM1. 將左遞歸改為右遞歸：2) <declaration_list><declaration_list><declaration_stat> | 改寫后：<declaration_list>:=<declaration_list1><declaration_list1>:=<declaration_stat&g

9、t;<declaration_list1>|4) <statement_list><statement_list><statement>| 改寫后：<statement_list>:=<statement_list1><statement_list1>:=<statement><statement_list1>|15)< additive_expr>< additive_expr>+<term>|< additive_expr>-<t

10、erm>|< term >改寫后：<additive_expr>:=<term><additive_expr1><additive_expr>:=+<term><additive_expr1>|-<term><additive_expr1>|16)< term >< term >*<factor>|< term >/<factor>|< factor >改寫后：<term>:=<factor&

11、gt;<term1><term1>:=*<factor><term1>|/<factor><term1>|2. 提取公因式：14)<bool_expr><additive_expr> |<additive_expr>(>|<|>=|<=|=|!=)< additive_expr >改寫后：<bool_expr> := <additive_expr><bool_expr1><bool_expr1> :=|(

12、>|<|>=|<=|=|!=)<additive_expr>3. 是否可以提取公因式6) <if_stat> if (<expr>) <statement >| if (<expr>) <statement >else < statement >不可以提取公因式，if語句和ifelse語句是相互獨(dú)立的,并沒有必然的聯(lián)系。 4規(guī)則13超前讀入符號(hào)解決方案：如果識(shí)別出標(biāo)識(shí)符的符號(hào)ID后，在讀入一個(gè)符號(hào)，如果這個(gè)符號(hào)時(shí)=，說明選擇的是賦值表達(dá)式，如果不是=，則說明選擇是布爾表達(dá)式。(二) 、求

13、出右部符號(hào)串的FIRST集和含有產(chǎn)生式的左部非終結(jié)符的FOLLOW集1)<program><declaration_list><statement_list>FIRST(<declaration_list><statement_list>) = ;2) <declaration_list>:=<declaration_list1><declaration_list1>:=<declaration_stat><declaration_list1>|FIRST(<decla

14、ration_list1>) = int, ;FIRST(<declaration_stat><declaration_list1>) = int ;FOLLOW(<declaration_list1>) = if,while,for,read,write,;,ID,(,NUM;3) <declaration_stat>int ID;FIRST(int ID;) = int ;4)<statement_list>:=<statement_list1><statement_list1>:=<state

15、ment><statement_list1>|FIRST(<statement_list1>) = if,while,for,read,write,;,ID,NUM,(;FIRST(<statement><statement_list1>) = if,while,for,read,write,;,ID,NUM,(;FOLLOW(<statement_list1>) = ;5) <statement><if_stat>|<while_stat>|<for_stat>|<read

16、_stat>|<write_stat>|< compound_stat > |<expression_stat>FIRST(<if_stat>) = if;FIRST(<while_stat>)= whileFIRST(<for_stat>) = forFIRST(<read_stat>) = read;FIRST(<write_stat>) = writeFIRST(<compound_stat>)=FIRST(<expression_stat>)=ID,NUM,;,

17、(6) <if_stat> if (<expr>) <statement >| if (<expr>) <statement >else < statement >FIRST(if (<expr>) <statement >) = ifFIRST(if (<expr>) <statement >else < statement >)=if7) <while_stat> while (<expression>) < statement

18、>FIRST(while (<expression>) < statement >) = while8) <for_stat> for (<expression><expression><expression>)<statement>FIRST(for (<expression><expression><expression>)<statement> = for9) <write_stat>write <expression>FIRS

19、T(write <expression>) = write10) <read_stat>read ID;FIRST(read ID;) = read11)<compound_stat><statement_list>FIRST(<statement_list>) = 12)<expression_stat>< expression >|;FIRST(< expression >) = (,ID,NUM;FIRST(;) = ;13)< expression > ID=<bool_e

20、xpr>|<bool_expr>FIRST(ID=<bool_expr>) = ID;FIRST(<bool_expr>) = ID,NUM,(;14)<bool_expr><additive_expr> |<additive_expr>(>|<|>=|<=|=|!=)< additive_expr ><bool_expr> := <additive_expr><bool_expr1><bool_expr1> :=|(>|<

21、;|>=|<=|=|!=)<additive_expr>FIRST(<additive_expr><bool_expr1>)=（，ID，NUMFIRST(>|<|>=|<=|=|!=)< additive_expr >)=>,<,>=,<=,=,!=FOLLOW(<bool_expr1>)=),;15)< additive_expr>< additive_expr>+<term>|< additive_expr>-<ter

22、m>|< term ><additive_expr>:=<term><additive_expr1><additive_expr1>:=+<term><additive_expr1>|-<term><additive_expr1>|FIRST(< term ><additive_expr1>)= (,ID,NUM FIRST(+<term><additive_expr1>)=+FIRST(-<term><additi

23、ve_expr1>)=-FOLLOW(<additive_expr1>)=>,<,>=,<=,=,!=,;,)16)< term >< term >*<factor>|< term >/<factor>|< factor ><term>:=<factor><term1><term1>:=*<factor><term1>|/<factor><term1>|FIRST(<factor&

24、gt;) = (,ID,NUM;FIRST(*<factor><term1>)=*;FIRST(/<factor><term1>)=/;FOLLOW(<term1>) = +,-,;,>,<,>=,<=,=,!=17)< factor >(< expression >)|ID|NUMFIRST(<expression>)= (:FIRST(ID) =ID;FIRST(NUM) = NUM;(三) 、<statement>程序流程圖(四) 、<expressi

25、on>程序流程圖四、 試驗(yàn)調(diào)試記錄：1、問題表現(xiàn)：當(dāng)語法分析到最后一行時(shí)進(jìn)入死循環(huán)。分析原因：可能是文件沒有結(jié)束條件，導(dǎo)致一直讀取文件最后一個(gè)字符解決方案：經(jīng)過百度發(fā)現(xiàn)fscanf()具有返回值，如果不為空返回1，為空則返回0。在文件結(jié)束時(shí)，它會(huì)默認(rèn)將文件最后一個(gè)字符繼續(xù)讀入。程序就進(jìn)入了死循環(huán)。 所以在每次讀取文件是都判斷fscanf()是否小于等于0，如果成立，則把讀入的字符數(shù)組置為空。解決結(jié)果：讀到最后一行時(shí)沒有進(jìn)入死循環(huán)。成功解決問題。2、問題表現(xiàn)：讀到第5行時(shí)缺少； 按照常理應(yīng)該在這一行報(bào)錯(cuò)。但是確報(bào)錯(cuò)在第6行。分析原因：因?yàn)榈?行讀到c時(shí)匹配，這個(gè)時(shí)候就繼續(xù)讀入下一個(gè)字符，但

26、是這個(gè)字符是在下一行的for，并不是；所以就在for所在的這一行報(bào)錯(cuò)。就顯示的第6行有錯(cuò)誤。解決方案：其實(shí)我覺得這是沒有錯(cuò)誤的，所以就沒有處理這個(gè)問題。像codeblocks這個(gè)編譯軟件遇到這種問題也是在下一行報(bào)錯(cuò)。所以我沒有改變這個(gè)報(bào)錯(cuò)模式。五、實(shí)驗(yàn)結(jié)果:1、測(cè)試數(shù)據(jù)：int a;int i;int 2b;int cfor (i=1; i <= 10 i=i+1);a=a+ib=b*i;c=a+b;while(x<=)C=a+b+(x*y;if (a>b) read a;else write b;write c2、實(shí)驗(yàn)現(xiàn)象：運(yùn)用實(shí)驗(yàn)一詞法分析的結(jié)果進(jìn)行語法分析1)、第一處錯(cuò)

27、誤：int 2b;將int 2b;改為int b;后2)、第二處錯(cuò)誤：int c加上;后解決該行錯(cuò)誤3)、第三處錯(cuò)誤：for (i=1; i <= 10 i=i+1)分析這個(gè)語句可以判斷缺少一個(gè) ；在10后面加上分號(hào)后解決該行錯(cuò)誤4)、第四處錯(cuò)誤：a = a + i在句末加上;后解決該行問題5)、第五處錯(cuò)誤：while(x<=)改為 while(x <= i) 6)、第六處錯(cuò)誤：C=a+b+(x*y;改為 C=a+b+(x*y);7)、第七處錯(cuò)誤：write c改為 write c;8)、第八處錯(cuò)誤：在程序末尾加上 9)、第九處錯(cuò)誤：在程序結(jié)尾加上 后解決了所有語法問題六、討

28、論與分析1、TEST語言中不滿足無回溯遞歸下降分析的語法規(guī)則有：第（2）、（4）、（14）、（15）、（16）這幾個(gè)語法規(guī)則。解決方案：將第（2）、（4）、（15）、（16）這幾條規(guī)則改為右遞歸；對(duì)第（14）條語法規(guī)則提取左公因子。2、不是所有文法都可以滿足遞歸下降分析條件，如：GS:SAU|BRAaAU|bBaBR|bUcRd對(duì)于規(guī)則SAU|BR，因?yàn)镕IRST(AU) FIRST(BR) ，所以該文法不是LL(1)文法。將A、B的產(chǎn)生式代入S的產(chǎn)生式,得到：SaAUU|bU|aBRR|bR，提取公因子后得到：Sa(AUU|BRR)|b(U|R)，令S1AUU|BRR,S2U|R，則得到如下

29、文法：SaS1|bS2S1AUU|BRRS2U|RAaAU|bBaBR|bUcRd對(duì)于規(guī)則S1AUU|BRR,因?yàn)镕IRST(AUU) FIRST(BRR) ,所以它不是LL(1)文法，無論重復(fù)多少次都不能把它變?yōu)長(zhǎng)L（1）文法。3、改寫文法有什么弊端？遞歸算法的實(shí)現(xiàn)效率低，處理能力相對(duì)有限，通用性差，難以自動(dòng)生成。七、自我評(píng)價(jià)本次實(shí)驗(yàn)自我感覺良好，獨(dú)立完成了程序。對(duì)于規(guī)則（13）我參考了教材71頁的設(shè)計(jì)方法，但是這一頁的這個(gè)程序存在著一個(gè)小錯(cuò)誤。最終的測(cè)試結(jié)果和我預(yù)想的并沒有差別?？偟膩碚f這是一次很有意義的實(shí)驗(yàn)。但是代碼本身卻可以有優(yōu)化，我對(duì)每一個(gè)表達(dá)式都設(shè)置了返回值。所以遇到錯(cuò)誤就會(huì)停止分

30、析。不會(huì)一次性把所有錯(cuò)誤都顯示出來，需要改錯(cuò)后再運(yùn)行詞法分析，然后再語法分析。在這一點(diǎn)上是不人性化的。每一次實(shí)驗(yàn)都是對(duì)理論知識(shí)的復(fù)習(xí)和鞏固。通過這一次試驗(yàn)我也發(fā)現(xiàn)了自身存在很多的不足。八、關(guān)鍵代碼：/語法分析程序的入口int TESTgrammar() int flag = 0; if(file = fopen(scanout,"r") = NULL) printf("nOpen file %s error!n",scanout); flag = 1; if(flag = 0) flag = program(); fclose(file); return

31、 flag;<statement>語法規(guī)則：int statement() int flag = 0; if(strcmp(buff_0,"if") = 0) flag = if_stat(); else if(strcmp(buff_0,"while") = 0) flag = while_stat(); else if(strcmp(buff_0,"for") = 0) flag = for_stat(); else if(strcmp(buff_0,"read") = 0) flag = read

32、_stat(); else if(strcmp(buff_0,"write") = 0) flag = write_stat(); else if(strcmp(buff_0,"") = 0) flag = compound_stat(); else if(strcmp(buff_0,"") = 0) | (strcmp(buff_0,"ID") = 0) |(strcmp(buff_0,"NUM") = 0) | (strcmp(buff_0,"(") = 0) flag

33、= expression_stat(); else printf("%dterror: expected 'reserved words' nt or 'delimiter' or 'ID' or 'NUM' before '%s'n",line,buff_1); return 1; return flag;對(duì)于改造文法列舉其中一個(gè)：/*<declaration_list> := <declaration_list><declaration_stat>|消除左

34、遞歸后得到<declaration_list> := <declaration_list1><declaration_list1> := <declaration_stat><declaration_list1>|*/int declaration_list() int flag = 0; if(strcmp(buff_0,"int") = 0) flag = declaration_list1(); return flag; else printf("%dterror: expected 'in

35、t' before '%s'n",line,buff_1); return 1; /<declaration_list1><declaration_stat><declaration_list1>|int declaration_list1() int flag = 0; if(strcmp(buff_0,"int") = 0) flag = declaration_stat(); if(flag > 0) return 1; flag = declaration_list1(); return f

36、lag; else if(strcmp(buff_0,"if") = 0 | strcmp(buff_0,"while") = 0 | strcmp(buff_0,"for") = 0 | strcmp(buff_0,"read") = 0 | strcmp(buff_0,"write") = 0 | strcmp(buff_0,"") = 0 | strcmp(buff_0,"") = 0 | strcmp(buff_0,"") = 0 | strcmp(buff_0,"ID") = 0 | strcmp(buff_0,"("