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

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

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

3、. . . * /圍起來(lái)。注釋可以放在任何空白出現(xiàn)的位置（即注釋不能放在標(biāo)記內(nèi)）上，且可以超過(guò)一行。注釋不能嵌套。（二）測(cè)試用輸入串測(cè)試用輸入串為輸入兩個(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. 單詞的分類(lèi)可將所有標(biāo)識(shí)符歸為一類(lèi)；將常數(shù)歸為另一類(lèi)；保留字和分隔符則可采取一詞一類(lèi)。2. 符號(hào)表的建立可事先建立一保留字表，以備在識(shí)別保留字時(shí)進(jìn)行查詢(xún)。變量名表及常數(shù)表則在詞法分析過(guò)程中建立。3. 程序的輸出形式為單詞串的輸出形式。所輸出的每一單詞，均按形如（CLASS，VALUE）的二元式編碼。對(duì)于變量標(biāo)識(shí)符和常數(shù)，CLASS字段為相應(yīng)的類(lèi)別碼，VALUE字段則是該標(biāo)識(shí)符、常數(shù)在其符號(hào)表中登記項(xiàng)的序號(hào)。四、實(shí)驗(yàn)擴(kuò)充構(gòu)造C-Minus語(yǔ)言的詞法分析程序，要求識(shí)別出變量類(lèi)型并記錄相關(guān)信息。五、實(shí)驗(yàn)說(shuō)明：1時(shí)間安排：第4章“詞法分析”后。2實(shí)驗(yàn)環(huán)境：WINDOWS下，工具為T(mén)

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

6、法識(shí)別中僅使用其內(nèi)碼。在這里將詞法分析作為語(yǔ)法分析的一個(gè)子程序，當(dāng)語(yǔ)法分析需要單詞時(shí)，就調(diào)用相應(yīng)的詞法分析程序獲得一個(gè)單詞。語(yǔ)法分析的作用是識(shí)別輸入符號(hào)串是否是文法上定義的句子，即判斷輸入符號(hào)串是否是滿(mǎn)足“程序”定義的要求。也就是當(dāng)語(yǔ)法識(shí)別程序從正常退出表示輸入符號(hào)串是正確的“程序”；若從出錯(cuò)退出，則輸入符號(hào)串不是正確的“程序”。出錯(cuò)時(shí)，可以根據(jù)讀字符的位置判斷出錯(cuò)的位置。四、實(shí)驗(yàn)擴(kuò)充根據(jù)C-Minus的語(yǔ)法，構(gòu)造C-Minus語(yǔ)言的遞歸下降語(yǔ)法分析程序，任意輸入一個(gè)符號(hào)串，并判斷它是否為文法的一個(gè)句子。C-Minus的BNF語(yǔ)法如下：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)說(shuō)明：1時(shí)間安排：安排在“詞法分析”后。2實(shí)驗(yàn)環(huán)境：WINDOWS下，工具為T(mén)urbo C2.0或Visual C 6.0六、實(shí)驗(yàn)考核方式：1提交實(shí)驗(yàn)報(bào)告2演示程序和答辯（抽查）實(shí)驗(yàn)三 LL(1)語(yǔ)法分析 一實(shí)驗(yàn)?zāi)康臉?gòu)造某一文法的語(yǔ)法分析程序，要求采用LL(1)語(yǔ)法分析方法對(duì)輸入的字符串進(jìn)行語(yǔ)法分析，進(jìn)一步掌握LL(1)語(yǔ)法

