編譯原理(第二版)張素琴清華大學(xué)---答案詳解

1、編譯原理課后習(xí)題答案第一章 第 1 章 引論 第1題 解釋下列術(shù)語： （1）編譯程序 （2）源程序 （3）目標(biāo)程序 （4）編譯程序的前端 （5）后端 （6）遍 答案： （1） 編譯程序：如果源語言為高級語言，目標(biāo)語言為某臺計算機上的匯編語言或機器語 言，則此翻譯程序稱為編譯程序。 （2） 源程序：源語言編寫的程序稱為源程序。 （3） 目標(biāo)程序：目標(biāo)語言書寫的程序稱為目標(biāo)程序。 （4） 編譯程序的前端：它由這樣一些階段組成：這些階段的工作主要依賴于源語言而與 目標(biāo)機無關(guān)。通常前端包括詞法分析、語法分析、語義分析和中間代碼生成這些階 段，某些優(yōu)化工作也可在前端做，也包括與前端每個階段相關(guān)的出錯處理

2、工作和符 號表管理等工作。 （5） 后端：指那些依賴于目標(biāo)機而一般不依賴源語言，只與中間代碼有關(guān)的那些階段， 即目標(biāo)代碼生成，以及相關(guān)出錯處理和符號表操作。 （6） 遍：是對源程序或其等價的中間語言程序從頭到尾掃視并完成規(guī)定任務(wù)的過程。 第2題 一個典型的編譯程序通常由哪些部分組成？各部分的主要功能是什么？并畫出編譯程 序的總體結(jié)構(gòu)圖。 答案： 一個典型的編譯程序通常包含 8 個組成部分，它們是詞法分析程序、語法分析程序、語 義分析程序、中間代碼生成程序、中間代碼優(yōu)化程序、目標(biāo)代碼生成程序、表格管理程序和 錯誤處理程序。其各部分的主要功能簡述如下。 詞法分析程序：輸人源程序，拼單詞、檢查單詞和

3、分析單詞，輸出單詞的機內(nèi)表達形式。 語法分析程序：檢查源程序中存在的形式語法錯誤，輸出錯誤處理信息。 語義分析程序：進行語義檢查和分析語義信息，并把分析的結(jié)果保存到各類語義信息表 中。 中間代碼生成程序：按照語義規(guī)則，將語法分析程序分析出的語法單位轉(zhuǎn)換成一定形式 的中間語言代碼，如三元式或四元式。 中間代碼優(yōu)化程序：為了產(chǎn)生高質(zhì)量的目標(biāo)代碼，對中間代碼進行等價變換處理。 盛威網(wǎng)（）專業(yè)的計算機學(xué)習(xí)網(wǎng)站 1編譯原理課后習(xí)題答案第一章 目標(biāo)代碼生成程序：將優(yōu)化后的中間代碼程序轉(zhuǎn)換成目標(biāo)代碼程序。 表格管理程序：負責(zé)建立、填寫和查找等一系列表格工作。表格的作用是記錄源程序的 各類信息和編譯各階段的進

4、展情況，編譯的每個階段所需信息多數(shù)都從表格中讀取，產(chǎn)生的 中間結(jié)果都記錄在相應(yīng)的表格中?？梢哉f整個編譯過程就是造表、查表的工作過程。需要指 出的是，這里的"表格管理程序"并不意味著它就是一個獨立的表格管理模塊，而是指編譯 程序具有的表格管理功能。 錯誤處理程序：處理和校正源程序中存在的詞法、語法和語義錯誤。當(dāng)編譯程序發(fā)現(xiàn)源 程序中的錯誤時，錯誤處理程序負責(zé)報告出錯的位置和錯誤性質(zhì)等信息，同時對發(fā)現(xiàn)的錯誤 進行適當(dāng)?shù)男Ｕㄐ迯?fù)） ，目的是使編譯程序能夠繼續(xù)向下進行分析和處理。 注意：如果問編譯程序有哪些主要構(gòu)成成分，只要回答六部分就可以。如果搞不清楚， 就回答八部分。 第3題

