編譯原理課程實(shí)驗(yàn)指導(dǎo)書-PL0語言及其編譯器

1、編譯原理編譯原理課程實(shí)驗(yàn)指導(dǎo)書課程實(shí)驗(yàn)指導(dǎo)書（Compiler Principle） 1目錄目錄序言序言.1一、實(shí)驗(yàn)安排一、實(shí)驗(yàn)安排.2第一階段：編譯器的詞法分析第一階段：編譯器的詞法分析.2第二階段：編譯器的語法分析第二階段：編譯器的語法分析.2第三階段：編譯器的代碼生成第三階段：編譯器的代碼生成.3二、考核方式及評定標(biāo)準(zhǔn)二、考核方式及評定標(biāo)準(zhǔn).4三、參考資料與編譯器分析三、參考資料與編譯器分析.4第一部分第一部分 PL 語言及其編譯器語言及其編譯器.41. PL 語言介紹 .41.1 PL 語言的語法圖.52. PL 語言編譯器 .82.1 詞法分析.92.2 語法分析.92.3 語義分析

2、.112.4 代碼生成.112.5 代碼執(zhí)行.132.6 錯誤診斷處理.152.7 符號表管理.172.8 其他.18第二部分第二部分 上機(jī)實(shí)驗(yàn)要求上機(jī)實(shí)驗(yàn)要求.19第三部分第三部分 PL 語言編譯器源程序與示例語言編譯器源程序與示例.211示例與結(jié)果表示示例與結(jié)果表示.211.1 PL 語言源程序.211.2 生成的代碼（片段）.232. PL 語言編譯器源程序語言編譯器源程序.231序言序言本編譯原理實(shí)驗(yàn)，其目的是讓大家動手設(shè)計和實(shí)現(xiàn)一個規(guī)模適中的語言的編譯器，該編譯器不僅涉及編譯程序的各個階段，而且也強(qiáng)調(diào)了編譯的總體設(shè)計、各個階段的接口安排等等。通過上機(jī)實(shí)踐，來設(shè)計這個相對完整的編譯器，

3、一方面可以使同學(xué)們增加對編譯程序的整體認(rèn)識和了解鞏固編譯原理課程所學(xué)知識，另一方面，通過上機(jī)練習(xí)，學(xué)生也可以學(xué)到很多程序調(diào)試技巧和設(shè)計大型程序一般的原則，如模塊接口的協(xié)調(diào)，數(shù)據(jù)結(jié)構(gòu)的合理選擇等等。為了使學(xué)生能盡早動手實(shí)踐，我們建議把實(shí)踐分成三部分，首先閱讀本教程第一部分，在這部分就 PL 語言的語法及其編譯程序的各個階段作了簡單介紹，以便對 PL 編譯程序有個初步的印象。其次要認(rèn)真閱讀理解第三部分所給出的 PL編譯器源程序及示例，使上一階段的初步印象得以加深、具體化。最后按照第二部分的實(shí)驗(yàn)要求擴(kuò)充 PL 語言的功能并加以實(shí)現(xiàn)。具體操作時分成三個階段：詞法分析、語法分析及代碼生成。最后再統(tǒng)一組裝

4、成一個完整的 PL 編譯器，并適當(dāng)進(jìn)行改進(jìn)、補(bǔ)充。2一、實(shí)驗(yàn)安排一、實(shí)驗(yàn)安排第一階段：編譯器的詞法分析第一階段：編譯器的詞法分析學(xué)時：學(xué)時：2（一） 、實(shí)驗(yàn)?zāi)康模和ㄟ^閱讀 PL 的語法圖，設(shè)計、編制并調(diào)試一個 PL 詞法分析程序，加深對詞法分析原理的理解。（二） 、實(shí)驗(yàn)內(nèi)容：PL 的詞法分析器將要完成以下工作：（1）跳過分隔符（如空格，回車，制表符） ；（2）識別諸如 begin，end，if，while 等保留字；（3）識別非保留字的一般標(biāo)識符，此標(biāo)識符值（字符序列）賦給全局量 id，而全局量 sym 賦值為 SYM_IDENTIFIER。（4）識別數(shù)字序列，當(dāng)前值賦給全局量 NUM，sym

5、 則置為 SYM_NUMBER；（5）識別:=，=之類的特殊符號，全局量 sym 則分別被賦值為SYM_BECOMES，SYM_LEQ，SYM_GEQ 等。相關(guān)過程（函數(shù)）有 getsym()，getch()，其中 getch()為獲取單個字符的過程，除此之外，它還完成：（1）識別且跳過行結(jié)束符；（2）將輸入源文件復(fù)寫到輸出文件；（3）產(chǎn)生一份程序列表，輸出相應(yīng)行號或指令計數(shù)器的值。第二階段：編譯器的語法分析第二階段：編譯器的語法分析學(xué)時：學(xué)時：4（一） 、實(shí)驗(yàn)?zāi)康模赫莆?PL 語言編譯器的語法分析程序設(shè)計與 LL（1）文法應(yīng)用的實(shí)現(xiàn)方法。（二） 、實(shí)驗(yàn)內(nèi)容：采用遞歸下降的方法來設(shè)計 PL/0

6、 編譯器，證明 PL/0 語言屬于 LL（1）文法。然后結(jié)合語法圖編寫（遞歸下降）語法分析程序的一般方法，具體方面有：（1）用合適的替換將語法約化成盡可能少的單個圖；（2）將每一個圖按下面的規(guī)則（3）-（7）翻譯成一個過程說明；（3）順序圖對應(yīng)復(fù)合語句：（4）選擇：（5）循環(huán)（6）表示另一個圖 A 的圖：（7）表示終結(jié)符的單元圖：相關(guān)過程有：block(), constdeclaration(), vardeclaration(), statement(), condition(), expression(), term(), factor()等。并畫出它們之間依賴關(guān)系圖，并在此基礎(chǔ)上實(shí)現(xiàn)程序

