編譯原理實(shí)驗(yàn)指導(dǎo)書

1、編譯原理實(shí)驗(yàn)指導(dǎo)書華中農(nóng)業(yè)大學(xué)理學(xué)院計(jì)算機(jī)系實(shí)驗(yàn)一 詞法分析程序一實(shí)驗(yàn)?zāi)康模簶?gòu)造C-Minus語言的詞法分析程序，程序要求能對(duì)輸入的字符串流進(jìn)行詞法分析。在實(shí)驗(yàn)的過程中，學(xué)會(huì)應(yīng)用單詞分析的方法NFA（非確定有窮自動(dòng)機(jī)）和DFA（確定有窮自動(dòng)機(jī)）。二、實(shí)驗(yàn)內(nèi)容：編寫為任一正則文法（見實(shí)驗(yàn)參考（一）C-Minus慣用的詞法）構(gòu)造非確定有窮自動(dòng)機(jī)NFA并轉(zhuǎn)換成確定有窮自動(dòng)機(jī)DFA，并對(duì)任給的一個(gè)輸入串（見實(shí)驗(yàn)參考（二）測試用輸入串）進(jìn)行詞法分析的程序，程序的輸出為單詞的序列（見實(shí)驗(yàn)參考（三）程序輸出形式）。三、實(shí)驗(yàn)參考：（一）C-Minus 慣用的詞法1. 下面是語言的關(guān)鍵字：else if int

2、 return void while所有的關(guān)鍵字都是保留字，并且必須是小寫。2. 下面是專用符號(hào)：+ - * / < <= > >= = != = ; , ( ) /* */及各種復(fù)合賦值運(yùn)算符。3. 其他標(biāo)記是ID和NUM，通過下列正則表達(dá)式定義：ID = letter letter*NUM = digit digit*letter = a | . | z | A | . | Zdigit = 0 | . | 9小寫和大寫字母是有區(qū)別的。 思考：構(gòu)造實(shí)數(shù)的正規(guī)表達(dá)式，力爭實(shí)現(xiàn)對(duì)實(shí)數(shù)的識(shí)別及表示。4. 空格由空白、換行符和制表符組成。5. 注釋用通常的C語言符號(hào)/ *

3、. . . * /圍起來。注釋可以放在任何空白出現(xiàn)的位置（即注釋不能放在標(biāo)記內(nèi)）上，且可以超過一行。注釋不能嵌套。（二）測試用輸入串測試用輸入串為輸入兩個(gè)整數(shù)，計(jì)算并輸出它們的最大公因子的程序。int max_factor( int p , int q ) if (q =0) return p;else return max_factor( q , p - p / q * q );/* p - p / q * q = p mod q */void main(void)int x; int y;x=input(); y=input();output( max_factor( x , y ) )（

4、三）程序輸出形式1. 單詞的分類可將所有標(biāo)識(shí)符歸為一類；將常數(shù)歸為另一類；保留字和分隔符則可采取一詞一類。2. 符號(hào)表的建立可事先建立一保留字表，以備在識(shí)別保留字時(shí)進(jìn)行查詢。變量名表及常數(shù)表則在詞法分析過程中建立。3. 程序的輸出形式為單詞串的輸出形式。所輸出的每一單詞，均按形如（CLASS，VALUE）的二元式編碼。對(duì)于變量標(biāo)識(shí)符和常數(shù)，CLASS字段為相應(yīng)的類別碼，VALUE字段則是該標(biāo)識(shí)符、常數(shù)在其符號(hào)表中登記項(xiàng)的序號(hào)。四、實(shí)驗(yàn)擴(kuò)充構(gòu)造C-Minus語言的詞法分析程序，要求識(shí)別出變量類型并記錄相關(guān)信息。五、實(shí)驗(yàn)說明：1時(shí)間安排：第4章“詞法分析”后。2實(shí)驗(yàn)環(huán)境：WINDOWS下，工具為T

5、urbo C2.0或Visual C 6.0六、實(shí)驗(yàn)考核方式：1提交實(shí)驗(yàn)報(bào)告2演示程序和答辯（抽查）實(shí)驗(yàn)二 遞歸下降語法分析一、實(shí)驗(yàn)?zāi)康臉?gòu)造文法的語法分析程序，要求采用遞歸下降語法分析方法對(duì)輸入的字符串進(jìn)行語法分析，進(jìn)一步掌握遞歸下降的語法分析方法。二、實(shí)驗(yàn)內(nèi)容編寫為一上下文無關(guān)文法構(gòu)造其遞歸下降語法分析程序，并對(duì)任給的一個(gè)輸入串進(jìn)行語法分析檢查。程序要求能對(duì)輸入串進(jìn)行遞歸下降語法分析，能判別程序是否符合已知的語法規(guī)則，如果不符合（編譯出錯(cuò)），則輸出錯(cuò)誤信息。三、實(shí)驗(yàn)參考：算法思想為每個(gè)非終結(jié)符設(shè)計(jì)一個(gè)識(shí)別的子程序，尋找該非終結(jié)符也就是調(diào)用相應(yīng)的子程序。由于單詞在語法分析中作為一個(gè)整體，故在語