5、 何謂翻譯程序、編譯程序和解釋程序？它們?nèi)咧g有何種關(guān)系？ 答案： 翻譯程序是指將用某種語言編寫的程序轉(zhuǎn)換成另一種語言形式的程序的程序， 如編譯程 序和匯編程序等。 編譯程序是把用高級語言編寫的源程序轉(zhuǎn)換（加工）成與之等價的另一種用低級語言編 寫的目標(biāo)程序的翻譯程序。 解釋程序是解釋、執(zhí)行高級語言源程序的程序。解釋方式一般分為兩種：一種方式是， 源程序功能的實現(xiàn)完全由解釋程序承擔(dān)和完成，即每讀出源程序的一條語句的第一個單詞， 則依據(jù)這個單詞把控制轉(zhuǎn)移到實現(xiàn)這條語句功能的程序部分， 該部分負責(zé)完成這條語句的功 能的實現(xiàn)，完成后返回到解釋程序的總控部分再讀人下一條語句繼續(xù)進行解釋、執(zhí)行，如此 反

6、復(fù)；另一種方式是，一邊翻譯一邊執(zhí)行，即每讀出源程序的一條語句，解釋程序就將其翻 譯成一段機器指令并執(zhí)行之，然后再讀人下一條語句繼續(xù)進行解釋、執(zhí)行，如此反復(fù)。無論 盛威網(wǎng)（）專業(yè)的計算機學(xué)習(xí)網(wǎng)站 2編譯原理課后習(xí)題答案第一章 是哪種方式，其加工結(jié)果都是源程序的執(zhí)行結(jié)果。目前很多解釋程序采取上述兩種方式的綜 合實現(xiàn)方案，即先把源程序翻譯成較容易解釋執(zhí)行的某種中間代碼程序，然后集中解釋執(zhí)行 中間代碼程序，最后得到運行結(jié)果。 廣義上講，編譯程序和解釋程序都屬于翻譯程序，但它們的翻譯方式不同，解釋程序是 邊翻譯（解釋）邊執(zhí)行，不產(chǎn)生目標(biāo)代碼，輸出源程序的運行結(jié)果。而編譯程序只負責(zé)把源 程序翻譯成目標(biāo)程序

7、，輸出與源程序等價的目標(biāo)程序，而目標(biāo)程序的執(zhí)行任務(wù)由操作系統(tǒng)來 完成，即只翻譯不執(zhí)行。 第4題 對下列錯誤信息，請指出可能是編譯的哪個階段（詞法分析、語法分析、語義分析、 代碼生成）報告的。 （1） else 沒有匹配的 if （2） 數(shù)組下標(biāo)越界 （3） 使用的函數(shù)沒有定義 （4） 在數(shù)中出現(xiàn)非數(shù)字字符 答案： （1） （2） （3） （4） 第5題 語法分析 語義分析 語法分析 詞法分析 編譯程序大致有哪幾種開發(fā)技術(shù)？ 答案： （1）自編譯：用某一高級語言書寫其本身的編譯程序。 （2）交叉編譯：A 機器上的編譯程序能產(chǎn)生 B 機器上的目標(biāo)代碼。 （3）自展：首先確定一個非常簡單的核心語言

8、L0，用機器語言或匯編語言書寫出它的編譯 程序 T0，再把語言 L0 擴充到 L1，此時 L0 Ì L1 ,并用 L0 編寫 L1 的編譯程序 T1，再把語 言 L1 擴充為 L2，有 L1 Ì L2 ,并用 L1 編寫 L2 的編譯程序 T2，¼¼，如此逐步擴展下去， 好似滾雪球一樣，直到我們所要求的編譯程序。 （4）移植：將 A 機器上的某高級語言的編譯程序搬到 B 機器上運行。 盛威網(wǎng)（）專業(yè)的計算機學(xué)習(xí)網(wǎng)站 3編譯原理課后習(xí)題答案第一章 第題 計算機執(zhí)行用高級語言編寫的程序有哪些途徑?它們之間的主要區(qū)別是什么? 答案： 計算機執(zhí)行用高級語言編寫的