7、的編制。3并適當(dāng)進(jìn)行語義分析的相關(guān)檢查：（1）是否存在標(biāo)識符先引用未聲明的情況；（2）是否存在己聲明的標(biāo)識符的錯誤引用；（3）是否存在一般標(biāo)識符的多重聲明。第三階段：編譯器的代碼生成第三階段：編譯器的代碼生成學(xué)時：學(xué)時：2（一） 、實(shí)驗(yàn)?zāi)康模赫莆?PL 語言編譯器的中間代碼生成的程序分析與實(shí)現(xiàn)方法，并能對錯誤進(jìn)行分析與處理。（二） 、實(shí)驗(yàn)內(nèi)容：為了使我們的編譯程序保持適當(dāng)簡單的水平，不致陷入與本課程無關(guān)的實(shí)際機(jī)器的特有性質(zhì)的考慮中去，我們假想有臺適合 PL 程序運(yùn)行的計算機(jī)，我們稱之為 PL 處理機(jī)。PL 處理機(jī)順序解釋生成的目標(biāo)代碼。PL 處理機(jī)的指令集根據(jù) PL 語言的要求而設(shè)計，它包括以

8、下的指令：（1）LIT /* 將常數(shù)置于棧頂 */（2）LOD /* 將變量值置于棧頂 */（3）STO /* 將棧頂?shù)闹蒂x與某變量 */（4）CAL /* 用于過程調(diào)用的指令 */（5）INT /* 在數(shù)據(jù)棧中分配存貯空間 */（6）JMP, JPC /* 用于 if, while 語句的條件或無條件控制轉(zhuǎn)移指令 */（7）OPR /* 一組算術(shù)或邏輯運(yùn)算指令 */上述指令的格式由三部分組成：FLA其中，f, l, a 的含義見下表：FLaINT常 量LIT常 量LOD層次差數(shù)據(jù)地址STO層次差數(shù)據(jù)地址CAL層次差程序地址JMP程序地址JPC程序地址OPR運(yùn)算類別PL 的編譯程序?yàn)槊恳粭l P

9、L 源程序的可執(zhí)行語句生成后綴式目標(biāo)代碼。另一方面，發(fā)現(xiàn)錯誤，并給出合適的診斷信息且繼續(xù)編譯下去從而發(fā)現(xiàn)更多的錯誤，對于編譯程序而言是完全必要的。結(jié)合關(guān)鍵字規(guī)則、鎮(zhèn)定規(guī)則，采用策略：先用一些明顯的關(guān)鍵符號給它賦初值，然后隨著分析子目標(biāo)的層次深入，逐步補(bǔ)充別的合法符號。并編寫子程序去驗(yàn)證之。表 1 PL 處理機(jī)指令4二、考核方式及評定標(biāo)準(zhǔn)二、考核方式及評定標(biāo)準(zhǔn)上機(jī)實(shí)驗(yàn)要求對 PL 語言及其編譯器進(jìn)行實(shí)現(xiàn)及擴(kuò)充、修改。每個擴(kuò)充或修改方式可得到不同的分?jǐn)?shù)，滿分為 100 分。完成上機(jī)作業(yè)后，必須提交下列文檔：（1） 修改后的 PL 語言文本。包含詞法分析（正規(guī)式） ，語法分析（BNF） 。（2） 有

10、關(guān)修改后的 PL 編譯/解釋器的說明。詳細(xì)說明編譯器是如何編譯新的 PL 語言程序的。指出程序中最精彩的部分，以及為什么這樣做，如何控制和恢復(fù)語義錯誤的。（3） 給出改動后的編譯器源程序清單，并標(biāo)記出所修改的部分。比較你的編譯器和原來的編譯器之間的差別。（4） 說明你的編譯器中可能存在的錯誤。（5） 總結(jié)經(jīng)驗(yàn)與教訓(xùn)，如果重做一遍，會有哪些新的改進(jìn)？對現(xiàn)存的 PL 編譯程序做如下修改或擴(kuò)充，其中（1） 、 （2） 、 （11）和（12）必須完成，剩余的均可任意選擇，但總分必須超過 40 分。（1） 注釋（5 分）（2） 布爾類型的數(shù)據(jù)（10 分）（3） 布爾表達(dá)式的短路計算（5 分）（4） 數(shù)組

11、（10 分）為了便于解釋執(zhí)行，可能要增加新的 PL 機(jī)器操作指令。（5） 參數(shù)（10 分） 語法同 Pascal（不用 var 聲明） 。（6） 函數(shù)（10 分）語法同 Pascal。 （7） else 子句和 repeat 語句（5 分）（8） for 語句，語法參照 Pascal 或 C 語言（5 分）（9） exit 語句和 break 語句（5 分）（10）記錄（結(jié)構(gòu)）,語法同 Pascal 語言（10 分） 。（11）更有力的語法錯誤恢復(fù)機(jī)制（20 分）（12）分離解釋和編譯器（5 分）三、參考資料與編譯器分析三、參考資料與編譯器分析第一部分第一部分 PL 語言及其編譯器語言及其編譯

12、器1. PL 語言介紹語言介紹PL 程序設(shè)計語言是一個較簡單的語言，它以賦值語句為基礎(chǔ)，構(gòu)造概念有順序、條件和重復(fù)（循環(huán)）三種。PL 有子程序概念，包括過程定義（可以嵌套）與調(diào)用且有局部變量說明。PL 中唯一的數(shù)據(jù)類型是整型，可以用來說明該類型的常量和變量。當(dāng)然 PL 也具有通常的算術(shù)運(yùn)算和關(guān)系運(yùn)算。具體的 PL 語法圖如下。51.1 PLPL 語言的語法圖語言的語法圖程序程序程序體程序體語句序列語句序列程序體.constidentnumber=var;identprocedure,ident;程序體;語句語句;,6語句語句條件條件表達(dá)式表達(dá)式項(xiàng)項(xiàng)identcallbeginwhileendi