6、法識(shí)別中僅使用其內(nèi)碼。在這里將詞法分析作為語法分析的一個(gè)子程序，當(dāng)語法分析需要單詞時(shí)，就調(diào)用相應(yīng)的詞法分析程序獲得一個(gè)單詞。語法分析的作用是識(shí)別輸入符號(hào)串是否是文法上定義的句子，即判斷輸入符號(hào)串是否是滿足“程序”定義的要求。也就是當(dāng)語法識(shí)別程序從正常退出表示輸入符號(hào)串是正確的“程序”；若從出錯(cuò)退出，則輸入符號(hào)串不是正確的“程序”。出錯(cuò)時(shí)，可以根據(jù)讀字符的位置判斷出錯(cuò)的位置。四、實(shí)驗(yàn)擴(kuò)充根據(jù)C-Minus的語法，構(gòu)造C-Minus語言的遞歸下降語法分析程序，任意輸入一個(gè)符號(hào)串，并判斷它是否為文法的一個(gè)句子。C-Minus的BNF語法如下：1. program declaration-list2.

7、 declaration-list declaration-list declaration | declaration3. declaration var-declaration | fun-declaration4. var-declaration type-specifier ID ; | type-specifier ID NUM ;5. type-specifier int | void6. fun-declaration type-specifier ID ( params ) | compound-stmt7. params params-list | void8. param-

8、list param-list , param | param9. param type-specifier ID | type-specifier ID 10. compound-stmt local-declarations statement-list 11. local-declarations local-declarations var-declaration | empty12. statement-list statement-list statement | empty13. statement expression-stmt | compound-stmt | select

9、ion-stmt | iteration-stmt | return-stmt14. expression-stmt expression ; | ;15. selection-stmt if ( expression ) statement | if ( expression ) statement else statement16. iteration-stmt while(expression) statement17. return-stmt return ; | return expression ;18. expression var = expression | simple-e

10、xpression19. var ID | ID expression 20. simple-expression additive-expression relop additive-expression | additive-expression21. relop <= | < | > | >= | = | !=22. additive-expression additive-expression addop term | term23. addop + | -24. term term mulop factor | factor25. mulop * | /26.

11、 factor ( expression ) | var | call | NUM27. call ID ( args )28. args arg-list | empty29. arg-list arg-list , expression | expression五、實(shí)驗(yàn)說明：1時(shí)間安排：安排在“詞法分析”后。2實(shí)驗(yàn)環(huán)境：WINDOWS下，工具為Turbo C2.0或Visual C 6.0六、實(shí)驗(yàn)考核方式：1提交實(shí)驗(yàn)報(bào)告2演示程序和答辯（抽查）實(shí)驗(yàn)三 LL(1)語法分析 一實(shí)驗(yàn)?zāi)康臉?gòu)造某一文法的語法分析程序，要求采用LL(1)語法分析方法對(duì)輸入的字符串進(jìn)行語法分析，進(jìn)一步掌握LL(1)語法

12、分析方法，以及它和遞歸下降子程序法的聯(lián)系和區(qū)別。二、實(shí)驗(yàn)內(nèi)容編寫為某一任意上下文無關(guān)文法構(gòu)造的遞歸下降語法分析程序，并對(duì)任給的一個(gè)輸入串進(jìn)行語法分析檢查。程序要求為該文法構(gòu)造預(yù)測分析表，并按照預(yù)測分析算法對(duì)輸入串進(jìn)行語法分析，判別程序是否符合已知的語法規(guī)則，如果不符合（編譯出錯(cuò)），則輸出錯(cuò)誤信息。三、實(shí)驗(yàn)參考LL(1)分析器的總控算法開 始j1，S1#，S2識(shí)別符chstrjTOP(S)VT?TOP(S)=ch?TOP(S)=#?ii-1, jj+1chstrjMTOP(S), ch=U=x1x2xn?用xnxn-1x1替換棧頂U(kuò)errorSTOPNOKSTOPYerrorSTOPNNYYYN