9、程序主要途徑有兩種，即解釋與編譯。 像 Basic 之類的語言，屬于解釋型的高級語言。它們的特點是計算機并不事先對高級語 言進行全盤翻譯，將其變?yōu)闄C器代碼，而是每讀入一條高級語句，就用解釋器將其翻譯為一 條機器代碼，予以執(zhí)行，然后再讀入下一條高級語句，翻譯為機器代碼，再執(zhí)行，如此反復(fù)。 總而言之，是邊翻譯邊執(zhí)行。 像 C，Pascal 之類的語言，屬于編譯型的高級語言。它們的特點是計算機事先對高級語 言進行全盤翻譯，將其全部變?yōu)闄C器代碼，再統(tǒng)一執(zhí)行，即先翻譯，后執(zhí)行。從速度上看， 編譯型的高級語言比解釋型的高級語言更快。 盛威網(wǎng)（）專業(yè)的計算機學(xué)習(xí)網(wǎng)站 4編譯原理課后習(xí)題答案第二章 第 2 章

10、 PL/0 編譯程序的實現(xiàn) 第1題 PL/0 語言允許過程嵌套定義和遞歸調(diào)用，試問它的編譯程序如何解決運行時的存儲管 理。 答案： PL/0 語言允許過程嵌套定義和遞歸調(diào)用，它的編譯程序在運行時采用了棧式動態(tài)存儲 管理。（數(shù)組 CODE 存放的只讀目標(biāo)程序，它在運行時不改變。）運行時的數(shù)據(jù)區(qū) S 是由 解釋程序定義的一維整型數(shù)組，解釋執(zhí)行時對數(shù)據(jù)空間 S 的管理遵循后進先出規(guī)則，當(dāng)每 個過程(包括主程序)被調(diào)用時，才分配數(shù)據(jù)空間，退出過程時，則所分配的數(shù)據(jù)空間被釋放。 應(yīng)用動態(tài)鏈和靜態(tài)鏈的方式分別解決遞歸調(diào)用和非局部變量的引用問題。 第2題 若 PL/0 編譯程序運行時的存儲分配策略采用棧式動

11、態(tài)分配，并用動態(tài)鏈和靜態(tài)鏈的方 式分別解決遞歸調(diào)用和非局部變量的引用問題，試寫出下列程序執(zhí)行到賦值語句 b=10 時 運行棧的布局示意圖。 var x,y; procedure p; var a; procedure q; var b; begin (q) b=10; end (q); procedure s; var c,d; procedure r; var e,f; begin (r) call q; end (r); begin (s) call r; end (s); begin (p) call s; 盛威網(wǎng)（）專業(yè)的計算機學(xué)習(xí)網(wǎng)站 1編譯原理課后習(xí)題答案第二章 end (p);

12、begin (main) call p; end (main). 答案： 程序執(zhí)行到賦值語句 b=10 時運行棧的布局示意圖為： 第3題 寫出題 2 中當(dāng)程序編譯到 r 的過程體時的名字表 table 的內(nèi)容。 name kind level/val adr size 答案： 題 2 中當(dāng)程序編譯到 r 的過程體時的名字表 table 的內(nèi)容為： name kind level/val adr size xvariable 0dx yvariable 0dx+1 pprocedure 0過程 p 的入口（待填） 5盛威網(wǎng)（）專業(yè)的計算機學(xué)習(xí)網(wǎng)站 2編譯原理課后習(xí)題答案第二章 avariable

13、 1dx qprocedure 1過程 q 的入口 4sprocedure 1過程 s 的入口（待填） 5cvariable 2dx dvariable 2dx rprocedure 2過程 r 的入口 5evariable 3dx fvariable 3dx+1 注意：q 和 s 是并列的過程，所以 q 定義的變量 b 被覆蓋。 第4題 指出棧頂指針 T，最新活動記錄基地址指針 B，動態(tài)鏈指針 DL，靜態(tài)鏈指針 SL 與返 回地址 RA 的用途。 答案： 棧頂指針 T，最新活動記錄基地址指針 B，動態(tài)鏈指針 DL，靜態(tài)鏈指針 SL 與返回地址 RA 的用途說明如下： T： 棧頂寄存器 T 指