13、dent:=ifdothen語句語句表達(dá)式語句序列條件條件表達(dá)式odd表達(dá)式=表達(dá)式項(xiàng)項(xiàng)+-+7因子因子因子因子/*identnumber表達(dá)式()82. PL 語言編譯器語言編譯器本書所提供的 PL 語言編譯器的基本工作流程如圖 1-1 所示：語法分析詞法分析語義分析代碼生成代碼執(zhí)行源程序執(zhí)行結(jié)果符號表管理錯誤診斷處理圖 1-1 PL 編譯器基本工作流程92.1 詞法分析詞法分析PL 的語言的詞法分析器將要完成以下工作：(1) 跳過分隔符（如空格，回車，制表符） ；(2) 識別諸如 begin，end，if，while 等保留字；(3) 識別非保留字的一般標(biāo)識符，此標(biāo)識符值（字符序列）賦給全

14、局量id，而全局量 sym 賦值為 SYM_IDENTIFIER。(4) 識別數(shù)字序列，當(dāng)前值賦給全局量 NUM，sym 則置為 SYM_NUMBER；(5) 識別:=，=之類的特殊符號，全局量 sym 則分別被賦值為SYM_BECOMES，SYM_LEQ，SYM_GEQ 等。相關(guān)過程（函數(shù)）有 getsym()，getch()，其中 getch()為獲取單個字符的過程，除此之外，它還完成：(1) 識別且跳過行結(jié)束符；(2) 將輸入源文件復(fù)寫到輸出文件；(3) 產(chǎn)生一份程序列表，輸出相應(yīng)行號或指令計數(shù)器的值。2.2 語法分析語法分析我們采用遞歸下降的方法來設(shè)計 PL 編譯器。以下我們給出該語言

15、的 FIRST和 FOLLOW 集合。非終結(jié)符（非終結(jié)符（S S）FIRST(S)FIRST(S)FOLLOW(S)FOLLOW(S)程序體const var procedure ident call if begin while. ;語句ident call begin if while. ; end條件odd + - ( ident numberthen do表達(dá)式+ - ( ident number. ; ) R end then do項(xiàng)ident number (. ; ) R + - end then do因子ident number (. ; ) R + - * / end the

16、n do注：表中 R 代表六個關(guān)系運(yùn)算符。不難證明，PL 語言屬于 LL（1）文法。 （證明從略。 ）以下是我們給出如何結(jié)合語法圖編寫（遞歸下降）語法分析程序的一般方法。假定圖 S 所對應(yīng)的程序段為 T（S） ，則：(1) 用合適的替換將語法約化成盡可能少的單個圖；(2) 將每一個圖按下面的規(guī)則（3）-（7）翻譯成一個過程說明；(3) 順序圖對應(yīng)復(fù)合語句：對應(yīng)：begin T(S1); T(S2); .; T(Sn) end(4)選擇：S1S2Sn10對應(yīng)：case 語句或者條件語句：case ch of if ch in L1 then T(S1) else L1: T(S1); if ch

17、 in L2 then T(S2) else L2: T(S2); 或 . if ch in Ln then T(Sn) elseLn: T(Sn); error其中 LiFIRST（Si） ，ch 為當(dāng)前輸入符號。 （下同）(5) 循環(huán)對應(yīng)：while ch in L do T(S)(6) 表示另一個圖 A 的圖：對應(yīng)：過程調(diào)用 A。(7) 表示終結(jié)符的單元圖：對應(yīng)：if ch = x then read(ch) else error相關(guān)過程有：block(), constdeclaration(), vardeclaration(), statement(), condition(), e

18、xpression(), term(), factor()等。它們之間依賴關(guān)系如圖 1-2：S1S2S3SAx112.3 語義分析語義分析PL 的語義分析主要進(jìn)行以下檢查：(1) 是否存在標(biāo)識符先引用未聲明的情況；(2) 是否存在己聲明的標(biāo)識符的錯誤引用；(3) 是否存在一般標(biāo)識符的多重聲明。2.4 代碼生成代碼生成PL 編譯程序不僅完成通常的詞法分析、語法分析，而且還產(chǎn)生中間代碼和“目標(biāo)”代碼。最終我們要“運(yùn)行”該目標(biāo)碼。為了使我們的編譯程序保持適當(dāng)簡單的水平，不致陷入與本課程無關(guān)的實(shí)際機(jī)器的特有性質(zhì)的考慮中去，我們假想有臺適合 PL 程序運(yùn)行的計算機(jī)，我們稱之為 PL 處理機(jī)。PL 處理機(jī)

19、順序解釋生成的目標(biāo)代碼，我們稱之為解釋程序。注意：這里的假設(shè)與我們的編譯概念并不矛盾，在本課程中我們寫的只是一個示范性的編譯程序，它的后端無法完整地實(shí)現(xiàn)，因而只能在一個解釋性的環(huán)境下予以模擬。從另一個角度上講，把解釋程序程序程序體語句條件表達(dá)式項(xiàng)因子圖 1-2 語法分析過程依賴關(guān)系12就看成是 PL 機(jī)硬件，把解釋執(zhí)行看成是 PL 的硬件執(zhí)行，那么我們所做的工作：由 PL 源語言程序到 PL 機(jī)器指令的變換，就是一個完整的編譯程序。PL 處理機(jī)有兩類存貯，目標(biāo)代碼放在一個固定的存貯數(shù)組 code 中，而所需數(shù)據(jù)組織成一個棧形式存放。PL 處理機(jī)的指令集根據(jù) PL 語言的要求而設(shè)計，它包括以下的

20、指令：（1）LIT /* 將常數(shù)置于棧頂 */（2）LOD /* 將變量值置于棧頂 */（3）STO /* 將棧頂?shù)闹蒂x與某變量 */（4）CAL /* 用于過程調(diào)用的指令 */（5）INT /* 在數(shù)據(jù)棧中分配存貯空間 */（6）JMP, JPC /* 用于 if, while 語句的條件或無條件控制轉(zhuǎn)移指令 */（7）OPR /* 一組算術(shù)或邏輯運(yùn)算指令 */上述指令的格式由三部分組成：FLA其中，f, l, a 的含義見下表： F FL La aINT常 量LIT常 量LOD層次差數(shù)據(jù)地址STO層次差數(shù)據(jù)地址CAL層次差程序地址JMP程序地址JPC程序地址OPR運(yùn)算類別上表中，層次差為變

