貴州大學(xué)【習(xí)題答案】第03章 詞法分析.pdf

編譯原理 課后練習(xí)參考答案 第 03 章 詞法分析 共 4 頁(yè) 第 1 頁(yè) 課后練習(xí)參考答案課后練習(xí)參考答案 第第 03 章章 詞法分析詞法分析 1 寫出正規(guī)式寫出正規(guī)式 a a b a b a b 相應(yīng)的正規(guī)文法 相應(yīng)的正規(guī)文法 解 引入開始符號(hào) S 構(gòu)造 S a a b a b a b a a b a b a b a a b a a b a a b b a b a a b a a b b a b aA aC 引入非終結(jié)符 A B C A a b a b a b a b a b A C a b a a b b a b a b a a b b a b a b a b a a b b a b a b a b a a b b a b a a b b a b a b a b a a b b a b a a b b a b a b a b a a b b a b B B aC bC B a b a b aA bA 得到正規(guī)文法 G S S aA aC A aA bA C aC bC B B B aA bA 2 給定正規(guī)式 給定正規(guī)式 0 0 1 1 1 寫出相應(yīng)的正規(guī)文法 寫出相應(yīng)的正規(guī)文法 2 畫出相應(yīng)的狀態(tài)轉(zhuǎn)移圖 畫出相應(yīng)的狀態(tài)轉(zhuǎn)移圖 解 1 引入非終結(jié)符 S A S 0 0 1 1 0A A 0 1 1 0 1 1 1 0 1 1 1 0 1 0 1 1 1 0A 1A 得到正規(guī)文法 G S S 0A A 0A 1A 1 2 第一問中給出的 G S 是一個(gè)右線性文法 按照由右線性正規(guī)文法構(gòu)造狀態(tài)轉(zhuǎn)換圖的方法構(gòu)造相應(yīng)的狀態(tài)轉(zhuǎn)移圖如下 S A 0 Z 1 0 1 編譯原理 課后練習(xí)參考答案 第 03 章 詞法分析 共 4 頁(yè) 第 2 頁(yè) 3 給定文法給定文法 G Z S 0U 1V U 1S 1 V 0S 0 1 請(qǐng)構(gòu)造該文法的狀態(tài)轉(zhuǎn)換圖請(qǐng)構(gòu)造該文法的狀態(tài)轉(zhuǎn)換圖 2 利用所得的狀態(tài)轉(zhuǎn)換圖判別符號(hào)串利用所得的狀態(tài)轉(zhuǎn)換圖判別符號(hào)串 100101 和和 100111 是否該文法的句子 是否該文法的句子 解 1 增加一個(gè)終態(tài) Z 得到該文法對(duì)應(yīng)的狀態(tài)轉(zhuǎn)換圖如下 S U 0 V 1 0 0 1 1 Z 2 對(duì)符號(hào)串 100101 的識(shí)別過程經(jīng)歷了狀態(tài) S V S U S U Z 終止于終止?fàn)顟B(tài) Z 所 以 100101 是此文法的句子 對(duì)符號(hào)串 100111 的識(shí)別過程經(jīng)歷了狀態(tài) S V S U S V 識(shí)別出 10011 后 在狀態(tài) V 無(wú)法進(jìn)一步識(shí)別 所以 100111 不是此文法的句子 4 給出描述包含奇數(shù)個(gè)給出描述包含奇數(shù)個(gè) 1 或奇數(shù)個(gè)或奇數(shù)個(gè) 0 的二進(jìn)制數(shù)串的正規(guī)表達(dá)式 的二進(jìn)制數(shù)串的正規(guī)表達(dá)式 解 本題求二進(jìn)制串 并且要求包含奇數(shù)個(gè) 0 或奇數(shù)個(gè) 1 由于 0 和 1 都可以在二進(jìn)制串中任何 地方出現(xiàn) 所以本題只需要考慮包含奇數(shù)個(gè) 0 的字符串 另外一種情況可以類似求得 由于只關(guān)心 0 的個(gè)數(shù)的奇偶數(shù) 我們可以把二進(jìn)制串分成多段來(lái)考慮 第 1 段為二進(jìn)制串的開始到第 1 個(gè)0 為止 這一段包含 1 個(gè) 0 并且 0 的前面有 0 或多個(gè) 1 對(duì)于剩下的二進(jìn)制串按照每段包含兩個(gè) 0 的方式去劃分 即以 0 開始 以 0 結(jié)尾 中間 可以有 0 個(gè)或多個(gè) 1 如果一個(gè)二進(jìn)制串被這樣劃分完后 剩下的部分如果全部是全 1 串 這些全 1 串在前面劃分 的串之間或最后 則該二進(jìn)制串就具有奇數(shù)個(gè) 0 所以包含奇數(shù)個(gè) 0 的二進(jìn)制串可以這樣描述 以第 1 段 1 開始 后面由全 1 串 1 以及包含兩個(gè) 0 的串 01 0 組成 其正規(guī)表達(dá)式為 1 0 1 01 0 本題的解答則是 1 0 1 01 0 0 1 0 10 1 5 請(qǐng)給出接受 請(qǐng)給出接受 0 1 上不含子串 上不含子串 010 的所有串的正規(guī)表達(dá)式和的所有串的正規(guī)表達(dá)式和 DFA 解 本題有兩種解題思路 一種是直接構(gòu)造一個(gè)滿足條件的狀態(tài)轉(zhuǎn)換圖 然后根據(jù)狀態(tài)轉(zhuǎn)換 圖求正規(guī)表達(dá)式 另一種方法是分析題意直接寫出滿足條件的正規(guī)表達(dá)式 編譯原理 課后練習(xí)參考答案 第 03 章 詞法分析 共 4 頁(yè) 第 3 頁(yè) 方法方法 1 直接寫出滿足條件的狀態(tài)轉(zhuǎn)換圖 在狀態(tài)轉(zhuǎn)換圖中引入 3 個(gè)狀態(tài) 初始狀態(tài) S 也是終止?fàn)?態(tài) 表示當(dāng)前讀入的串中不包含子串 010 并且最后讀入的字符是 1 或沒讀入任何字符 初 始狀態(tài)讀入字符 0 后進(jìn)入一個(gè)新的狀態(tài) A 狀態(tài) A 表示當(dāng)前讀入的串中不包含子串 010 并 且最后讀入的字符是 0 狀態(tài) A 如果讀入字符 1 后進(jìn)入新狀態(tài) B 狀態(tài) B 表示當(dāng)前讀入的串 中不包含子串 010 并且最后讀入的字符是 01 狀態(tài) B 不接受字符 0 然后用 0 1 連接各狀 態(tài)就構(gòu)造出了滿足條件的狀態(tài)轉(zhuǎn)換圖 如下所示 然后根據(jù)狀態(tài)轉(zhuǎn)換圖來(lái)求正規(guī)表達(dá)式 這 里就不詳細(xì)說(shuō)明了 方法方法 2 直接寫出滿足條件的正規(guī)表達(dá)式 考慮滿足條件的字符串中的 1 在串的開始部分可以有 0 個(gè)或多個(gè) 1 串的尾部也可以有 0 個(gè)或多個(gè) 1 但串的之間只要出現(xiàn) 1 則至少在兩個(gè)以上 所以滿足條件的正規(guī)表達(dá)式為 1 0 111 1 解答 所求正規(guī)表達(dá)式為 1 0 111 1 所求 DFA 如上圖所示 6 一個(gè)人帶著狼 山羊和白菜在一條河的左岸 有一條船 大小正好能裝下這個(gè)人和其它一個(gè)人帶著狼 山羊和白菜在一條河的左岸 有一條船 大小正好能裝下這個(gè)人和其它 3 件東西中的一件 人和他的隨行物都要過到河的右岸 人每次只能將一件東西擺渡過河 但若人將狼和羊留在同一岸而無(wú)人照顧的話 狼將把羊吃掉 類似的 羊也可能會(huì)吃掉 白菜 請(qǐng)問是否有可能擺渡過河 并使得羊和白菜都不會(huì)被吃掉 如果可能 請(qǐng)用有限 自動(dòng)機(jī)寫出渡河的方法 件東西中的一件 人和他的隨行物都要過到河的右岸 人每次只能將一件東西擺渡過河 但若人將狼和羊留在同一岸而無(wú)人照顧的話 狼將把羊吃掉 類似的 羊也可能會(huì)吃掉 白菜 請(qǐng)問是否有可能擺渡過河 并使得羊和白菜都不會(huì)被吃掉 如果可能 請(qǐng)用有限 自動(dòng)機(jī)寫出渡河的方法 解 這是一道經(jīng)典的智力題 很顯然是有辦法渡河的 關(guān)鍵是如何用有限自動(dòng)機(jī)來(lái)求解渡河 的方法 有限自動(dòng)機(jī)描述的是狀態(tài)和狀態(tài)之間的轉(zhuǎn)換 對(duì)于本題 可以把人 狼 山羊和白 菜都在左岸作為有限自動(dòng)機(jī)的初始狀態(tài) 而把他們都在右岸作為終止?fàn)顟B(tài) 只要構(gòu)造一個(gè)自 動(dòng)機(jī)使得存在一條從初始狀態(tài)到終止?fàn)顟B(tài)的路徑就可以了 首先構(gòu)造有限自動(dòng)機(jī)的狀態(tài)集 可以用 M W G C 表示人 狼 山羊和白 菜都在左岸 用 M W G C 表示人 狼 山羊和白菜都在右岸 可能存在狀態(tài) 共有 1 初態(tài) 4 4 選 1 過河 4 3 4 選 2 過河 4 4 選 1 留左岸 1 終態(tài) 22 個(gè) 但其中 有些狀態(tài)是不安全的 如 G C M W 表示人和狼在右岸 山羊和白菜在左岸 山 羊會(huì)吃了白菜 去掉不安全的狀態(tài) 剩下的狀態(tài)就是要構(gòu)造的有限自動(dòng)狀態(tài)集 共 10 個(gè)狀態(tài) M W G C M W G C M W G C M W C G M G C W C M W G G M W C W M 編譯原理 課后練習(xí)參考答案 第 03 章 詞法分析 共 4 頁(yè) 第 4 頁(yè) G C M G W C W C M G 接下來(lái)為有限自動(dòng)機(jī)添加箭弧 用 M 表示人獨(dú)自過河 用 MW 表示人和狼一起過 河 用 MG 表示人和山羊一起過河 用 MC 表示人和白菜一起過河 在狀態(tài)之間只要 可以使用箭弧 則得到一個(gè)狀態(tài)轉(zhuǎn)換圖 如下圖所示 觀察所求得的有限自動(dòng)機(jī)的狀態(tài)轉(zhuǎn)換圖 可以發(fā)現(xiàn)從初始狀態(tài)到終止?fàn)顟B(tài)之間存在兩條 較短的路徑 它們分別為 MG M MW MG MC M MG 和 MG M MC MG MW M MG 這兩條路徑就是兩種正確的渡河方法 解答 分析題意 求得相應(yīng)有限自動(dòng)機(jī)的狀態(tài)轉(zhuǎn)換圖如下所示 從圖中直接可以得到兩種渡河 方法 MG M MW MG MC M MG 和 M