14、出了當(dāng)前棧中最新分配的單元(T 也是數(shù)組 S 的下標(biāo))。 B：基址寄存器，指向每個過程被調(diào)用時，在數(shù)據(jù)區(qū) S 中給它分配的數(shù)據(jù)段起 始 地址， 也稱基地址。 SL： 靜態(tài)鏈，指向定義該過程的直接外過程（或主程序）運行時最新數(shù)據(jù)段的基地址， 用以引用非局部（包圍它的過程）變量時，尋找該變量的地址。 DL： 動態(tài)鏈，指向調(diào)用該過程前正在運行過程的數(shù)據(jù)段基地址，用以過程執(zhí)行結(jié)束釋 放數(shù)據(jù)空間時，恢復(fù)調(diào)用該過程前運行棧的狀態(tài)。 RA： 返回地址，記錄調(diào)用該過程時目標(biāo)程序的斷點，即調(diào)用過程指令的下一條指令的 地址，用以過程執(zhí)行結(jié)束后返回調(diào)用過程時的下一條指令繼續(xù)執(zhí)行。 在每個過程被調(diào)用時在棧頂分配 3

15、個聯(lián)系單元，用以存放 SL，DL， RA。 第5題 PL/0 編譯程序所產(chǎn)生的目標(biāo)代碼是一種假想棧式計算機的匯編語言，請說明該匯編語 言中下列指令各自的功能和所完成的操作。 （） INT 0 A （） OPR 0 0 （） CAL L A 答案： PL/0 編譯程序所產(chǎn)生的目標(biāo)代碼中有 3 條非常重要的特殊指令，這 3 條指令在 code 中 的位置和功能以及所完成的操作說明如下： 盛威網(wǎng)（）專業(yè)的計算機學(xué)習(xí)網(wǎng)站 3編譯原理課后習(xí)題答案第二章 INT 0 A 在過程目標(biāo)程序的入口處，開辟 A 個單元的數(shù)據(jù)段。A 為局部變量的個數(shù)+3。 OPR 0 0 在過程目標(biāo)程序的出口處，釋放數(shù)據(jù)段（退棧）

16、，恢復(fù)調(diào)用該過程前正在運行的過程的 數(shù)據(jù)段基址寄存器 B 和棧頂寄存器 T 的值，并將返回地址送到指令地址寄存器 P 中，以使 調(diào)用前的程序從斷點開始繼續(xù)執(zhí)行。 CAL L A 調(diào)用過程，完成填寫靜態(tài)鏈、動態(tài)鏈、返回地址，給出被調(diào)用過程的基地址值，送入基 址寄存器 B 中，目標(biāo)程序的入口地址 A 的值送指令地址寄存器 P 中，使指令從 A 開始執(zhí)行。 第6題 給出對 PL/0 語言作如下功能擴充時的語法圖和 EBNF 的語法描述。 (1) 擴充條件語句的功能使其為： if條件then語句else語句 (2) 擴充 repeat 語句為： repeat語句； 語句until條件 答案： 對 PL

17、/0 語言作如下功能擴充時的語法圖和 EBNF 的語法描述如下： (1) 擴充條件語句的語法圖為： EBNF 的語法描述為： 條件語句:= if條件then語句else語句 (2) 擴充 repeat 語句的語法圖為： EBNF 的語法描述為： 重復(fù)語句:= repeat語句；語句until條件 盛威網(wǎng)（）專業(yè)的計算機學(xué)習(xí)網(wǎng)站 4編譯原理課后習(xí)題答案第三章 第3章 文法和語言 第1題 文法 G(A,B,S,a,b,c,P,S)其中 P 為： S®Ac|aB A®ab B®bc 寫出 L(GS)的全部元素。 答案： L(GS)=abc 第2題 文法 GN為： N&#

18、174;D|ND D®0|1|2|3|4|5|6|7|8|9 GN的語言是什么？ 答案: GN的語言是 V+。V=0,1,2,3,4,5,6,7,8,9 N=>ND=>NDD. =>NDDDD.D=>D.D 或者：允許 0 開頭的非負整數(shù)？ 第題 為只包含數(shù)字、加號和減號的表達式，例如 9-25，3-1，等構(gòu)造一個文法。 答案： GS: S->S+D|S-D|D D->0|1|2|3|4|5|6|7|8|9 第4題 已知文法 GZ： Z®aZb|ab 寫出 L(GZ)的全部元素。 盛威網(wǎng)（）專業(yè)的計算機學(xué)習(xí)網(wǎng)站 1編譯原理課后習(xí)題答案第三