21、量名或過程名引用和聲明之間的靜態(tài)層次差別，程序地址為目標(biāo)數(shù)組 code 的下標(biāo)，數(shù)據(jù)地址為變量在局部存貯中的相對地址。PL 的編譯程序?yàn)槊恳粭l PL 源程序的可執(zhí)行語句生成后綴式目標(biāo)代碼。這種代碼生成方式對于表達(dá)式、賦值語句、過程調(diào)用等的翻譯較簡單。如賦值語句 X := Y op Z（op 為某個運(yùn)算符） ，將被翻譯成下面的目標(biāo)代碼序列：（設(shè)指令計數(shù)從第 100 號開始）No.No.f fL La a100LODLevel_diff_YAddr_Y101LODLevel_diff_ZAddr_Z102OPRop103STOLevel_diff_XAddr_X而對 if 和 while 語句稍繁

22、瑣一點(diǎn)，因?yàn)榇藭r要生成一些跳轉(zhuǎn)指令，而跳轉(zhuǎn)的目標(biāo)地址大都是未知的。為解決這一問題，我們在 PL 編譯程序中采用了回填表 2-1 PL 處理機(jī)指令13技術(shù)，即產(chǎn)生跳轉(zhuǎn)目標(biāo)地址不明確的指令時，先保留這些指令的地址（code 數(shù)組的下標(biāo)） ，等到目標(biāo)地址明確后再回過來將該跳轉(zhuǎn)指令的目標(biāo)地址補(bǔ)上，使其成為完整的指令。下表是 if、while 語句目標(biāo)代碼生成的模式。 （L1，L2 是代碼地址）ifif C C thenthen S SWhileWhile C C dodo S S條件 C 的目標(biāo)代碼JPC - L1語句 S 的目標(biāo)代碼L1: .L1: 條件 C 的目標(biāo)代碼JPC L2語句 S 的目標(biāo)代

23、碼JMP L1L2: .相關(guān)過程（函數(shù)）有：gen()，其任務(wù)是把三個參數(shù) f、l、a 組裝成一條目標(biāo)指令并存放于 code 數(shù)組中，增加 CX 的值，CX 表示下一條即將生成的目標(biāo)指令的地址。2.5 代碼執(zhí)行代碼執(zhí)行為了簡單起見，我們假設(shè)有一個 PL 處理機(jī)，它能夠解釋執(zhí)行 PL 編譯程序所生成的目標(biāo)代碼。這個 PL 處理機(jī)有兩類存貯、一個指令寄存器和三個地址寄存器組成。程序（目標(biāo)代碼）存貯稱為 code，由編譯程序裝入，在目標(biāo)代碼執(zhí)行過程中保持不變，因此它可被看成是“只讀”存貯器。數(shù)據(jù)存貯 S 組織成為一個棧，所有的算術(shù)運(yùn)算均對棧頂元和次棧頂元進(jìn)行（一元運(yùn)算僅作用于棧頂元） ，并用結(jié)果值代

24、替原來的運(yùn)算對象。棧頂元的地址（下標(biāo)）記在棧頂寄存器 T 中，指令寄存器 I 包含著當(dāng)前正在解釋執(zhí)行的指令，程序地址寄存器 P 指向下一條將取出的指令。PL 的每一個過程可能包含著局部變量，因?yàn)檫@些過程可以被遞歸地調(diào)用，故在實(shí)際調(diào)用前，無法為這些局部變量分配存貯地址。各個過程的數(shù)據(jù)區(qū)在存貯棧S 內(nèi)順序疊起來，每個過程，除用戶定義的變量外，還應(yīng)當(dāng)有它自己的內(nèi)部信息，即調(diào)用它的程序段地址（返回地址）和它的調(diào)用者的數(shù)據(jù)區(qū)地址。在過程終止后，為了恢復(fù)原來程序的執(zhí)行，這兩個地址都是必須的。我們可將這兩個內(nèi)部值作為位于該過程數(shù)據(jù)區(qū)的內(nèi)部式隱式局部變量。我們把它們分別稱為返回地址（return addres

25、s）RA 和動態(tài)鏈（dynamic link）DL。動態(tài)鏈的頭，即最新分配的數(shù)據(jù)區(qū)的地址，保存在某地址寄存器 B 內(nèi)。因?yàn)閷?shí)際的存貯分配是運(yùn)行（解釋）時進(jìn)行的，編譯程序不能為其生成的代碼提供絕對地址，它只能確定變量在數(shù)據(jù)區(qū)內(nèi)的位置，因此它只能提供相對地址。為了正確地存取數(shù)據(jù)，解釋程序需將某個修正量加到相應(yīng)的數(shù)據(jù)區(qū)的基地址上去。若變量是局部于當(dāng)前正在解釋的過程，則此基地址由寄存器 B 給出，否則，就需要順著數(shù)據(jù)區(qū)的鏈逐層上去找。然而遺憾的是，編譯程序只能知道存取路線的表的長度，同時動態(tài)鏈保存的則是過程活動的動態(tài)歷史，而這兩條存取路線并不總是一樣。例如，假定有過程 A，B，C，其中過程 C 的說明

26、局部于過程 B，而過程 B 的表 2-2 if-while 語句目標(biāo)代碼生成模式14說明局部于過程 A，程序運(yùn)行時，過程 A 調(diào)用過程 B，過程 B 則調(diào)用過程 C，過程 C 又調(diào)用過程 B，如下圖所示：從靜態(tài)的角度我們可以說 A 是在第一層說明的，B 是在第二層說明的，C 則是在第三層說明的。若在 B 中存取 A 中說明的變量 a，由于編譯程序只知道 A，B間的靜態(tài)層差為 1，如果這時沿著動態(tài)鏈下降一步，將導(dǎo)致對 C 的局部變量的操作。為防止這種情況發(fā)生，有必要設(shè)置第二條鏈，它以編譯程序能明了的方式將各個數(shù)據(jù)區(qū)連接起來。我們稱之為靜態(tài)鏈（static link）SL。這樣，編譯程序所生成的代