13、四、實(shí)驗(yàn)擴(kuò)充構(gòu)造C-Minus語言的LL(1)語法分析程序，任意輸入一個(gè)符號(hào)串，并判斷它是否為文法的一個(gè)句子。五、實(shí)驗(yàn)說明：1時(shí)間安排：第4章“詞法分析”后。2實(shí)驗(yàn)環(huán)境：WINDOWS下，工具為Turbo C2.0或Visual C 6.0六、實(shí)驗(yàn)考核方式：1提交實(shí)驗(yàn)報(bào)告2演示程序和答辯（抽查）實(shí)驗(yàn)四 自底下上語法分析-簡單優(yōu)先分析方法一實(shí)驗(yàn)?zāi)康臉?gòu)造某一文法的語法分析程序，要求采用簡單優(yōu)先的語法分析方法對(duì)輸入的字符串進(jìn)行語法分析，進(jìn)一步掌握簡單優(yōu)先語法分析方法。 二、實(shí)驗(yàn)內(nèi)容：編寫為某上下文無關(guān)文法構(gòu)造的簡單優(yōu)先語法分析程序，并對(duì)任給的一個(gè)輸入串進(jìn)行語法分析檢查。程序要求為該文法構(gòu)造簡單優(yōu)先關(guān)

14、系矩陣，并按照簡單優(yōu)先分析算法對(duì)輸入串進(jìn)行語法分析，判別輸入串是否符合已知的語法規(guī)則，如果不符合（編譯出錯(cuò)），則輸出錯(cuò)誤信息。三、實(shí)驗(yàn)參考：簡單優(yōu)先分析算法開 始S1#，i, j1kiSiTRj?MSi, TRj=error?YSk-1>Sk?=SkSk+1Si是句柄，用它查產(chǎn)生式表Y與一產(chǎn)生式右部相同：Si=#且 TRj=#？NYOK結(jié) 束NerrorikSiUU是該產(chǎn)生式左部符號(hào)YerrorNii+1SiTRjjj+1Nkk-1四、實(shí)驗(yàn)說明：1時(shí)間安排：第7章“語法分析”后。2實(shí)驗(yàn)環(huán)境：WINDOWS下，工具為Turbo C2.0或Visual C 6.0 五、實(shí)驗(yàn)考核方式：1提交實(shí)

15、驗(yàn)報(bào)告2演示程序和答辯（抽查）實(shí)驗(yàn)五 自底下上語法分析-算符優(yōu)先分析方法一實(shí)驗(yàn)?zāi)康臉?gòu)造某一文法的語法分析程序，要求采用算符優(yōu)先的語法分析方法對(duì)輸入的字符串進(jìn)行語法分析，進(jìn)一步掌握算符優(yōu)先的語法分析方法。 二、實(shí)驗(yàn)內(nèi)容：編寫為某上下文無關(guān)文法構(gòu)造的簡單優(yōu)先語法分析程序，并對(duì)任給的一個(gè)輸入串進(jìn)行語法分析檢查。程序要求為該文法構(gòu)造簡單優(yōu)先關(guān)系矩陣，并按照簡單優(yōu)先分析算法對(duì)輸入串進(jìn)行語法分析，判別輸入串是否符合已知的語法規(guī)則，如果不符合（編譯出錯(cuò)），則輸出錯(cuò)誤信息。三、實(shí)驗(yàn)參考：算符優(yōu)先分析算法開 始S1#，j1，k1SjVT?ijYij-1Sj>TRk?NPSi，ii-1YSj> VT?

16、ii-1NSi<P?YNYSi+1Sj為最左素短語ji+1, SjVj=2且 TRk=#?YS2是開始符？Y待查符號(hào)串是句子結(jié) 束待查符號(hào)串不是句子NNjj+1SjTRkkk+1N四、實(shí)驗(yàn)說明：1時(shí)間安排：安排在“語法分析”后。2實(shí)驗(yàn)環(huán)境：WINDOWS下，工具為Turbo C2.0或Visual C 6.0 五、實(shí)驗(yàn)考核方式：1提交實(shí)驗(yàn)報(bào)告2演示程序和答辯（抽查）實(shí)驗(yàn)六 語義分析一實(shí)驗(yàn)?zāi)康模簶?gòu)造C-Minus語言的語義分析程序，程序要求能對(duì)輸入的字符串流進(jìn)行靜態(tài)語義分析。在實(shí)驗(yàn)的過程中，學(xué)會(huì)應(yīng)用語義分析的方法。二、實(shí)驗(yàn)內(nèi)容：編寫為任一屬性文法（見實(shí)驗(yàn)參考（一）C-Minus的語義）構(gòu)造

17、語義分析程序，并對(duì)任給的一個(gè)輸入串（見實(shí)驗(yàn)參考（二）測試用輸入串）進(jìn)行語義分析檢查。要求對(duì)輸入串進(jìn)行語義分析，包括建立符號(hào)表、作用域檢查和類型檢查等幾個(gè)部分，且輸出錯(cuò)誤信息。三、實(shí)驗(yàn)參考：（一）C-Minus的語義對(duì)C-Minus的語法的每條文法規(guī)則，給出了相關(guān)語義的簡短解釋。1. program declaration-list2. declaration-list declaration-list declaration | declaration3. declaration var-declaration | fun-declaration程序由聲明序列組成。聲明可以是函數(shù)或變量聲明，順