19、章 答案： Z=>aZb=>aaZbb=>aaa.Z.bbb=> aaa.ab.bbb L(GZ)=anbn|n>=1 第5題 寫一文法，使其語言是偶正整數(shù)的集合。 要求： (1) 允許 0 打頭； (2)不允許 0 打頭。 答案： (1)允許 0 開頭的偶正整數(shù)集合的文法 E®NT|D T®NT|D N®D|1|3|5|7|9 D®0|2|4|6|8 (2)不允許 0 開頭的偶正整數(shù)集合的文法 E®NT|D T®FT|G N®D|1|3|5|7|9 D®2|4|6|8 F®

20、N|0 G®D|0 第6題 已知文法 G： <表達式>:=<項><表達式><項> <項>:=<因子><項>*<因子> <因子>:=（<表達式>）i 試給出下述表達式的推導(dǎo)及語法樹。 （）i+(i+i) （）i+i*i 盛威網(wǎng)（）專業(yè)的計算機學(xué)習(xí)網(wǎng)站 2編譯原理課后習(xí)題答案第三章 答案： (5) <表達式> =><表達式><項> =><表達式><因子> =><表達式>（<表

21、達式>） =><表達式>（<表達式><項>） =><表達式>（<表達式><因子>） =><表達式>（<表達式>i） =><表達式>（<項>i） <表達式> <項> <表達式> +<項> <因子> =><表達式>（<因子>i） =><表達式>（ii） =><項>（ii） =><因子>（ii） =>i（

22、ii） <因子> i（<表達式> <項> <因子> i<表達式> +)<項> <因子> i(6) <表達式> =><表達式><項> =><表達式><項>*<因子> =><表達式><項>*i =><表達式><因子>*i =><表達式>i*i =><項>i*i =><因子>i*i =>ii*i <表達式>

23、; <項> <因子> i<表達式> +<項> <因子> i<項> *<因子> i盛威網(wǎng)（）專業(yè)的計算機學(xué)習(xí)網(wǎng)站 3編譯原理課后習(xí)題答案第三章 第7題 證明下述文法 G表達式是二義的。 表達式=a|(表達式)|表達式 運算符 表達式 運算符=+|-|*|/ 答案： 可為句子 a+a*a 構(gòu)造兩個不同的最右推導(dǎo): 最右推導(dǎo) 1 表達式 表達式 運算符 達式 表 表達式 運算符a 表達式* a 表達式 運算符 達式* a 表 表達式 運算符a * a 表達式+ a * a a+a*a 最右推導(dǎo) 2 表達式 表達式 運

24、算符 達式 表 表達式 運算符 達式 表 運算符 表達式 表達式 運算符 達式 表 運算符 a 表達式 運算符 達式 * a 表 表達式 運算符a * a 表達式+ a * a a+a*a 盛威網(wǎng)（）專業(yè)的計算機學(xué)習(xí)網(wǎng)站 4編譯原理課后習(xí)題答案第三章 第8題 文法 GS為： S®Ac|aB A®ab B®bc 該文法是否為二義的？為什么？ 答案： 對于串 abc (1)S=>Ac=>abc (2)S=>aB=>abc 即存在兩不同的最右推導(dǎo)。所以，該文法是二義的。 或者： 對輸入字符串 abc，能構(gòu)造兩棵不同的語法樹，所以它是二義的。 SS

25、aBAcbcab第9題 考慮下面上下文無關(guān)文法： S®SS*|SS+|a (1)表明通過此文法如何生成串 aa+a*，并為該串構(gòu)造語法樹。 (2)GS的語言是什么？ SSS*答案： SS+a(1)此文法生成串 aa+a*的最右推導(dǎo)如下 S=>SS*=>SS*=>Sa*=>SS+a*=>Sa+a*=>aa+a* aa(2)該文法生成的語言是：*和+的后綴表達式，即逆波蘭式。 盛威網(wǎng)（）專業(yè)的計算機學(xué)習(xí)網(wǎng)站 5編譯原理課后習(xí)題答案第三章 第 10 題 文法 S®S(S)S|e (1) 生成的語言是什么？ (2) 該文法是二義的嗎？說明理由。