27、碼地址是一對數(shù)，指示著靜態(tài)層差和數(shù)據(jù)區(qū)的相對修正量。下面我們給出的是過程 A、B 和 C 運(yùn)行時刻的數(shù)據(jù)區(qū)圖示： DLDL RARA SLSLA A 的變量的變量B B 的變量的變量C C 的變量的變量B B 的變量的變量有了以上認(rèn)識，我們就不難明白 PL 源程序的目標(biāo)代碼是如何被解釋執(zhí)行的。以語句 X ：= Y op Z 為例， （該語句的目標(biāo)代碼序列我們己在 2.4 節(jié)給出） ，PL處理機(jī)解釋該指令的“步驟”如下：AABBBCACB圖 2-1 過程說明嵌套圖 過程調(diào)用圖 表示 A 調(diào)用B15stepstep 1,1, S+T Sbase(level_diff_Y) + addr_Y;/ 將

28、變量 Y 的值放在棧頂stepstep 2,2, S+T Sbase(level_diff_Z) + addr_Z;/ 將變量 Z 的值放在棧頂，此棧頂元為變量 Y 的值stepstep 3,3, T-;/ 棧頂指針指向次棧頂元，即存放結(jié)果的單元stepstep 4,4, ST ST op ST + 1;/ 變量 Y 和變量 Z 之間進(jìn)行“op”操作stepstep 5,5, Sbase(level_diff_X) + addr_X ST;/ 將棧頂?shù)闹荡娣诺阶兞?X 所在的單元stepstep 6,6, T-;/ 棧頂指針減一相關(guān)過程：base()，interpret()。其中 base()

29、的功能是根據(jù)層次差并從當(dāng)前數(shù)據(jù)區(qū)沿著靜態(tài)鏈查找，以便獲取變量實(shí)際所在的數(shù)據(jù)區(qū)其地址；interpret()則完成各種指令的執(zhí)行工作。2.6 錯誤診斷處理錯誤診斷處理一個編譯程序，在多數(shù)情況下，所接受的源程序正文都是有錯誤的。發(fā)現(xiàn)錯誤，并給出合適的診斷信息且繼續(xù)編譯下去從而發(fā)現(xiàn)更多的錯誤，對于編譯程序而言是完全必要的。一個好的編譯器，其特征在于：任何輸入序列都不會引起編譯程序的崩潰。一切按語言定義為非法的結(jié)構(gòu)，都能被發(fā)現(xiàn)和標(biāo)志出來。經(jīng)常出現(xiàn)的錯誤，程序員的粗心或誤解造成的錯誤能被正確地診斷出來，而不致引起進(jìn)一步的株連錯誤。根據(jù)這樣的要求，我們?yōu)?PL 編譯程序制定了以下兩條規(guī)則：（1） 關(guān)鍵字規(guī)

30、則；程序員在寫程序時，可能會因?yàn)榇中亩┑粽Z句的分隔符“;” ，但他決不會漏掉算術(shù)運(yùn)算符“+” ，對于編譯程序而言，不論是分隔符號類的符號還是關(guān)鍵字符號類的符號，它們都具有同等重要的地位。基于這樣的特點(diǎn)，我們可以采用不易出錯的部分來作為恢復(fù)正常步調(diào)的標(biāo)記。每當(dāng)遇到錯誤時，分析程序跳過后面的某些部分，直到出現(xiàn)所期望的符號為止。對于程序設(shè)計語言來說，這種符號（稱為同步符號）的最好選擇就是關(guān)鍵字。PL 的每一種構(gòu)造語句以begin、if 或 while 開頭；每種說明則以 var、const 或 procedure 開頭。每遇到錯誤時，編譯程序便可跳過一段程序，直到遇到這類符號為止，而繼續(xù)編譯。（2

31、） 鎮(zhèn)定規(guī)則；自頂向下分析的特點(diǎn)在于目標(biāo)對分成一些子目標(biāo)，分程序則用別的分析程序來處理其子目標(biāo)。鎮(zhèn)定規(guī)則是說一個分析程序發(fā)現(xiàn)16了錯誤，它不應(yīng)該消極地停止前進(jìn)，僅僅向調(diào)用它的程序報告發(fā)生的錯誤；而應(yīng)該自己繼續(xù)向前掃描，找到似乎可以使正常的分析得以恢復(fù)的地方。這一規(guī)則在程序設(shè)計上的含義就是任一分析程序除了正常終止外，沒有其它出口。對于鎮(zhèn)定規(guī)則，一個可能的嚴(yán)格解釋為：一旦發(fā)現(xiàn)非法結(jié)構(gòu)，即跳過后面的輸入正文，直到下一個可以正確地跟隨當(dāng)前正在分析的句子結(jié)構(gòu)的符號為止。這意味著每一分析程序需知道其當(dāng)前活動結(jié)點(diǎn)的后繼符號集合。為了找到這個后繼符號集合，我們給對應(yīng)語法圖的每一個分析過程提供一個顯式參數(shù)，se

32、t，它指明可能的后繼集合。不過在任何條件下，如果都跳到輸入正文中下一個這種后繼符號出現(xiàn)的地方，未免太短視了。程序中所含的錯誤可能只不過是漏掉了一個符號（如“;” ）而己，由此而忽略去源程序的符號集合中，再湊加一些關(guān)鍵字，它們用于標(biāo)記那些不容忽略的結(jié)構(gòu)的開始符，因此，作為參數(shù)傳遞給分析過程的那些符號就不僅是后繼符號了。對于這樣的符號集，我們采用這樣的計算策略：先用一些明顯的關(guān)鍵符號給它賦初值，然后隨著分析子目標(biāo)的層次深入，逐步補(bǔ)充別的合法符號。為了靈活起見，我們引入 test 子程序來實(shí)現(xiàn)所說的驗(yàn)證工作。test 過程有三個參數(shù)：（1） 可允許的下一個符號集合 S1，如果當(dāng)前符號不在此集合中，當(dāng)