12、分析方法，以及它和遞歸下降子程序法的聯(lián)系和區(qū)別。二、實(shí)驗(yàn)內(nèi)容編寫(xiě)為某一任意上下文無(wú)關(guān)文法構(gòu)造的遞歸下降語(yǔ)法分析程序，并對(duì)任給的一個(gè)輸入串進(jìn)行語(yǔ)法分析檢查。程序要求為該文法構(gòu)造預(yù)測(cè)分析表，并按照預(yù)測(cè)分析算法對(duì)輸入串進(jìn)行語(yǔ)法分析，判別程序是否符合已知的語(yǔ)法規(guī)則，如果不符合（編譯出錯(cuò)），則輸出錯(cuò)誤信息。三、實(shí)驗(yàn)參考LL(1)分析器的總控算法開(kāi) 始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語(yǔ)言的LL(1)語(yǔ)法分析程序，任意輸入一個(gè)符號(hào)串，并判斷它是否為文法的一個(gè)句子。五、實(shí)驗(yàn)說(shuō)明：1時(shí)間安排：第4章“詞法分析”后。2實(shí)驗(yàn)環(huán)境：WINDOWS下，工具為T(mén)urbo C2.0或Visual C 6.0六、實(shí)驗(yàn)考核方式：1提交實(shí)驗(yàn)報(bào)告2演示程序和答辯（抽查）實(shí)驗(yàn)四 自底下上語(yǔ)法分析-簡(jiǎn)單優(yōu)先分析方法一實(shí)驗(yàn)?zāi)康臉?gòu)造某一文法的語(yǔ)法分析程序，要求采用簡(jiǎn)單優(yōu)先的語(yǔ)法分析方法對(duì)輸入的字符串進(jìn)行語(yǔ)法分析，進(jìn)一步掌握簡(jiǎn)單優(yōu)先語(yǔ)法分析方法。 二、實(shí)驗(yàn)內(nèi)容：編寫(xiě)為某上下文無(wú)關(guān)文法構(gòu)造的簡(jiǎn)單優(yōu)先語(yǔ)法分析程序，并對(duì)任給的一個(gè)輸入串進(jìn)行語(yǔ)法分析檢查。程序要求為該文法構(gòu)造簡(jiǎn)單優(yōu)先關(guān)

14、系矩陣，并按照簡(jiǎn)單優(yōu)先分析算法對(duì)輸入串進(jìn)行語(yǔ)法分析，判別輸入串是否符合已知的語(yǔ)法規(guī)則，如果不符合（編譯出錯(cuò)），則輸出錯(cuò)誤信息。三、實(shí)驗(yàn)參考：簡(jiǎn)單優(yōu)先分析算法開(kāi) 始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)說(shuō)明：1時(shí)間安排：第7章“語(yǔ)法分析”后。2實(shí)驗(yàn)環(huán)境：WINDOWS下，工具為T(mén)urbo C2.0或Visual C 6.0 五、實(shí)驗(yàn)考核方式：1提交實(shí)

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

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

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

18、序是任意的，且程序中至少有一個(gè)聲明。所有的變量和函數(shù)在使用前必須聲明，這是語(yǔ)義限制。程序中最后一個(gè)聲明必須是main函數(shù)聲明。C-Minus中聲明和定義之間沒(méi)有區(qū)別。4. var-declaration type-specifier ID ; | type-specifier ID NUM ;5. type-specifier int | void在C-Minus中基本類(lèi)型只有整型和空類(lèi)型。int類(lèi)型用于變量聲明；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ù)聲明由返回類(lèi)型指示符、標(biāo)識(shí)符以及在圓括號(hào)內(nèi)的用逗號(hào)分開(kāi)的參數(shù)列表組成，后面跟著一個(gè)復(fù)合語(yǔ)句，是函數(shù)的代碼。如果函數(shù)的返回類(lèi)型是void，那么函數(shù)不返回任何值（即是一個(gè)過(guò)程）。函數(shù)的參數(shù)可以是void（即沒(méi)有參數(shù)），或者一列描述函數(shù)的參數(shù)。參數(shù)后面跟著方括號(hào)是數(shù)組參數(shù)，其大小是可變的。簡(jiǎn)單的整型參數(shù)由值傳遞。數(shù)組參數(shù)由指針來(lái)傳遞，在調(diào)

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

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

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

23、ple-expression19. var ID | ID expression 表達(dá)式是由變量、賦值符號(hào)（等號(hào)）和表達(dá)式組成，或者就是一個(gè)簡(jiǎn)單的表達(dá)式組成。var是簡(jiǎn)單的（整型）變量或下標(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 <= | < | > | >= | = | !=簡(jiǎn)單表達(dá)式由無(wú)結(jié)合的關(guān)系操作符組成（即無(wú)括號(hào)的表達(dá)式僅有一個(gè)關(guān)系操作符）。簡(jiǎ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á)式的值；變