26、答案： （） 嵌套的括號 （） 是二義的，因為對于（） （）可以構(gòu)造兩棵不同的語法樹。 第 11 題 令文法 GE為： E®T|E+T|E-T T®F|T*F|T/F F®(E)|i 證明 E+T*F 是它的一個句型，指出這個句型的所有短語、直接短語和句柄。 答案： 此句型對應(yīng)語法樹如右，故為此文法一個句型。 或者：因為存在推導(dǎo)序列: E=>E+T=>E+T*F，所 以 E+T*F 句型 此句型相對于 E 的短語有:E+T*F； 相對于 T 的短語 有 T*F 直接短語為：T*F 句柄為：T*F 第 13 題 一個上下文無關(guān)文法生成句子 abbaa 的

27、推導(dǎo)樹如下： (1)給出串 abbaa 最左推導(dǎo)、最右推導(dǎo)。 (2)該文法的產(chǎn)生式集合 P 可能有哪些元素？ (3)找出該句子的所有短語、直接短語、句柄。 ASaeSBBbBbAaSa盛威網(wǎng)（）專業(yè)的計算機學(xué)習(xí)網(wǎng)站 6編譯原理課后習(xí)題答案第三章 答案： (1)串 abbaa 最左推導(dǎo): S=>ABS=>aBS=>aSBBS=>aBBS=>abBS=>abbS=>abbAa=>abbaa 最右推導(dǎo)： S=>ABS=>ABAa=>ABaa=>ASBBaa=>ASBbaa=>ASbbaa=>Abbaa=>

28、abbaa (2)產(chǎn)生式有：S®ABS |Aa|e A®a B®SBB|b 可能元素有：e aa ab (3)該句子的短語有： a 是相對 A 的短語 e 是相對 S 的短語 b 是相對 B 的短語 ebb 是相對 B 的短語 aa 是相對 S 的短語 aebbaa 是相對 S 的短語 直接短語有：a e b 句柄是：a abbaa aaabbaa ¼¼ 第 14 題 給出生成下述語言的上下文無關(guān)文法： （1） anbnambm| n，m>=0 （2） 1n0m 1m0n| n，m>=0 （3）WaWr|W 屬于0|a*，Wr 表示

29、 W 的逆 答案： （） S®AA A®aAb|e （） S®1S0|A A®0A1|e （） S®0S0|1S1|e 盛威網(wǎng)（）專業(yè)的計算機學(xué)習(xí)網(wǎng)站 7編譯原理課后習(xí)題答案第三章 第 16 題 給出生成下述語言的三型文法： (1)an|n >=0 (2) anbm|n,m>=1 (3)anbmck|n,m,k>=0 答案： (1) S®aS|e (2) S®aA A®aA|B B®bB|b (3) A®aA|B B®bB|C C®cC|e 第 17 題 習(xí)

30、題和習(xí)題 11 中的文法等價嗎？ 答案： 等價。 第 18 題 解釋下列術(shù)語和概念： （） 字母表 （） 串、字和句子 （） 語言、語法和語義 答案： （）字母表：是一個非空有窮集合。 （）串：符號的有窮序列。 字：字母表中的元素。 +句子：如果 Z x , x ÎV *T 則稱 x 是文法 G 的一個句子。 盛威網(wǎng)（）專業(yè)的計算機學(xué)習(xí)網(wǎng)站 8編譯原理課后習(xí)題答案第三章 （）語言：它是由句子組成的集合，是由一組記號所構(gòu)成的集合。程序設(shè)計的語言就是所 有該語言的程序的全體。語言可以看成在一個基本符號集上定義的，按一定規(guī) 則構(gòu)成的一切基本符號串組成的集合。 語法：表示構(gòu)成語言句子的各個記

31、號之間的組合規(guī)律。程序的結(jié)構(gòu)或形式。 語義：表示按照各種表示方法所表示的各個記號的特定含義。語言所代表的含義。 盛威網(wǎng)（）專業(yè)的計算機學(xué)習(xí)網(wǎng)站 9編譯原理課后習(xí)題答案第三章 附加題 問題 1： 給出下述文法所對應(yīng)的正規(guī)式： S®0A|1B A®1S|1 B®0S|0 答案： R = (01 | 10) ( 01 | 10 )* 問題 2： 已知文法 GA，寫出它定義的語言描述 GA: A ® 0B|1C B ® 1|1A|0BB C ® 0|0A|1CC 答案: GA定義的語言由 0、1 符號串組成，串中 0 和 1 的個數(shù)相同. 問

