貴州大學【習題答案】第03章 詞法分析.pdf

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