編譯原理課后習(xí)題答案+清華大學(xué)出版社第二版

編譯原理 課后習(xí)題答案第一章 1 第 1 章 引論 第 1 題 解釋下列術(shù)語 1 編譯程序 2 源程序 3 目標(biāo)程序 4 編譯程序的前端 5 后端 6 遍 答案 1 編譯程序 如果源語言為高級(jí)語言 目標(biāo)語言為某臺(tái)計(jì)算機(jī)上的匯編語言或機(jī)器語 言 則此翻譯程序稱為編譯程序 2 源程序 源語言編寫的程序稱為源程序 3 目標(biāo)程序 目標(biāo)語言書寫的程序稱為目標(biāo)程序 4 編譯程序的前端 它由這樣一些階段組成 這些階段的工作主要依賴于源語言而與 目標(biāo)機(jī)無關(guān) 通常前端包括詞法分析 語法分析 語義分析和中間代碼生成這些階 段 某些優(yōu)化工作也可在前端做 也包括與前端每個(gè)階段相關(guān)的出錯(cuò)處理工作和符 號(hào)表管理等工作 5 后端 指那些依賴于目標(biāo)機(jī)而一般不依賴源語言 只與中間代碼有關(guān)的那些階段 即目標(biāo)代碼生成 以及相關(guān)出錯(cuò)處理和符號(hào)表操作 6 遍 是對(duì)源程序或其等價(jià)的中間語言程序從頭到尾掃視并完成規(guī)定任務(wù)的過程 第 2 題 一個(gè)典型的編譯程序通常由哪些部分組成 各部分的主要功能是什么 并畫出編譯程序 的總體結(jié)構(gòu)圖 答案 一個(gè)典型的編譯程序通常包含 8個(gè)組成部分 它們是詞法分析程序 語法分析程序 語 義分析程序 中間代碼生成程序 中間代碼優(yōu)化程序 目標(biāo)代碼生成程序 表格管理程序和 錯(cuò)誤處理程序 其各部分的主要功能簡述如下 詞法分析程序 輸人源程序 拼單詞 檢查單詞和分析單詞 輸出單詞的機(jī)內(nèi)表達(dá)形式 語法分析程序 檢查源程序中存在的形式語法錯(cuò)誤 輸出錯(cuò)誤處理信息 語義分析程序 進(jìn)行語義檢查和分析語義信息 并把分析的結(jié)果保存到各類語義信息表 中 中間代碼生成程序 按照語義規(guī)則 將語法分析程序分析出的語法單位轉(zhuǎn)換成一定形式 的中間語言代碼 如三元式或四元式 中間代碼優(yōu)化程序 為了產(chǎn)生高質(zhì)量的目標(biāo)代碼 對(duì)中間代碼進(jìn)行等價(jià)變換處理 目標(biāo)代碼 生成程序 將優(yōu)化后的中間代碼程序轉(zhuǎn)換成目標(biāo)代碼程序 編譯原理 課后習(xí)題答案第一章 盛威網(wǎng) 專業(yè)的計(jì)算機(jī)學(xué)習(xí)網(wǎng)站 2 表格管理程序 負(fù)責(zé)建立 填寫和查找等一系列表格工作 表格的作用是記錄源程序的 各類信息和編譯各階段的進(jìn)展情況 編譯的每個(gè)階段所需信息多數(shù)都從表格中讀取 產(chǎn)生的 中間結(jié)果都記錄在相應(yīng)的表格中 可以說整個(gè)編譯過程就是造表 查表的工作過程 需要指 出的是 這里的 表格管理程序 并不意味著它就是一個(gè)獨(dú)立的表格管理模塊 而是指編譯 程序具有的表格管理功能 錯(cuò)誤處理程序 處理和校正源程序中存在的詞法 語法和語義錯(cuò)誤 當(dāng)編譯程序發(fā)現(xiàn)源 程序中的錯(cuò)誤時(shí) 錯(cuò)誤處理程序負(fù)責(zé)報(bào)告出錯(cuò)的位置和錯(cuò)誤性質(zhì)等信息 同時(shí)對(duì)發(fā)現(xiàn)的錯(cuò)誤 進(jìn)行適當(dāng)?shù)男Ｕ?修復(fù) 目的是使編譯程序能夠繼續(xù)向下進(jìn)行分析和處理 注意 如果問編譯程序有哪些主要構(gòu)成成分 只要回答六部分就可以 如果搞不清楚 就回答八部分 第 3 題 何謂翻譯程序 編譯程序和解釋程序 它們?nèi)咧g有何種關(guān)系 答案 翻譯程序是指將用某種語言編寫的程序轉(zhuǎn)換成另一種語言形式的程序的程序 如編譯程 序和匯編程序等 編譯程序是把用高級(jí)語言編寫的源程序轉(zhuǎn)換 加工 成與之等價(jià)的另一種用低級(jí)語言編 寫的目標(biāo)程序的翻譯程序 解釋程序是解釋 執(zhí)行高級(jí)語言源程序的程序 解釋方式一般分為兩種 一種方式是 源程序功能的實(shí)現(xiàn)完全由解釋程序承擔(dān)和完成 即每讀出源程序的一條語句的第一個(gè)單詞 則依據(jù)這個(gè)單詞把控制轉(zhuǎn)移到實(shí)現(xiàn)這條語句功能的程序部分 該部分負(fù)責(zé)完成這條語句的功 能的實(shí)現(xiàn) 完成后返回到解釋程序的總控部分再讀人下一條語句繼續(xù)進(jìn)行解釋 執(zhí)行 如此 反復(fù) 另一種方式是 一邊翻譯一邊執(zhí)行 即每讀出源程序的一條語句 解釋程序就將其翻 譯成一段機(jī)器指令并執(zhí)行之 然后再讀人下一條語句繼續(xù)進(jìn)行解釋 執(zhí)行 如此反復(fù) 無論 是哪種方式 其加工結(jié)果都是源程序的執(zhí)行結(jié)果 目前很多解釋程序采取上述兩種方式的綜 編譯原理 課后習(xí)題答案第一章 3 合實(shí)現(xiàn)方案 即先把源程序翻譯成較容易解釋執(zhí)行的某種中間代碼程序 然后集中解釋執(zhí)行 中間代碼程序 最后得到運(yùn)行結(jié)果 廣義上講 編譯程序和解釋程序都屬于翻譯程序 但它們的翻譯方式不同 解釋程序是 邊翻譯 解釋 邊執(zhí)行 不產(chǎn)生目標(biāo)代碼 輸出源程序的運(yùn)行結(jié)果 而編譯程序只負(fù)責(zé)把源 程序翻譯成目標(biāo)程序 輸出與源程序等價(jià)的目標(biāo)程序 而目標(biāo)程序的執(zhí)行任務(wù)由操作系統(tǒng)來 完成 即只翻譯不執(zhí)行 第 4 題 對(duì)下列錯(cuò)誤信息 請(qǐng)指出可能是編譯的哪個(gè)階段 詞法分析 語法分析 語義分析 代 碼生成 報(bào)告的 1 else 沒有匹配的 if 2 數(shù)組下標(biāo)越界 3 使用的函數(shù)沒有定義 4 在數(shù)中出現(xiàn)非數(shù)字字符 答案 1 語法分析 2 語義分析 3 語法分析 4 詞法分析 第 5題 編譯程序大致有哪幾種開發(fā)技術(shù) 答案 1 自編譯 用某一高級(jí)語言書寫其本身的編譯程序 2 交叉編譯 A 機(jī)器上的編譯程序能產(chǎn)生 B 機(jī)器上的目標(biāo)代碼 3 自展 首先確定一個(gè)非常簡單的核心語言 L0 用機(jī)器語言或匯編語言書寫出它的編 譯程序 T0 再把語言 L0 擴(kuò)充到 L1 此時(shí) L0 L1 并用 L0 編寫 L1 的編譯程序 T1 再把語 言 L1 擴(kuò)充為 L2 有 L1 L2 并用 L1 編寫 L2 的編譯程序 T2 如此逐步擴(kuò)展下 去 好似滾雪球一樣 直到我們所要求的編譯程序 4 移植 將 A 機(jī)器上的某高級(jí)語言的編譯程序搬到 B 機(jī)器上運(yùn)行 編譯原理 課后習(xí)題答案第一章 盛威網(wǎng) 專業(yè)的計(jì)算機(jī)學(xué)習(xí)網(wǎng)站 4 第 題 計(jì)算機(jī)執(zhí)行用高級(jí)語言編寫的程序有哪些途徑 它們之間的主要區(qū)別是什么 答案 計(jì)算機(jī)執(zhí)行用高級(jí)語言編寫的程序主要途徑有兩種 即解釋與編譯 像 Basic之類的語言 屬于解釋型的高級(jí)語言 它們的特點(diǎn)是計(jì)算機(jī)并不事先對(duì)高級(jí)語 言進(jìn)行全盤翻譯 將其變?yōu)闄C(jī)器代碼 而是每讀入一條高級(jí)語句 就用解釋器將其翻譯為一 條機(jī)器代碼 予以執(zhí)行 然后再讀入下一條高級(jí)語句 翻譯為機(jī)器代碼 再執(zhí)行 如此反復(fù) 總而言之 是邊翻譯邊執(zhí)行 像 C Pascal 之類的語言 屬于編譯型的高級(jí)語言 它們的特點(diǎn)是計(jì)算機(jī)事先對(duì)高級(jí)語 言進(jìn)行全盤翻譯 將其全部變?yōu)闄C(jī)器代碼 再統(tǒng)一執(zhí)行 即先翻譯 后執(zhí)行 從速度上看 編譯型的高級(jí)語言比解釋型的高級(jí)語言更快 編譯原理 課后習(xí)題答案第二章 1 第 2 章 PL 0 編譯程序的實(shí)現(xiàn) 第 1 題 PL 0 語言允許過程嵌套定義和遞歸調(diào)用 試問它的編譯程序如何解決運(yùn)行時(shí)的存儲(chǔ)管理 答案 PL 0 語言允許過程嵌套定義和遞歸調(diào)用 它的編譯程序在運(yùn)行時(shí)采用了棧式動(dòng)態(tài)存儲(chǔ) 管理 數(shù)組 CODE 存放的只讀目標(biāo)程序 它在運(yùn)行時(shí)不改變 運(yùn)行時(shí)的數(shù)據(jù)區(qū) S 是由解 釋程序定義的一維整型數(shù)組 解釋執(zhí)行時(shí)對(duì)數(shù)據(jù)空間 S 的管理遵循后進(jìn)先出規(guī)則 當(dāng)每個(gè) 過程 包括主程序 被調(diào)用時(shí) 才分配數(shù)據(jù)空間 退出過程時(shí) 則所分配的數(shù)據(jù)空間被釋放 應(yīng)用動(dòng)態(tài)鏈和靜態(tài)鏈的方式分別解決遞歸調(diào)用和非局部變量的引用問題 第 2 題 若 PL 0 編譯程序運(yùn)行時(shí)的存儲(chǔ)分配策略采用棧式動(dòng)態(tài)分配 并用動(dòng)態(tài)鏈和靜態(tài)鏈的方 式分別解決遞歸調(diào)用和非局部變量的引用問題 試寫出下列程序執(zhí)行到賦值語句 b 10 時(shí)運(yùn)行棧的布局示意圖 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 end p begin main call p end main 答案 程序執(zhí)行到賦值語句 b 10 時(shí)運(yùn)行棧的布局示意圖為 編譯原理 課后習(xí)題答案第二章 盛威網(wǎng) 專業(yè)的計(jì)算機(jī)學(xué)習(xí)網(wǎng)站 2 第 3 題 寫出題 2 中當(dāng)程序編譯到 r 的過程體時(shí)的名字表 table 的內(nèi)容 name kind level val adr size 答案 題 2 中當(dāng)程序編譯到 r 的過程體時(shí)的名字表 table 的內(nèi)容為 name kind level val adr size x variable 0 dx y variable 0 dx 1 p procedure 0 過程 p 的入口 待填 5 a variable 1 dx q procedure 1 過程 q 的入口 4 s procedure 1 過程 s 的入口 待填 5 c variable 2 dx d variable 2 dx 編譯原理 課后習(xí)題答案第二章 3 r procedure 2 過程 r 的入口 5 e variable 3 dx f variable 3 dx 1 注意 q 和 s 是并列的過程 所以 q 定義的變量 b 被覆蓋 第 4 題 指出棧頂指針 T 最新活動(dòng)記錄基地址指針 B 動(dòng)態(tài)鏈指針 DL 靜態(tài)鏈指針 SL 與 返回地址 RA 的用途 答案 棧頂指針 T 最新活動(dòng)記錄基地址指針 B 動(dòng)態(tài)鏈指針 DL 靜態(tài)鏈指針 SL 與返回地址 RA 的用途說明如下 T 棧頂寄存器 T 指出了當(dāng)前棧中最新分配的單元 T 也是數(shù)組 S 的下標(biāo) B 基址寄存器 指向每個(gè)過程被調(diào)用時(shí) 在數(shù)據(jù)區(qū) S 中給它分配的數(shù)據(jù)段起 始 地址 也稱基地址 SL 靜態(tài)鏈 指向定義該過程的直接外過程 或主程序 運(yùn)行時(shí)最新數(shù)據(jù)段的基地址 用以引用非局部 包圍它的過程 變量時(shí) 尋找該變量的地址 DL 動(dòng)態(tài)鏈 指向調(diào)用該過程前正在運(yùn)行過程的數(shù)據(jù)段基地址 用以過程執(zhí)行結(jié)束釋放 數(shù)據(jù)空間時(shí) 恢復(fù)調(diào)用該過程前運(yùn)行棧的狀態(tài) RA 返回地址 記錄調(diào)用該過程時(shí)目標(biāo)程序的斷點(diǎn) 即調(diào)用過程指令的下一條指令的地 址 用以過程執(zhí)行結(jié)束后返回調(diào)用過程時(shí)的下一條指令繼續(xù)執(zhí)行 在每個(gè)過程被調(diào)用時(shí)在棧頂分配 3 個(gè)聯(lián)系單元 用以存放 SL DL RA 第 5 題 PL 0 編譯程序所產(chǎn)生的目標(biāo)代碼是一種假想棧式計(jì)算機(jī)的匯編語言 請(qǐng)說明該匯編語 言中下列指令各自的功能和所完成的操作 INT 0 A OPR 0 0 CAL L A 答案 PL 0 編譯程序所產(chǎn)生的目標(biāo)代碼中有 3 條非常重要的特殊指令 這 3 條指令在 code 中的位置和功能以及所完成的操作說明如下 INT 0 A 在過程目標(biāo)程序的入口處 開辟 A 個(gè)單元的數(shù)據(jù)段 A 為局部變量的個(gè)數(shù) 3 OPR 0 0 在過程目標(biāo)程序的出口處 釋放數(shù)據(jù)段 退棧 恢復(fù)調(diào)用該過程前正在運(yùn)行的過程的數(shù) 據(jù)段基址寄存器 B 和棧頂寄存器 T 的值 并將返回地址送到指令地址寄存器 P 中 以使 調(diào)用前的程序從斷點(diǎn)開始繼續(xù)執(zhí)行 編譯原理 課后習(xí)題答案第二章 盛威網(wǎng) 專業(yè)的計(jì)算機(jī)學(xué)習(xí)網(wǎng)站 4 CAL L A 調(diào)用過程 完成填寫靜態(tài)鏈 動(dòng)態(tài)鏈 返回地址 給出被調(diào)用過程的基地址值 送入基址 寄存器 B 中 目標(biāo)程序的入口地址 A 的值送指令地址寄存器 P 中 使指令從 A 開始執(zhí)行 第 6 題 給出對(duì) PL 0 語言作如下功能擴(kuò)充時(shí)的語法圖和 EBNF 的語法描述 1 擴(kuò)充條件語句的功能使其為 if 條件 then 語句 else 語句 2 擴(kuò)充 repeat 語句為 repeat 語句 語句 until 條件 答案 對(duì) PL 0 語言作如下功能擴(kuò)充時(shí)的語法圖和 EBNF 的語法描述如下 1 擴(kuò)充條件語句的語法圖為 EBNF 的語法描述為 條件語句 if 條件 then 語句 else 語句 2 擴(kuò)充 repeat 語句的語法圖為 EBNF 的語法描述為 重復(fù)語句 repeat 語句 語句 until 條件 編譯原理 課后習(xí)題答案第三章 盛威網(wǎng) 專業(yè)的計(jì)算機(jī)學(xué)習(xí)網(wǎng)站 1 第 3 章 文法和語言 第 1 題 文法 G A B S a b c P S 其中 P 為 S Ac aB A ab B bc 寫出 L G S 的全 部元素 答案 L G S abc 第 2 題 文法 G N 為 N D ND D 0 1 2 3 4 5 6 7 8 9 G N 的語言是什么 答案 G N 的語言是 V V 0 1 2 3 4 5 6 7 8 9 N ND NDD NDDDD D D D 或者 允許 0 開頭的非負(fù)整數(shù) 第 題 為只包含數(shù)字 加號(hào)和減號(hào)的表達(dá)式 例如 9 2 5 3 1 等構(gòu)造一個(gè)文法 答案 G S S S D S D D D 0 1 2 3 4 5 6 7 8 9 第 4 題 已知文法 G Z Z aZb ab 寫出 L G Z 的全部元素 編譯原理 課后習(xí)題答案第三章 盛威網(wǎng) 專業(yè)的計(jì)算機(jī)學(xué)習(xí)網(wǎng)站 2 答案 Z aZb aaZbb aaa Z bbb aaa ab bbb n n L G Z a b 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 N 0 G D 0 第 6 題 已知文法 G i 試給出下述表達(dá)式的推導(dǎo)及語法樹 i i i i i i 編譯原理 課后習(xí)題答案第三章 盛威網(wǎng) 專業(yè)的計(jì)算機(jī)學(xué)習(xí)網(wǎng)站 3 答案 5 i i i i i i i i i i i i 6 i i i i i i i i i i i i i i i i i 編譯原理 課后習(xí)題答案第三章 盛威網(wǎng) 專業(yè)的計(jì)算機(jī)學(xué)習(xí)網(wǎng)站 4 第 7 題 證明下述文法 G 表達(dá)式 是二 義的 表達(dá)式 a 表達(dá)式 表達(dá)式 運(yùn)算符 表達(dá)式 運(yùn)算符 答案 可為句子 a a a 構(gòu)造兩個(gè)不同的最右推導(dǎo) 最右推 導(dǎo) 1 表達(dá)式 表達(dá)式 運(yùn)算符 表達(dá)式 表達(dá)式 運(yùn)算符 a 表達(dá)式 a 表達(dá)式 運(yùn)算符 表達(dá)式 a 表達(dá)式 運(yùn)算符 a a 表達(dá)式 a a a a a 最右推導(dǎo) 2 表達(dá)式 表達(dá)式 運(yùn)算符 表達(dá)式 表達(dá)式 運(yùn)算符 表達(dá)式 運(yùn)算符 表達(dá)式 表達(dá)式 運(yùn)算符 表達(dá)式 運(yùn)算符 a 表達(dá)式 運(yùn)算符 表達(dá)式 a 表達(dá)式 運(yùn)算符 a a 表達(dá)式 a a a a a 第 8 題 文法 G S 為 S Ac aB A ab B bc 該文法是否為二義的 為什么 答案 對(duì)于串 abc 1 S Ac abc 2 S aB abc 即存在兩不同的最右推導(dǎo) 所以 該文法是二義的 編譯原理 課后習(xí)題答案第三章 盛威網(wǎng) 專業(yè)的計(jì)算機(jī)學(xué)習(xí)網(wǎng)站 5 或者 對(duì)輸入字符串 abc 能構(gòu)造兩棵不同的語法樹 所以它是二義的 S a B b c S A c a b 第 9 題 考慮下面上下文無關(guān)文法 S SS SS a 1 表明通過此文法如何生成串 aa a 并為該串構(gòu)造 語法樹 2 G S 的語言是什么 答案 1 此文法生成串 aa a 的最右推導(dǎo)如下 S SS SS Sa SS a Sa a aa a 2 該文法生成的語言是 和 的后綴表達(dá)式 即逆波蘭式 第 10 題 文法 S S S S 1 生成的語言是什么 2 該文法是二義的嗎 說明理由 答案 嵌套的括號(hào) 是二義的 因?yàn)閷?duì)于 可以構(gòu)造兩棵不同的語法樹 S S S a S S a a 編譯原理 課后習(xí)題答案第三章 盛威網(wǎng) 專業(yè)的計(jì)算機(jī)學(xué)習(xí)網(wǎng)站 6 第 11 題 令文法 G E 為 E T E T E T T F T F T F F E i 證明 E T F 是它的一個(gè)句型 指出這個(gè)句型的所有短語 直接短語和句柄 答案 此句型對(duì)應(yīng)語法樹如右 故為此文法一個(gè)句型 或者 因?yàn)榇嬖谕茖?dǎo)序列 E E T E T F 所 以 E T F 句型 此句型相對(duì)于 E 的短語有 E T F 相對(duì)于 T 的短 語 有 T F 直接短語為 T F 句柄為 T F 第 13 題 一個(gè)上下文無關(guān)文法生成句子 abbaa 的推導(dǎo)樹如下 1 給出串 abbaa 最左推導(dǎo) 最右推導(dǎo) 2 該文法的產(chǎn)生式集合 P 可能有哪些元素 3 找出該句子的所有短語 直接短語 句 柄 a 答案 1 串 abbaa 最左推導(dǎo) S ABS aBS aSBBS aBBS abBS abbS abbAa abbaa 最右推導(dǎo) S ABS ABAa ABaa ASBBaa ASBbaa ASbbaa Abbaa abbaa 2 產(chǎn)生式有 S ABS Aa A a B SBB b 可能元素有 aa ab abbaa aaabbaa 3 該句子的短語有 a 是相 對(duì) A 的短語 是相對(duì) S 的短語 b 是相對(duì) B 的短語 bb 是相對(duì) B B S A B S a S B A b b a 編譯原理 課后習(xí)題答案第三章 盛威網(wǎng) 專業(yè)的計(jì)算機(jī)學(xué)習(xí)網(wǎng)站 7 的短語 aa 是相對(duì) S 的 短語 a bbaa 是相對(duì) S 的短語 直接短語有 a b 句柄是 a 第 14 題 給出生成下述語言的上下文無關(guān)文法 1 anbnambm n m 0 2 1n0m 1m0n n m 0 3 WaWr W 屬于 0 a Wr 表示 W 的逆 答案 S AA A aAb S 1S0 A A 0A1 S 0S0 1S1 第 16 題 給出生成下述語言的三型文 法 1 an n 0 2 anbm n m 1 3 anbmck n m k 0 答案 1 S aS 2 編譯原理 課后習(xí)題答案第三章 盛威網(wǎng) 專業(yè)的計(jì)算機(jī)學(xué)習(xí)網(wǎng)站 8 S aA A aA B B bB b 3 A aA B B bB C C cC 第 17 題 習(xí)題 和習(xí)題 11 中的文法等價(jià)嗎 答案 等價(jià) 第 18 題 解釋下列術(shù)語和概念 字母表 串 字和句子 語言 語法和語義 答案 字母表 是一個(gè)非空有窮集合 串 符號(hào)的有窮序列 字 字母表中的元素 句子 如果 Z x x V T 則稱 x 是文法 G 的一個(gè)句子 語言 它是由句子組成的集合 是由一組記號(hào)所構(gòu)成的集合 程序設(shè)計(jì)的語言就是所 有該語言的程序 的全體 語言可以看成在一個(gè)基本符號(hào)集上定義的 按一定規(guī)則構(gòu)成的一切基 本符號(hào)串組成的集合 語法 表示構(gòu)成語言句子的各個(gè)記號(hào)之間的組合規(guī)律 程序的結(jié)構(gòu)或形式 語義 表示按照各種表示方法所表示的各個(gè)記號(hào)的特定含義 語言所代表的含義 編譯原理 課后習(xí)題答案第三章 盛威網(wǎng) 專業(yè)的計(jì)算機(jī)學(xué)習(xí)網(wǎng)站 9 附加題 問題 1 給出下述文法所對(duì)應(yīng)的正規(guī)式 S 0A 1B A 1S 1 B 0S 0 答案 R 01 10 01 10 問題 2 已知文法 G A 寫出它定義的語言描述 G A A 0B 1C B 1 1A 0BB C 0 0A 1CC 答案 G A 定義的語言由 0 1 符號(hào)串組成 串中 0 和 1 的個(gè)數(shù)相同 問題 3 給出語言描述 構(gòu)造文法 構(gòu)造一文法 其定義的語言是由算符 和運(yùn)算對(duì)象 a 構(gòu)成的算術(shù)表達(dá)式的集合 答案一 G E E E T T T T F F F E a 答案二 G E E E E E E E a 問題 4 已知文法 G S S dAB A aA a B bB 編譯原理 課后習(xí)題答案第三章 盛威網(wǎng) 專業(yè)的計(jì)算機(jī)學(xué)習(xí)網(wǎng)站 10 相應(yīng)的正規(guī)式是什么 G S 能否改寫成為等價(jià)的正規(guī)文法 答案 正規(guī)式是 daa b 相應(yīng)的正規(guī)文法為 由自動(dòng)機(jī)化簡來 G S S dA A a aB B aB a b bC C bC b 也可為 觀察得來 G S S dA A a aA aB B bB 問題 5 已知文法 G E E T E T T T T F T F F F E i 試給出下述表達(dá)式的推導(dǎo)及語法樹 1 i 2 i i i 3 i i i 4 i i i 答案 1 E T F i 2 E E T T T T F T F F T i F T i i T 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 E E T F F i 1 i 2 3 E E T E T i T F F E i T F i F 4 E T T T F F i i E T i T F i F i 編譯原理 課后習(xí)題答案第三章 盛威網(wǎng) 專業(yè)的計(jì)算機(jī)學(xué)習(xí)網(wǎng)站 11 問題 6 已知文法 G E E ET T T TF F F F a 試證 FF 是文法的句型 指出該句型的短語 簡單短語和句柄 答案 該句型對(duì)應(yīng)的語法樹如下 該句型相對(duì)于 E 的短語有 FF 相對(duì)于 T 的短語有 FF F 相對(duì)于 F 的短語有 F F 簡單短 語有 F F 句柄為 F 問題 7 適當(dāng)變換文法 找到下列文法所定義語言的一個(gè)無二義的文法 S SaS SbS ScS d 答案 該文法的形式很典型 可以先采用優(yōu)先級(jí)聯(lián)規(guī)則變換文法 然后再規(guī)定結(jié)合性對(duì)文法做進(jìn) 一步變換 即可消除二義性 設(shè) a b 和 c 的優(yōu)先級(jí)別依次增高 根據(jù)優(yōu)先級(jí)聯(lián)規(guī)則將文法變換為 S SaS A A AbA C C CcC d 規(guī)定結(jié)合性為左結(jié)合 進(jìn)一步將文法變換為 S SaA A A AbC C 編譯原理 課后習(xí)題答案第三章 盛威網(wǎng) 專業(yè)的計(jì)算機(jī)學(xué)習(xí)網(wǎng)站 12 C CcF F F d 該文法為非二義的 問題 8 構(gòu)造產(chǎn)生如下語言的上下文無關(guān)文法 1 anb2ncm n m 0 2 anbmc2m n m 0 3 ambn m 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)文法的特點(diǎn) 要產(chǎn)生形如 anb2ncm 的串 可以分別產(chǎn)生形如 a nb2n 和 形如 c m 的串 設(shè)計(jì)好的文法是否就是該語言的文法 嚴(yán)格地說 應(yīng)該給出證明 但若不是 特別指明 通?？梢院雎赃@一點(diǎn) 對(duì)于該語言 存在一個(gè)由以下產(chǎn)生式定義的上下文無關(guān)文法 G S S AB A aAbb B cB 2 同樣 要產(chǎn)生形如 anbmc2m 的串 可以分別產(chǎn)生形如 a n 和形如 b mc2m 的串 對(duì)于該 語言 存在一個(gè)由以下產(chǎn)生式定義的上下文無關(guān)文法 G S S AB A aA B bBcc 3 考慮在先產(chǎn)生同樣數(shù)目的 a b 然后再生成多余的 a 以下 G S 是一種解法 S aSb aS 4 以下 G S 是一種解法 S aSd A D A bAd B D aDc B 編譯原理 課后習(xí)題答案第三章 盛威網(wǎng) 專業(yè)的計(jì)算機(jī)學(xué)習(xí)網(wǎng)站 13 B bBc 注 a 不多于 d 時(shí) b 不少于 c 反之 a 不少于 d 時(shí) b 不多于 c 前一種情形通過對(duì) 應(yīng) A 后一種情形對(duì)應(yīng) D 5 以下 G S 是一種解法 S Ab A BAB a B a b 問題 9 下面的文法 G S 描述由命題變量 p q 聯(lián)結(jié)詞 合取 析取 否定 構(gòu) 成的命題公式集合 S S T T T T F F F F p q 試指出句型 F q p 的直接短語 全部 以及句柄 答案 直接短語 p q F 句柄 F 問題 10 設(shè)字母表 A a 符號(hào)串 x aaa 寫出下列符號(hào)串及其長度 x0 xx x5 以及 A 答案 x0 aaa 0 x0 0 xx aaaaaa xx 6 x5 aaaaaaaaaaaaaaa x5 15 A A1 A 2 A n a aa aaa aaaa aaaaa A A0 A 1 A2 A n a aa aaa aaaa aaaaa 問題 11 令 a b c 又令 x abc y b z aab 寫出如下符號(hào)串及它們的長度 xy xyz xy 3 答案 xy abcb xy 4 xyz abcbaab xyz 7 編譯原理 課后習(xí)題答案第三章 盛威網(wǎng) 專業(yè)的計(jì)算機(jī)學(xué)習(xí)網(wǎng)站 14 xy 3 abcb 3 abcbabcbabcb xy 3 12 問題 12 已知文法 G Z Z U0 V1 U Z1 1 V Z0 0 請(qǐng)寫出全部由此文法描述 的只含有四個(gè)符號(hào)的句子 答案 Z U0 Z10 U010 1010 Z U0 Z10 V110 0110 Z V1 Z00 U000 1000 Z V1 Z00 V100 0100 問題 13 已知文法 G S S AB A aA B bBc bc 寫出該文法描述的語言 答案 A aA 描述的語言 a n n 0 B bBc bc 描述的語言 b ncn n 1 L G S anbmcm n 0 m 1 問題 14 已知文法 E T E T E T T F T F T F F E i 寫出該文法的開始 符號(hào) 終結(jié)符號(hào)集合 VT 非終結(jié)符號(hào)集合 VN 答案 開始符號(hào) E VT i VN E F T 問題 15 設(shè)有文法 G S S S S S S S a 該文法是二義性文法嗎 編譯原理 課后習(xí)題答案第三章 盛威網(wǎng) 專業(yè)的計(jì)算機(jī)學(xué)習(xí)網(wǎng)站 15 答案 根據(jù)所給文法推導(dǎo)出句子 a a a 畫出了兩棵不同的語法樹 所以該文法是二義性文法 S S S S S a a a S S S S S a a a 問題 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 編譯原理 課后習(xí)題答案第四章 盛威網(wǎng) 專業(yè)的計(jì)算機(jī)學(xué)習(xí)網(wǎng)站 1 第 4 章 詞法分析 第 1 題 構(gòu)造下列正規(guī)式相應(yīng)的 DFA 1 0 1 101 1010 1 010 1 0 a a b ab a b b ab bb ab 答案 1 先構(gòu)造 NFA 用子集法將 NFA 確定化 0 1 X A A A AB AB AC AB AC A ABY ABY AC AB 除 X A 外 重新命名其他狀態(tài) 令 AB 為 B AC 為 C ABY 為 D 因?yàn)?D 含有 Y NFA 的終態(tài) 所以 D 為終態(tài) 0 1 X A A A B B C B C A D D C B DFA 的狀態(tài)圖 編譯原理 課后習(xí)題答案第四章 盛威網(wǎng) 專業(yè)的計(jì)算機(jī)學(xué)習(xí)網(wǎng)站 2 2 先構(gòu)造 NFA X A1 B 1 C 0 D 1 E 0 F 1 G 0 H 1 I 0 J 1 K L 0 Y 用子集法將 NFA 確定化 0 1 X X T0 X A A ABFL T1 ABFL Y CG Y Y CG CGJ T2 Y T3 CGJ DH K DH DH K ABFKL T4 DH EI EI ABEFIL T5 ABFKL Y CG T6 ABEFIL EJY CG EJY ABEFGJLY T7 ABEFGJLY EHY CGK EHY ABEFHLY CGK ABCFGJKL T8 ABEFHLY EY CGI EY ABEFLY CGI CGJI T9 ABCFGJKL DHY CGK DHY DHY T10 ABEFLY EY CG T11 CGJI DHJ K 編譯原理 課后習(xí)題答案第四章 盛威網(wǎng) 專業(yè)的計(jì)算機(jī)學(xué)習(xí)網(wǎng)站 3 DHJ DHJ T12 DHY EI T13 DHJ EIK EIK ABEFIKL T14 ABEFIKL EJY CG 將 T0 T 1 T 2 T3 T 4 T 5 T6 T 7 T 8 T 9 T 10 T 11 T12 T 13 T 14重新命名 分別用 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 表示 因?yàn)?2 7 8 10 12 中含 有 Y 所以它們都為終態(tài) 0 1 0 1 1 2 3 2 3 4 5 4 6 5 2 3 6 7 3 7 8 9 8 10 11 9 12 9 10 10 3 11 13 5 12 6 13 14 14 7 3 編譯原理 課后習(xí)題答案第四章 盛威網(wǎng) 專業(yè)的計(jì)算機(jī)學(xué)習(xí)網(wǎng)站 4 0 1 0 12 1 2 7 810 3 4 5 6 9 11 13 14 1 1 0 1 0 1 0 1 1 0 1 1 0 1 0 1 10 0 1 0 1 用子集法將 NFA 確定化 a b X X T0 X A A ABCD T1 ABCD BE BY BE ABCDE BY ABCDY T2 ABCDE BEF BEY BEF ABCDEF BEY ABCDEY T3 ABCDY BE BY T4 ABCDEF BEF BEY T5 ABCDEY BEF BEY 將 T0 T 1 T 2 T3 T 4 T 5重新命名 分別用 0 1 2 3 4 5 表示 因?yàn)?3 5 中含有 Y 所以它們都為終態(tài) a b 0 1 1 2 3 3 先構(gòu)造 NFA 先構(gòu)造 NFA X Aa B a b D a E a F C Y b b 編譯原理 課后習(xí)題答案第四章 盛威網(wǎng) 專業(yè)的計(jì)算機(jī)學(xué)習(xí)網(wǎng)站 5 2 4 5 3 2 3 4 4 5 5 4 5 0 a b 1 3 2 a 5 4 a b a b a b a b 4 先構(gòu)造 NFA X Ab B a F b G b H E Ya C Db I b 用子集法將 NFA 確定化 a b X X T0 X A A ABDEF T1 ABDEF CI G CI CI G G T2 CI DY DY ABDEFY T3 G H H ABEFH 編譯原理 課后習(xí)題答案第四章 盛威網(wǎng) 專業(yè)的計(jì)算機(jī)學(xué)習(xí)網(wǎng)站 6 T4 ABDEFY CI G T5 ABEFH CI G 將 T0 T 1 T 2 T 3 T 4 T 5重新命名 分別用 0 1 2 3 4 5 表示 因?yàn)?4 中含有 Y 所以它為終態(tài) a b 0 1 1 2 3 2 4 3 5 4 2 3 5 2 3 DFA 的狀態(tài)圖 0 b b1 2 a 4 5 3 b b a b a b 編譯原理 課后習(xí)題答案第四章 盛威網(wǎng) 專業(yè)的計(jì)算機(jī)學(xué)習(xí)網(wǎng)站 7 第 題 已知 NFA x y z 0 1 M x z 其中 M x 0 z M y 0 x y M z 0 x z M x 1 x M y 1 M z 1 y 構(gòu)造相應(yīng)的 DFA 答案 先構(gòu)造其矩陣 0 1 x z x y x y z x z y 用子集法將 NFA 確定化 0 1 x z x z xz y xz xz xy y xy xy xyz x xyz xyz xy 將 x z xz y xy xyz 重新命名 分別用 A B C D E F 表示 因?yàn)?B C F 中含有 z 所以它為終態(tài) 0 1 A B A B C D C C E D E E F A F F E 編譯原理 課后習(xí)題答案第四章 盛威網(wǎng) 專業(yè)的計(jì)算機(jī)學(xué)習(xí)網(wǎng)站 8 DFA 的狀態(tài)圖 A 0 1 0 F E D 0 B 1 0 1 0 1 0 1 C 第 3 題 將下圖確定化 答案 用子集法將 NFA 確定化 0 1 S VQ QU VQ VZ QU QU V QUZ VZ Z Z V Z QUZ VZ QUZ Z Z Z 重新命名狀態(tài)子集 令 VQ 為 A QU 為 B VZ 為 C V 為 D QUZ 為 E Z 為 F 0 1 編譯原理 課后習(xí)題答案第四章 盛威網(wǎng) 專業(yè)的計(jì)算機(jī)學(xué)習(xí)網(wǎng)站 9 S A B A C B B D E C F F D F E C E F F F DFA 的狀態(tài)圖 第 4 題 將下圖的 a 和 b 分別確定化和最小化 答案 初始分劃得 0 終態(tài)組 0 非終態(tài)組 1 2 3 4 5 對(duì)非終態(tài)組進(jìn)行審查 1 2 3 4 5 a 0 1 3 5 而 0 1 3 5 既不屬于 0 也不屬于 1 2 3 4 5 編譯原理 課后習(xí)題答案第四章 盛威網(wǎng) 專業(yè)的計(jì)算機(jī)學(xué)習(xí)網(wǎng)站 10 4 a 0 所以得到新分劃 1 0 4 1 2 3 5 對(duì) 1 2 3 5 進(jìn)行審查 1 5 b 4 2 3 b 1 2 3 5 故得到新分劃 2 0 4 1 5 2 3 1 5 a 1 5 2 3 a 1 3 故狀態(tài) 2 和狀態(tài) 3 不等價(jià) 得到新分劃 3 0 2 3 4 1 5 這是最后分劃了 最小 DFA 第 5 題 構(gòu)造一個(gè) DFA 它接收 0 1 上所有滿足如下條件的字符串 每個(gè) 1 都有 0 直接跟在 右邊 并給出該語言的正規(guī)式 答案 按題意相應(yīng)的正規(guī)表達(dá)式是 0 10 0 或 0 0 10 0 構(gòu)造相應(yīng)的 DFA 首先構(gòu)造 NFA 為 用子集法確定化 I I0 I1 X 0 1 3 Y 0 1 3 Y 2 1 3 Y 0 1 3 Y 0 1 3 Y 1 3 Y 1 3 Y 2 2 2 重新命名狀態(tài)集 S 0 1 編譯原理 課后習(xí)題答案第四章 盛威網(wǎng) 專業(yè)的計(jì)算機(jī)學(xué)習(xí)網(wǎng)站 11 1 2 3 4 2 2 4 4 3 3 3 DFA 的狀態(tài)圖 可將該 DFA 最小化 終態(tài)組為 1 2 4 非終態(tài)組為 3 1 2 4 0 1 2 4 1 2 4 1 3 所以 1 2 4 為等價(jià)狀態(tài) 可合并 第 題 設(shè)無符號(hào)數(shù)的正規(guī)式為 dd dd dd dd dd 10 s dd 10 s dd dd 10 s dd dd dd 10 s dd 化簡 畫出 的 DFA 其中 d 0 1 2 9 s 答案 先構(gòu)造 NFA X d B d F G d H 10 d A C 10 d D s E d Y d s d 用子集法將 NFA 確定化 編譯原理 課后習(xí)題答案第四章 盛威網(wǎng) 專業(yè)的計(jì)算機(jī)學(xué)習(xí)網(wǎng)站 12 s 10 d X XA T0 XA B F A B B F FG A A T1 B C C C T2 FG G H G G H H T3 A B F A T4 C D C D DE T5 G H T6 H H T7 DE E Y E E Y Y T8 E Y T9 Y Y 將 XA B FG A C G H DE E Y 重新命名 分別用 0 1 2 3 4 5 6 7 8 9 表示 終態(tài)有 0 3 4 6 9 s 10 d 0 1 2 3 1 4 2 5 6 3 1 2 3 4 7 4 編譯原理 課后習(xí)題答案第四章 盛威網(wǎng) 專業(yè)的計(jì)算機(jī)學(xué)習(xí)網(wǎng)站 13 5 6 6 6 7 8 9 8 9 9 9 DFA 的狀態(tài)圖 d d 6 52 d 3 d 4 7 8 9 0 1 10 d s 10 10 d d s d d d 第 7 題 給文法 G S S aA bQ A aA bB b B bD aQ Q aQ bD b D bB aA E aB bF F bD aE b 構(gòu)造相應(yīng)的最小的 DFA 答案 先構(gòu)造其 NFA 編譯原理 課后習(xí)題答案第四章 盛威網(wǎng) 專業(yè)的計(jì)算機(jī)學(xué)習(xí)網(wǎng)站 14 S a A a Z Q b B D a E b F b b a b a a b bb b a b 用子集法將 NFA 確定化 a b S A Q A A BZ Q Q DZ BZ Q D DZ A B D A B B Q D 將 S A Q BZ DZ D B 重新命名 分別用 0 1 2 3 4 5 6 表示 因?yàn)?3 4 中含有 z 所以它們?yōu)榻K態(tài) a b 0 1 2 1 1 3 2 2 4 3 2 5 4 1 6 5 1 6 6 2 5 DFA 的狀態(tài)圖 編譯原理 課后習(xí)題答案第四章 盛威網(wǎng) 專業(yè)的計(jì)算機(jī)學(xué)習(xí)網(wǎng)站 15 0 a a 5 2 b 3 a a b 4 1 6 b a a b b b a b 令 P0 0 1 2 5 6 3 4 用 b 進(jìn)行分割 P1 0 5 6 1 2 3 4 再用 b 進(jìn)行分割 P2 0 5 6 1 2 3 4 再用 a b 進(jìn)行分割 仍不變 再令 為 A 1 2 為 B 3 4 為 C 5 6 為 D 最小化為 A a b D C a a B b a bb 第 題 給出下述文法所對(duì)應(yīng)的正規(guī)式 S 0A 1B A 1S 1 B 0S 0 答案 編譯原理 課后習(xí)題答案第四章 盛威網(wǎng) 專業(yè)的計(jì)算機(jī)學(xué)習(xí)網(wǎng)站 16 解方程組 S 的解 S 0A 1B A 1S 1 B 0S 0 將 A B 產(chǎn)生式的右部代入 S 中 S 01S 01 10S 10 01 10 S 01 10 所以 S 01 10 01 10 第 9 題 將下圖的 DFA 最小化 并用正規(guī)式描述它所識(shí)別的語言 1 a 2 6 c 3 c b 5 4 7 b b a b b b d d a 答案 令 P0 1 2 3 4 5 6 7 用 b 進(jìn)行分割 P1 1 2 3 4 5 6 7 再用 a b c d 進(jìn)行分割 仍不變 再令 1 2 為 A 3 4 為 B 5 為 C 6 7 為 D 最小化為 c A a C D b d B b a b 編譯原理 課后習(xí)題答案第四章 盛威網(wǎng) 專業(yè)的計(jì)算機(jī)學(xué)習(xí)網(wǎng)站 17 r b a c da bb b a c da b 編譯原理 課后習(xí)題答案第四章 盛威網(wǎng) 專業(yè)的計(jì)算機(jī)學(xué)習(xí)網(wǎng)站 18 附加題 問題 1 為下邊所描述的串寫正規(guī)式 字母表是 a b a 以 ab 結(jié)尾的所有串 b 包含偶數(shù)個(gè) b 但不含 a 的所有串 c 包含偶數(shù)個(gè) b 且含任意數(shù)目 a 的所有串 d 只包含一個(gè) a 的所有串 e 包含 ab 子串的所有串 f 不包含 ab 子串的所有串 答案 注意 正規(guī)式不唯一 a a b ab b bb c a ba ba d b ab e a b ab a b f b a 問題 2 請(qǐng)描述下面正規(guī)式定義的串 字母表 0 1 a 0 10 0 b 0 1 00 11 0 1 c 1 0 1 0 答案 a 每個(gè) 1 至少有一個(gè) 0 跟在后邊的串 b 所有含兩個(gè)相繼的 0 或兩個(gè)相繼的 1 的串 c 必須以 1 開頭和 0 結(jié)尾的串 問題 3 構(gòu)造有窮自動(dòng)機(jī) a 構(gòu)造一個(gè) DFA 接受字母表 0 1 上的以 01 結(jié)尾的所有串 b 構(gòu)造一個(gè) DFA 接受字母表 0 1 上的不包含 01 子串的所有串 c 構(gòu)造一個(gè) NFA 接受字母表 x y 上的正規(guī)式 x x y x 描述的集合 編譯原理 課后習(xí)題答案第四章 盛威網(wǎng) 專業(yè)的計(jì)算機(jī)學(xué)習(xí)網(wǎng)站 19 d 構(gòu)造一個(gè) NFA 接受字母表 a b 上的正規(guī)式 ab a b 描述的集合并將其轉(zhuǎn)換為 等價(jià)的 DFA 以及最小狀態(tài) DFA 答案 b c 編譯原理 課后習(xí)題答案第四章 盛威網(wǎng) 專業(yè)的計(jì)算機(jī)學(xué)習(xí)網(wǎng)站 20 最小化的 DFA 問題 4 設(shè)有如圖所示狀態(tài)轉(zhuǎn)換圖 求其對(duì)應(yīng)的正規(guī)表達(dá)式 可通過消結(jié)法得出正規(guī)式 R 01 00 1 0 1 0 也可通過轉(zhuǎn)換為正則文法 解方程得到正規(guī)式 問題 5 編譯原理 課后習(xí)題答案第四章 盛威網(wǎng) 專業(yè)的計(jì)算機(jī)學(xué)習(xí)網(wǎng)站 21 已知正規(guī)式 1 a b aa b 2 a b b 試用有限自動(dòng)機(jī)的等價(jià)性證明正規(guī)式 1 和 2 是等價(jià)的 并給出相應(yīng)的正規(guī)文法 分析 基本思路是對(duì)兩個(gè)正規(guī)式 分別經(jīng)過確定化 最小化 化簡為兩個(gè)最小 DFA 如這兩 個(gè)最小 DFA 一樣 也就證明了這兩個(gè)正規(guī)式是等價(jià)的 答案 狀態(tài)轉(zhuǎn)換表 1 a b X124 1234 124Y 1234 1234 124Y 124Y 1234 124Y 狀態(tài)轉(zhuǎn)換表 2 a B 1 2 3 2 2 3 3 2 3 由于 2 與 3 完全一樣 將兩者合并 即見下表 a b 1 2 3 編譯原理 課后習(xí)題答案第四章 盛威網(wǎng) 專業(yè)的計(jì)算機(jī)學(xué)習(xí)網(wǎng)站 22 2 3 而對(duì)正規(guī)式 2 可畫 NFA 圖 如圖所示 a b X12 12 12Y 12 12 12Y 12Y 12 12Y 可化簡得下表 a b 1 2 3 2 2 3 得 DFA圖 兩圖完全一樣 故兩個(gè)自動(dòng)機(jī)完全一樣 所以兩個(gè)正規(guī)文法等價(jià) 對(duì)相應(yīng)正規(guī)文法 令 A 對(duì)應(yīng) 1 B 對(duì)應(yīng) 2 故為 A aA bB b B aA bB b 即為 S aS bS B 此即為所求正規(guī)文 法 問題 6 考慮正規(guī)表達(dá)式 r a b a b 構(gòu)造可以生成語言 L r 的一個(gè)正規(guī)文法 答案 編譯原理 課后習(xí)題答案第四章 盛威網(wǎng) 專業(yè)的計(jì)算機(jī)學(xué)習(xí)網(wǎng)站 23 S a b a b 變換為 S aA S b a b A aA A b a b 變換為 S aA S bB B a b A aA A bC C a b 變換為 S aA S bB B a B b A aA A bC C a C b 所以 一個(gè)可能的正規(guī)文法為 G S S aA S bB B a B b A aA A bC C a C b 或表示為 S aA bB B a b A aA bC C a b 適當(dāng)?shù)葍r(jià)變換也可以 但要作說明 即要有步驟 問題 7 考慮下圖所示的 NFA N 構(gòu)造可以生成語言 L N 的一個(gè)正規(guī)文法 答案 G P P 0 P 1 P 1 Q Q 0 R 1 R R 問題 8 考慮如下文法 G S S 0S 1S 1A A 0B 1B B a 試構(gòu)造語言為 L G 的一個(gè)正規(guī)表達(dá)式 b 試構(gòu)造語言為 L G 的一個(gè)有限自動(dòng)機(jī) 編譯原理 課后習(xí)題答案第四章 盛威網(wǎng) 專業(yè)的計(jì)算機(jī)學(xué)習(xí)網(wǎng)站 24 答案 a 由 A 0B B 得 A 0 由 A 1B B 得 A 1 由 A 0 A 1 得 A 0 1 由 S 1A A 0 1 得 S 1 0 1 由 S 1A A 0 1 得 S 1 0 1 由 S 0S S 1 0 1 得 S 0 1 0 1 由 S 1S S 1 0 1 得 S 1 1 0 1 由 S 0 1 0 1 S 1 1 0 1 得 S 0 1 0 1 1 1 0 1 所以 一個(gè)可能的正規(guī)表達(dá)式為 0 1 0 1 1 1 0 1 b 編譯原理 課后習(xí)題答案第五章 盛威網(wǎng) 專業(yè)的計(jì)算機(jī)學(xué)習(xí)網(wǎng)站 1 第 5 章 自頂向下語法分析方法 第 1 題 對(duì)文法 G S S a T T T S S 1 給出 a a a 和 a a a a 的 左推導(dǎo) 2 對(duì)文法 G 進(jìn)行改寫 然后對(duì)每個(gè)非終結(jié)符寫出不帶回溯的遞歸子程序 3 經(jīng)改寫后的文法是否是 LL 1 的 給出它的預(yù)測分析表 4 給出輸入串 a a 的分析過程 并說明該串是否為 G 的句子 答案 1 對(duì) a a a 的 左推導(dǎo)為 S T T S S S a S a T a T S a S S a a S a a a 對(duì) a a a a 的 左推導(dǎo)為 S T T S S S T S T S S T S S S S S S S T S S S T S S S S S S S S S a S S S S a a S S S a a S S a a T S a a S S 編譯原理 課后習(xí)題答案第五章 盛威網(wǎng) 專業(yè)的計(jì)算機(jī)學(xué)習(xí)網(wǎng)站 2 a a a S a a a a 2 改寫文法為 0 S a 1 S 2 S T 3 T S N 4 N S N 5 N 非終結(jié)符 FIRST 集 FOLLOW 集 S a T a N 對(duì)左部為 N 的產(chǎn)生式可知 FIRST S N FIRST FOLLOW N 由于 SELECT N S N SELECT N 所以文法是 LL 1 的 預(yù)測分析表 Predicting Analysis Table a S a T T S N S N S N N S N 也可由預(yù)測分析表中無多重入口判定文法是 LL 1 的 3 對(duì)輸入串 a a 的分析過程為 編譯原理 課后習(xí)題答案第五章 盛威網(wǎng) 專業(yè)的計(jì)算機(jī)學(xué)習(xí)網(wǎng)站 3 棧 STACK 當(dāng)前輸入符 CUR CHAR 剩余輸入符 INOUT STRING 所用產(chǎn)生式 OPERATION S T T NS Na N NS NS Na N a a a a a a a a a a a a a a S T T SN S a N SN S a N 可見輸入串 a a 是文法的句子 編譯原理 課后習(xí)題答案第五章 盛威網(wǎng) 專業(yè)的計(jì)算機(jī)學(xué)習(xí)網(wǎng)站 4 第 3 題 已知文法 G S S MH a H LSo K dML L eHf M K bLM 判斷 G 是否是 LL 1 文法 如果是 構(gòu)造 LL 1 分析表 答案 文法展開為 0 S M H 1 S a 2 H L S o 3 H 4 K d M L 5 K 6 L e H f 7 M K 8 M b L M 非終結(jié)符 FIRST 集 FOLLOW 集 S a d b e o M d b e o H e f o L e a d b e o K d e o 對(duì)相同左部的產(chǎn)生式可知 SELECT S M H SELECT S a d b e o a SELECT H L S o SELECT H e f o SELECT K d M L SELECT K d e o SELECT M K SELECT M b L M d e o b 所以文法是 LL 1 的 預(yù)測分析表 a o d e f b S a MH MH MH MH MH 編譯原理 課后習(xí)題答案第五章 盛威網(wǎng) 專業(yè)的計(jì)算機(jī)學(xué)習(xí)網(wǎng)站 5 M K K K bLM K H LSo L eHf K dML 由預(yù)測分析表中無多重入口也可判定文法是 LL 1 的 編譯原理 課后習(xí)題答案第五章 盛威網(wǎng) 專業(yè)的計(jì)算機(jī)學(xué)習(xí)網(wǎng)站 6 第 7 題 對(duì)于一個(gè)文法若消除了左遞歸 提取了左公共因子后是否一定為 LL 1 文法 試對(duì)下面 文法進(jìn)行改寫 并對(duì)改寫后的文法進(jìn)行判斷 A baB B Abb a 2 A aABe a B Bb d 3 S Aa b A SB B ab 答案 先改寫 文法為 0 A baB 1 A 2 B baBbb 3 B bb 4 B a 再改寫文法為 0 A baB 1 A 2 B bN 3 B a 4 N aBbb 5 N b FIRST FOLLOW A b B b a b N b a b 預(yù)測分析表 a b A baB B a bN N aBbb b 由預(yù)測分析表中無多重入口判定文法是 LL 1 的 2 文法 編譯原理 課后習(xí)題答案第五章 盛威網(wǎng) 專業(yè)的計(jì)算機(jī)學(xué)習(xí)網(wǎng)站 7 A aABe a B Bb d 提取左公共因子和消除左遞歸后文法變?yōu)?0 A a N 1 N A B e 2 N 3 B d N1 4 N1 b N1 5 N1 非終結(jié)符 FIRST 集 FOLLOW 集 A a d B d e N a d N1 b e 對(duì)相同左部的產(chǎn)生式可知 SELECT N A B e SELECT N a d SELECT N1 b N1 SELECT N1 b e 所以文法是 LL 1 的 預(yù)測分析表 Predicting Analysis Table a e b d A a N B d N1 N1 b N1 N ABe 也可由預(yù)測分析表中無多重入口判定文法是 LL 1 的 3 文法 S Aa b A SB B ab 第 1 種改寫 用 A 的產(chǎn)生式右部代替 S 的產(chǎn)生式右部的 A 得 S SBa b B ab 消除左遞歸后文法變?yōu)?0 S b N 1 N B a N 2 N 編譯原理 課后習(xí)題答案第五章 盛威網(wǎng) 專業(yè)的計(jì)算機(jī)學(xué)習(xí)網(wǎng)站 8 3 B a b 非終結(jié)符 FIRST 集 FOLLOW 集 S b B a a N a 對(duì)相同左部的產(chǎn)生式可知 SELECT N B a N SELECT N a 所以文法是 LL 1 的 預(yù)測分析表 Predicting Analysis Table a b S b N B a b N B a N 也可由預(yù)測分析表中無多重入口判定文法是 LL 1 的 第 2 種改寫 用 S 的產(chǎn)生式右部代替 A 的產(chǎn)生式右部的 S 得 S Aa b A AaB bB B ab 消除左遞歸后文法變?yōu)?0 S A a 1 S b 2 A b B N 3 N a B N 4 N 5 B a b 非終結(jié)符 FIRST 集 FOLLOW 集 S b A b a B a a N a a 對(duì)相同左部的產(chǎn)生式可知 SELECT S A a SELECT S b b b b SELECT N a B N SELECT N a a a 所以文法不是 LL 1 的 預(yù)測分析表 a b 編譯原理 課后習(xí)題答案第五章 盛威網(wǎng) 專業(yè)的計(jì)算機(jī)學(xué)習(xí)網(wǎng)站 9 S A a b A b B N B a b N a B N 也可由預(yù)測分析表中含有多重入口判定文法不是 LL 1 的 編譯原理 課后習(xí)題答案第五章 盛威網(wǎng) 專業(yè)的計(jì)算機(jī)學(xué)習(xí)網(wǎng)站 10 附加題 問題 1 已知文法 G A 如下 試用類 C 或類 PASCAL 語言寫出其遞歸下降子程序 主程序不 需寫 G A A B B X A X a b a b 答案 不妨約定 在進(jìn)入一個(gè)非終結(jié)符號(hào)相應(yīng)的子程序前 已讀到一個(gè)單詞 word 存放當(dāng)前讀 到的單詞 Getsym 為一子程序 每調(diào)用一次 完成讀取一單詞的工作