32、題 3： 給出語言描述，構(gòu)造文法. 構(gòu)造一文法,其定義的語言是由算符+, *, (,)和運算對象 a 構(gòu)成的算術(shù)表達式的集合. 答案一： GE E®E+T|T T®T* F|F F®(E)|a 答案二： GE E®E+E|E* E|(E)|a 問題 4： 已知文法 GS: S®dAB 盛威網(wǎng)（）專業(yè)的計算機學(xué)習(xí)網(wǎng)站 10 編譯原理課后習(xí)題答案第三章 A®aA|a B®e|bB 相應(yīng)的正規(guī)式是什么？GS能否改寫成為等價的正規(guī)文法？ 答案： 正規(guī)式是 daa*b*； 相應(yīng)的正規(guī)文法為(由自動機化簡來)： GS:S®dA

33、 A®a|aB B®aB|a|b|bC C®bC|b 也可為(觀察得來):GS:S®dA A®a|aA|aB 問題 5： 已知文法 G： E®E+T|E-T|T T®T*F|T/F|F F®(E)|i 試給出下述表達式的推導(dǎo)及語法樹 (1) i; (2) i*i+i (3) i+i*i (4) i+(i+i) 答案： (1)E=>T=>F=>i B®bB|e (2)E=>E+T=>T+T=>T*F+T=>F*F+T=>i*F+T=>i*i+T=>

34、i*i+F=>i*i+i (3)E=>E+T=>T+T=>F+T=>i+T=>i+T*F=>i+F*F=>i+i*F=>i+i*i (4)E=>E+T=>T+T=>F+T=>i+T=>i+F=>i+(E)=>i+(E+T)=>i+(T+T)=>i+(F+T) =>i+(i+T)=>i+(i+F)=>i+(i+i) ETFTT* EE+FTFET+TETE+TFiFiiFFiF( E)(1) i(2) ii(3) iETFi+T Fi(4) 盛威網(wǎng)（）專業(yè)的計算機學(xué)習(xí)網(wǎng)站

35、 11 編譯原理課后習(xí)題答案第三章 問題 6： 已知文法 GE: E®ET+|T T®TF* | F F®F | a 試證：FF*是文法的句型，指出該句型的短語、簡單短語和句柄. 答案： 該句型對應(yīng)的語法樹如下： 該句型相對于 E 的短語有 FF* 相對于 T 的短語有 FF*,F 相對于 F 的短語有 F;F 簡單短語有 F;F 句柄為 F. 問題 7： 適當(dāng)變換文法，找到下列文法所定義語言的一個無二義的文法： S ® SaS SbS ScS d 答案： 該文法的形式很典型，可以先采用優(yōu)先級聯(lián)規(guī)則變換文法，然后再規(guī)定結(jié)合性對文法做 進一步變換，即可消除

36、二義性。 設(shè) a、b 和 c 的優(yōu)先級別依次增高，根據(jù)優(yōu)先級聯(lián)規(guī)則將文法變換為： S ® SaS A A ® AbA C C ® CcC d 規(guī)定結(jié)合性為左結(jié)合，進一步將文法變換為： S ® SaA A A ® AbC C C ® CcF F F®d 該文法為非二義的。 盛威網(wǎng)（）專業(yè)的計算機學(xué)習(xí)網(wǎng)站 12 編譯原理課后習(xí)題答案第三章 問題 8： 構(gòu)造產(chǎn)生如下語言的上下文無關(guān)文法： （1） anb2ncm | n，m ³ 0 （2） anbmc2m | n，m ³ 0 （3） ambn m ³

37、n （4） a m b n c p d q m+n = p+q （5） uawb u,w Îa, b* Ù | u | = | w | 答案： （1）根據(jù)上下文無關(guān)文法的特點，要產(chǎn)生形如anb2ncm的串，可以分別產(chǎn)生形如 anb2n 和 形如 cm 的串。設(shè)計好的文法是否就是該語言的文法？嚴(yán)格地說，應(yīng)該給出證明。但若不是 特別指明，通?？梢院雎赃@一點。 對于該語言，存在一個由以下產(chǎn)生式定義的上下文無關(guān)文法 GS： S ® AB A ® e aAbb B ® e cB （2）同樣，要產(chǎn)生形如anbmc2m的串，可以分別產(chǎn)生形如 an 和形如 b