18、序是任意的，且程序中至少有一個(gè)聲明。所有的變量和函數(shù)在使用前必須聲明，這是語義限制。程序中最后一個(gè)聲明必須是main函數(shù)聲明。C-Minus中聲明和定義之間沒有區(qū)別。4. var-declaration type-specifier ID ; | type-specifier ID NUM ;5. type-specifier int | void在C-Minus中基本類型只有整型和空類型。int類型用于變量聲明；void用于函數(shù)聲明。每個(gè)聲明只能針對(duì)一個(gè)變量聲明。整型的數(shù)組變量，索引范圍從0到NUM-1。6. fun-declaration type-specifier ID ( param

19、s ) compound-stmt7. params param-list | void8. param-list param-list , param | param9. param type-specifier ID | type-specifier ID 函數(shù)聲明由返回類型指示符、標(biāo)識(shí)符以及在圓括號(hào)內(nèi)的用逗號(hào)分開的參數(shù)列表組成，后面跟著一個(gè)復(fù)合語句，是函數(shù)的代碼。如果函數(shù)的返回類型是void，那么函數(shù)不返回任何值（即是一個(gè)過程）。函數(shù)的參數(shù)可以是void（即沒有參數(shù)），或者一列描述函數(shù)的參數(shù)。參數(shù)后面跟著方括號(hào)是數(shù)組參數(shù)，其大小是可變的。簡單的整型參數(shù)由值傳遞。數(shù)組參數(shù)由指針來傳遞，在調(diào)

20、用時(shí)必須通過數(shù)組變量來匹配。一個(gè)函數(shù)參數(shù)的作用域等于函數(shù)聲明的復(fù)合語句，函數(shù)的每次請(qǐng)求都有一個(gè)獨(dú)立的參數(shù)集。函數(shù)可以是遞歸的。10. compound-stmt local-declarations statement-list 復(fù)合語句由用花括號(hào)圍起來的一組聲明和語句組成。復(fù)合語句通過用給定的順序執(zhí)行語句序列來執(zhí)行。局部聲明的作用域等于復(fù)合語句的語句列表，并代替任何全局聲明。11. local-declarations local-declarations var-declaration | empty12. statement-list statement-list statement |

21、 empty聲明和語句列表都可以是空的（非終結(jié)符empty表示空字符串，也可記為）。13. statement expression-stmt | compound-stmt | selection-stmt | iteration-stmt | return-stmt14. expression-stmt expression ; | ;表達(dá)式語句有可用于賦值和函數(shù)調(diào)用。15. selection-stmt if (expression) statement | if (expression) statement else statementif語句的語義：表達(dá)式的值為真時(shí)，第一條語句執(zhí)行；

22、為假則第二條語句執(zhí)行。此規(guī)則導(dǎo)致了典型的else二義性，其解決方法：else部分通常作為當(dāng)前if的一個(gè)子結(jié)構(gòu)立即分析（“最近嵌套”非二義性規(guī)則）。16. iteration-stmt while ( expression ) statementwhile語句是C-Minus中唯一的循環(huán)語句。如果表達(dá)式的求值為真時(shí)，重復(fù)執(zhí)行語句；為假時(shí)則結(jié)束。17. return-stmt return ; | return expression ;返回語句可以有，也可無返回值。函數(shù)聲明為void時(shí)，沒有返回值。return控制語句返回。18. expression var = expression | sim

23、ple-expression19. var ID | ID expression 表達(dá)式是由變量、賦值符號(hào)（等號(hào)）和表達(dá)式組成，或者就是一個(gè)簡單的表達(dá)式組成。var是簡單的（整型）變量或下標(biāo)數(shù)組變量。C-Minus不進(jìn)行下標(biāo)越界檢查，負(fù)的下標(biāo)將引起程序停止，且指針運(yùn)算是禁止的。20. simple-expression additive-expression relop additive-expression | additive-expression21. relop <= | < | > | >= | = | !=簡單表達(dá)式由無結(jié)合的關(guān)系操作符組成（即無括號(hào)的表達(dá)式僅有一個(gè)關(guān)系操作符）。簡單表達(dá)式在它不包含關(guān)系操作符時(shí)，其值是加法表達(dá)式的值，如果關(guān)系算式求值為ture，其值為1，求值為false時(shí)值為0。22. additive-expression additive-expression addop term | term23. addop + | -24. term term mulop factor | factor25. mulop * | /加法表達(dá)式和項(xiàng)表示了算術(shù)操作符的結(jié)合性和優(yōu)先級(jí)。26. factor ( expression ) | var | call | NUM因子是括號(hào)內(nèi)的表達(dá)式的值；變