33、即得到一個錯誤號；（2） 另加的停止符號集合 S2，有些符號的出現(xiàn)，雖然無疑是錯的，但它們絕對不應(yīng)被忽略而跳過；（3） 整數(shù) n，表示有關(guān)錯誤的診斷號：voidvoid test(symsettest(symset s1,s1, symsetsymset s2,s2, intint n)n) symsetsymset s;s;ifif (!(! inset(sym,inset(sym, s1)s1) error(n);error(n);s s = = uniteset(s1,uniteset(s1, s2);s2);while(!while(! inset(sym,inset(sym, s)s

34、)getsym();getsym();destroyset(s);destroyset(s); 我們前面提出的方案，具有這樣的性質(zhì)：試圖通過略過輸入正文中的一個或多個符號來恢復(fù)分析的正常步調(diào)。在錯誤僅為漏掉一個符號所引起的情況下，它都是不適宜的策略。經(jīng)驗(yàn)表明，這類錯誤基本上限于那種僅有語法作用，而不代表動作的符號（如“;” ） 。把一些關(guān)鍵字加到后繼符號集合中去可使分析程序不再盲目地跳過后面的符號，好象漏掉的已經(jīng)補(bǔ)上去一樣。下面程序段就是 PL 分析程序中復(fù)合語句分析的一小段。它的效果等于關(guān)鍵字前插入漏掉的分號。statbegsys 集合是“語句”這個結(jié)構(gòu)的首符號集。ifif (sym(sym

35、 = SYM_BEGIN)SYM_BEGIN) getsym();getsym();17set1set1 = = createset(SYM_SEMICOLON,createset(SYM_SEMICOLON, SYM_END,SYM_END, SYM_NULL);SYM_NULL);setset = = uniteset(set1,uniteset(set1, fsys);fsys);statement(set);statement(set);whilewhile (sym(sym = SYM_SEMICOLONSYM_SEMICOLON | inset(sym,inset(sym, sta

36、tbegsys)statbegsys) ifif (sym(sym = SYM_SEMICOLON)SYM_SEMICOLON) getsym();getsym(); elseelse error(10);error(10); statement(set);statement(set); / whilewhiledestroyset(set1);destroyset(set1);destroyset(set);destroyset(set);ifif (sym(sym = SYM_END)SYM_END) getsym();getsym(); elseelse error(17);error(

37、17); / ; oror endend expected.expected. 相關(guān)過程：test(), inset(), createset, uniteset(), error().2.7 符號表管理符號表管理為了組成一條指令，編譯程序必須知道其操作碼及其參數(shù)（數(shù)或地址） 。這些值是由編譯程序本身聯(lián)系到相應(yīng)標(biāo)識符上去的。這種聯(lián)系是在處理常數(shù)、變量和過程說明完成的。為此，標(biāo)識符表應(yīng)包含每一標(biāo)識符所聯(lián)系的屬性；如果標(biāo)識符被說明為常數(shù)，其屬性值為常數(shù)值；如果標(biāo)識符被說明成變量，其屬性就是由層次和修正量（偏移量）組成的地址；如果標(biāo)識符被說明為過程，其屬性就是過程的入口地址及層次。常數(shù)的值由程序正文

38、提供，編譯的任務(wù)就是確定存放該值的地址。我們選擇順序分配變量和代碼的方法；每遇到一個變量說明，就將數(shù)據(jù)單元的下標(biāo)加一（PL 機(jī)中，每個變量占一個存貯單元） 。開始編譯一個過程時，要對數(shù)據(jù)單元的下標(biāo) dx 賦初值，表示新開辟一個數(shù)據(jù)區(qū)。dx 的初值為 3，因?yàn)槊總€數(shù)據(jù)區(qū)包含三個內(nèi)部變量 RA，DL 和 SL。相關(guān)過程：enter()，該函數(shù)用于向符號表添加新的符號，并確定標(biāo)識符的有關(guān)屬性。182.8 其他其他本實(shí)驗(yàn)所提供的 PL 編譯程序包括詞法分析、語法分析、錯誤診斷、代碼生成、解釋執(zhí)行等幾部分。關(guān)于這幾個程序，我們做如下說明：（1） 每一個分程序（過程）被編譯結(jié)束后，將列出該部分 PL 程序

39、代碼。這個工作由過程 listcode()完成。注意，每個分程序（過程）的第一條指令未被列出。該指令是跳轉(zhuǎn)指令。其作用是繞過該分程序的說明部分所產(chǎn)生的代碼（含過程說明所產(chǎn)生的代碼） 。（2） 解釋程序作為 PL 編譯程序的一個過程，若被編譯的源代碼沒有錯誤，則編譯結(jié)束時調(diào)用這個過程。（3） PL 語言沒有輸出語句。解釋程序按執(zhí)行次序，每遇到對變量的賦值就輸出其值。19第二部分第二部分 上機(jī)實(shí)驗(yàn)具體要求上機(jī)實(shí)驗(yàn)具體要求“編譯原理”的上機(jī)實(shí)驗(yàn)要求對 PL 語言及其編譯器進(jìn)行實(shí)現(xiàn)、擴(kuò)充和修改。每個擴(kuò)充或修改方式可得到不同的分?jǐn)?shù)，滿分為 100 分。完成上機(jī)作業(yè)后，必須提交下列文檔：(1) 修改后的

40、PL 語言文本。包含詞法分析（正規(guī)式） ，語法分析（BNF） 。(2) 有關(guān)修改后的 PL 編譯/解釋器的說明。詳細(xì)說明你的編譯器是如何編譯新的 PL 語言程序的。指出你的程序中最精彩的部分，以及你為什么這樣做，你是如何控制和恢復(fù)語義錯誤的。(3) 給出你所改動后的編譯器源程序清單，并標(biāo)記出你所修改的部分。比較你的編譯器和原來的編譯器之間的差別。(4) 說明你的編譯器中可能存在的錯誤。(5) 總結(jié)經(jīng)驗(yàn)與教訓(xùn)，如果重做一遍，你會有哪些新的改進(jìn)？對現(xiàn)存的 PL 編譯程序可做如下修改或擴(kuò)充，其中（1） 、 （2） 、 （11）和（12）必須完成，剩余的均可任意選擇，但總分必須超過 40 分。(1)

41、注釋（5 分）注釋由(*和*)包含，不允許嵌套。(2) 布爾類型的數(shù)據(jù)（10 分）布爾類型的 BNF 為：var_optionvar_option | | varvar var_decl_listvar_decl_listvar_decl_listvar_decl_list var_declvar_decl | | var_decl_listvar_decl_list var_declvar_declvar_declvar_decl ident_listident_list : : data_typedata_typedata_typedata_type integerinteger | |

42、booleanboolean這種修改包括：這種修改包括：（i）區(qū)別整型與布爾型變量、常量和表達(dá)式。（ii）增加按嚴(yán)格計算的布爾類型運(yùn)算符 and、or 和 not。這些算符以及己有的運(yùn)算符的優(yōu)先級與 Pascal 語言相同。（iii）能夠使用布爾常量 true 和 false。（iv）把 PL 語言中的“條件”概念一般化為 Pascal 語言那樣。（v v）布爾表達(dá)式可以比較大?。篺alse 0 0 dodobeginbeginifif oddodd b b thenthen z z :=:= z z + + a;a;a a :=:= 2 2 * * a;a; b b :=:= b b / /

43、 2;2;endendend;end;procedureprocedure divide;divide;varvar w;w;beginbeginr r :=:= x;x; q q :=:= 0;0; w w :=:= y;y;whilewhile w w y y dodobeginbeginq q :=:= 2 2 * * q;q; w w :=:= w w / / 2;2;ifif w w = r r thenthenbeginbeginr r :=:= r r - - w;w;q q :=:= q q + + 1;1;end;end;endendend;end;procedureproc

44、edure gcd;gcd;varvar f,f, g;g;beginbegin22f f :=:= x;x;g g :=:= y;y;whilewhile f f g g dodobeginbeginifif f f g g thenthen g g :=:= g g f;f;ifif g g 1212JPCJPC0 02929-ifif b b = 0odd(b)z := z + aa := 2 * ab := b / 2ifwhileb := y29 Pl0c.c#include #include pl0c.h#include string.h/* 解釋執(zhí)行時使用的棧 */#define

45、 stacksize 500 int main()bool nxtlevsymnum;init();/* 初始化 */fas=fopen(fas.tmp,w);fa1=fopen(fa1.tmp,w);printf(Input file? );fprintf(fa1,Input file? );scanf(%s,fname);/* 輸入文件名 */fin=fopen(fname,r);if(fin)fprintf(fa1,%sn,fname);printf(List object code?(Y/N);/* 是否輸出虛擬機(jī)代碼 */scanf(%s,fname);listswitch=(fna

46、me0=y|fname0=Y);printf(List symbol table?(Y/N); /* 是否輸出名字表 */scanf(%s,fname);tableswitch=(fname0=y|fname0=Y);err=0;cc=cx=ll=0;ch= ;kk=al-1;if(-1!=getsym()fa=fopen(fa.tmp,w);fa2=fopen(fa2.tmp,w);addset(nxtlev,declbegsys,statbegsys,symnum);nxtlevperiod=true;if(-1=block(0,0,nxtlev) /* 調(diào)用編譯程序 */fclose(f

47、a);fclose(fa1);fclose(fin);printf(n);return 0;30fclose(fa);fclose(fa1);if(sym!=period)error(9);if(err=0)interpret(); /* 調(diào)用解釋執(zhí)行程序 */elseprintf(Errors in pl/0 program);fclose(fin);elseprintf(Cant open file!n);fprintf(fa1,Cant open file!n);fclose(fa1);fclose(fas);printf(n);return 0;/* 在適當(dāng)?shù)奈恢蔑@示錯誤 */void

48、 error(int n)char space81;memset(space,32,81);spacecc-1=0; /* 出錯時當(dāng)前符號已經(jīng)讀完，所以 cc-1 */ printf(*%s!%dn,space,n);fprintf(fa1,*%s!%dn,space,n);err+;/* 詞法分析，獲取一個符號 */int getsym()int i,j,k;while(ch= |ch=10|ch=9) /* 忽略空格、換行和 TAB */getchdo;if(ch=a&ch=z)31/* 名字或保留字以 a.z 開頭 */k=0;doif(k=a&ch=0&ch=9);ak=0;strcp

49、y(id,a);i=0;j=norw-1;do /* 搜索當(dāng)前符號是否為保留字 */k=(i+j)/2;if(strcmp(id,wordk)=0)i=k+1;while(ij)sym=wsymk; else sym=ident; /* 搜索失敗則，是名字或數(shù)字 */elseif(ch=0&ch=0&chnmax)error(30);else32if(ch=:)/* 檢測賦值符號 */getchdo;if(ch=)sym=becomes;getchdo;elsesym=nul;/* 不能識別的符號 */elseif(ch=)/* 檢測大于或大于等于符號 */getchdo;if(ch=)sym

50、=geq;getchdo;elsesym=gtr;else33sym=ssymch;/* 當(dāng)符號不滿足上述條件時，全部按照單字符符號處理 */getchdo;return 0;/* 生成虛擬機(jī)代碼 */int gen(enum fct x, /* f */int y, /* l */int z /* a */)if(cxcxmax)printf(Program too long);/* 程序過長 */return -1;codecx.f=x;codecx.l=y;codecx.a=z;cx+;return 0;/* 在某一部分（如一條語句，一個表達(dá)式）將要結(jié)束時時我們希望下一個符號屬于某集合（

51、該部分的后跟符號） ，test 負(fù)責(zé)這項(xiàng)監(jiān)測，并且負(fù)責(zé)當(dāng)監(jiān)測不通過時的補(bǔ)救措施，程序在需要檢測時指定當(dāng)前需要的符號集合和補(bǔ)救用的集合（如之前未完成部分的后跟符號） ，以及檢測不通過時的錯誤號 */int test(bool* s1, /* 我們需要的符號 */ bool* s2, /* 如果不是我們需要的，則需要一個補(bǔ)救用的集合 */ int n) /* 錯誤號 */if(!inset(sym,s1)error(n);/* 當(dāng)檢測不通過時，不停獲取符號，直到它屬于需要的集合或補(bǔ)救的集合 */while(!inset(sym,s1)&(!inset(sym,s2)getsymdo;34retur

52、n 0;/* 編譯程序主體 */int block(int lev, /* 當(dāng)前分程序所在層 */ int tx, /* 名字表當(dāng)前尾指針 */ bool* fsys /* 當(dāng)前模塊后跟符號集合 */ )int i;int dx; /* 名字分配到的相對地址 */int tx0; /* 保留初始 tx */int cx0; /* 保留初始 cx */bool nxtlevsymnum; /* 在下級函數(shù)的參數(shù)中，符號集合均為值參，但由于使用數(shù)租實(shí)現(xiàn)，傳遞進(jìn)來的是指針，為防止下級函數(shù)改變上級函數(shù)的集合，開辟新的空間傳遞給下級函數(shù)，之后所有的 nxtlev 都是這樣 */dx=3; tx0=tx;

53、/* 記錄本層名字的初始位置 */tabletx.adr=cx;gendo(jmp,0,0);if(levlevmax)error(32);doif(sym=constsym)/* 收到常量聲明符號，開始處理常量聲明 */getsymdo;doconstdeclarationdo(&tx,lev,&dx); /* dx 的值會被constdeclaration 改變，使用指針 */while(sym=comma) getsymdo;constdeclarationdo(&tx,lev,&dx);if(sym=semicolon)getsymdo;else error(5);while(sym=

54、ident);35if(sym=varsym)/* 收到變量聲明符號，開始處理變量聲明 */getsymdo;dovardeclarationdo(&tx,lev,&dx);while(sym=comma) getsymdo;vardeclarationdo(&tx,lev,&dx);if(sym=semicolon)getsymdo;else error(5);while(sym=ident);while(sym=procsym) /* 收到過程聲明符號，開始處理過程聲明 */getsymdo;if(sym=ident)enter(procedur,&tx,lev,&dx); /* 記錄過程

55、名字 */getsymdo;else error(4);/* procedure 后應(yīng)為標(biāo)識符 */if(sym=semicolon)getsymdo;else error(5);/* 漏掉了分號 */memcpy(nxtlev,fsys,sizeof(bool)*symnum);nxtlevsemicolon=true;if(-1=block(lev+1,tx,nxtlev)return -1;/* 遞歸調(diào)用 */if(sym=semicolon)getsymdo;memcpy(nxtlev,statbegsys,sizeof(bool)*symnum);nxtlevident=true;n

56、xtlevprocsym=true;testdo(nxtlev,fsys,6);36else error(5);/* 漏掉了分號 */memcpy(nxtlev,statbegsys,sizeof(bool)*symnum);nxtlevident=true;testdo(nxtlev,declbegsys,7);while(inset(sym,declbegsys); /* 直到?jīng)]有聲明符號 */codetabletx0.adr.a=cx;/* 開始生成當(dāng)前過程代碼 */tabletx0.adr=cx;/* 當(dāng)前過程代碼地址 */tabletx0.size=dx;/* 聲明部分中每增加一條聲

57、明都會給 dx 增加 1，聲明部分已經(jīng)結(jié)束，dx 就是當(dāng)前過程數(shù)據(jù)的 size */cx0=cx;gendo(inte,0,dx);/* 生成分配內(nèi)存代碼 */if(tableswitch)/* 輸出名字表 */printf(TABLE:n);if(tx0+1tx)printf( NULLn);for(i=tx0+1;i=tx;i+)switch(tablei.kind)case constant:printf( %d const %s ,i,);printf(val=%dn,tablei.val);fprintf(fas, %d const %s ,i,tablei.n

58、ame);fprintf(fas,val=%dn,tablei.val);break;case variable:printf( %d var %s ,i,);printf(lev=%d addr=%dn,tablei.level,tablei.adr);fprintf(fas, %d var %s ,i,);fprintf(fas,lev=%d addr=%dn,tablei.level,tablei.adr);break;case procedur:printf( %d proc %s ,i,);printf(lev=%d

59、addr=%d size=%dn,tablei.level,tablei.adr,tablei.size);fprintf(fas, %d proc %s ,i,);fprintf(fas,lev=%d addr=%d size=%dn,tablei.level,tablei.adr,tablei.size);break;printf(n);37/* 語句后跟符號為分號或 end */memcpy(nxtlev,fsys,sizeof(bool)*symnum);/* 每個后跟符號集和都包含上層后跟符號集和，以便補(bǔ)救 */nxtlevsemicolon=true;nxtl

60、evendsym=true;statementdo(nxtlev,&tx,lev);gendo(opr,0,0); /* 每個過程出口都要使用的釋放數(shù)據(jù)段指令 */memset(nxtlev,0,sizeof(bool)*symnum);/*分程序沒有補(bǔ)救集合 */testdo(fsys,nxtlev,8); /* 檢測后跟符號正確性 */listcode(cx0);/* 輸出代碼 */return 0;/* 解釋程序 */void interpret()int p,b,t;/* 指令指針，指令基址，棧頂指針 */struct instruction i;/* 存放當(dāng)前指令 */int sst