38、mc2m 的串。對于該語 言，存在一個由以下產(chǎn)生式定義的上下文無關(guān)文法GS： S ® AB A ® e aA B ® e bBcc （3）考慮在先產(chǎn)生同樣數(shù)目的 a,b，然后再生成多余的 a。以下 GS是一種解法： S ® aSb aS e （4）以下 GS是一種解法： S ® aSd A D A ® bAd B D ® aDc B B ® bBc e 注：a 不多于 d 時，b 不少于 c；反之，a 不少于 d 時，b 不多于 c。前一種情形通過 對應(yīng) A，后一種情形對應(yīng) D。 （5）以下 GS是一種解法： S

39、® Ab A ® BAB a 盛威網(wǎng)（）專業(yè)的計算機學(xué)習(xí)網(wǎng)站 13 編譯原理課后習(xí)題答案第三章 B®ab 問題 9： 下面的文法 G(S)描述由命題變量 p、q ，聯(lián)結(jié)詞 Ù（合?。?Ú（析取） ¬（否定）構(gòu) 、成的命題公式集合： S®SÚTT T®TÙFF F®¬Fpq 試指出句型 ¬ F Ú ¬ q Ù p 的直接短語（全部）以及句柄。 答案： 直接短語：p，q，¬F 句柄：¬F 問題 10： 設(shè)字母表 A=a，

40、符號串 x=aaa，寫出下列符號串及其長度：x0,xx,x5 以及 A+. 答案： x0=(aaa)0=e | x0|=0 xx=aaaaaa |xx|=6 x5=aaaaaaaaaaaaaaa | x5|=15 A+ =A1 È A2 È ¼. È A n ȼ=a,aa,aaa,aaaa,aaaaa¼ A* = A0 ÈA1 È A2 È ¼. È A n ȼ=e,a,aa,aaa,aaaa,aaaaa¼ 問題 11： 令å=a，

41、b，c，又令 x=abc，y=b，z=aab，寫出如下符號串及它們的長度：xy，xyz， （xy）3 答案： xy=abcb |xy|=4 xyz=abcbaab |xyz|=7 (xy)3=(abcb)3 =abcbabcbabcb | (xy)3 |=12 問題 12： 已知文法 GZ：Z=U0V1 、 U=Z11 、V=Z00 ,請寫出全部由此文 法描述的只含有四個符號的句子。 盛威網(wǎng)（）專業(yè)的計算機學(xué)習(xí)網(wǎng)站 14 編譯原理課后習(xí)題答案第三章 答案： Z=>U0=>Z10=>U010=>1010 Z=>U0=>Z10=>V110=>0110

42、 Z=>V1=>Z00=>U000=>1000 Z=>V1=>Z00=>V100=>0100 問題 13： 已知文法 GS： S=AB 答案： A=aAe B=bBcbc , 寫出該文法描述的語言。 A=aAe描述的語言: an|n>=0 B=bBcbc描述的語言:,bncn|n>=1 L(GS)=anbmcm|n>=0,m>=1 問題 14： 已知文法E=TE+TE-T 、 T=FT*FT/F 、 F=(E)i，寫出該文法的開 始符號、終結(jié)符號集合VT、非終結(jié)符號集合VN。 答案： 開始符號：E VT=+, - , *

43、, / ,（ , ）, i VN=E , F , T 問題 15： 設(shè)有文法 GS：S=S*S|S+S|(S)|a，該文法是二義性文法嗎？ 答案： 根據(jù)所給文法推導(dǎo)出句子 a+a*a，畫出了兩棵不同的語法樹，所以該文法是二義性文法。 盛威網(wǎng)（）專業(yè)的計算機學(xué)習(xí)網(wǎng)站 15 編譯原理課后習(xí)題答案第三章 SSS*SS+SS+SaaS*Saaaa問題 16： 寫一文法，使其語言是奇正整數(shù)集合。 答案： A:=1|3|5|7|9|NA N:=N0|N1|N2|N3|N4|N5|N6|N7|N8|N9| N:=0|1|2|3|4|5|6|7|8|9 盛威網(wǎng)（）專業(yè)的計算機學(xué)習(xí)網(wǎng)站 16 編譯原理課后習(xí)題答案第四章 第4章 詞法分析 第1題 構(gòu)造下列正規(guī)式相應(yīng)的 DFA. （） 1(0|1)*101 （） (10