編譯原理_第1~5章習(xí)題課答案PPT課件.ppt

chapter1 1 何謂源程序 目標(biāo)程序 翻譯程序 編譯程序和解釋程序 它們之間可能有何種關(guān)系 源程序 用源語(yǔ)言編寫(xiě)的程序 目標(biāo)程序 源程序經(jīng)翻譯程序過(guò)加工處理后生成的程序 翻譯程序 將源程序轉(zhuǎn)換為與其邏輯上等價(jià)的目標(biāo)程序 編譯程序 源語(yǔ)言為高級(jí)語(yǔ)言 目標(biāo)語(yǔ)言為匯編語(yǔ)言或機(jī)器語(yǔ)言的翻譯程序 解釋程序 源語(yǔ)言程序作為輸入 但不產(chǎn)生目標(biāo)程序 而是邊解釋邊執(zhí)行源程序本身 先翻譯后執(zhí)行 邊解釋邊執(zhí)行 執(zhí)行速度快 有利于程序的調(diào)試 多次運(yùn)算 1次運(yùn)算 2 一個(gè)典型的編譯系統(tǒng)通常由有哪些部分組成 各部分的主要功能是什么 chapter1 編譯系統(tǒng) 編譯程序 語(yǔ)法分析 語(yǔ)義分析與中間代碼生成 優(yōu)化 目標(biāo)代碼生成 運(yùn)行系統(tǒng) 詞法分析 語(yǔ)法分析 SyntaxAnalysis 在詞法分析的基礎(chǔ)上將單詞序列分解成各類語(yǔ)法短語(yǔ) 如 程序 語(yǔ)句 表達(dá)式 等等 語(yǔ)義分析 SyntacticAnalysis 語(yǔ)義分析是在語(yǔ)法分析程序確定出語(yǔ)法短語(yǔ)后 審查有無(wú)語(yǔ)義錯(cuò)誤 并為代碼生成階段收集類型信息 chapter1 詞法分析 LexicalAnalysis 從左到右一個(gè)字符一個(gè)字符的讀入源程序 對(duì)構(gòu)成源程序的字符串進(jìn)行掃描和分解 從而識(shí)別出一個(gè)個(gè)單詞 也稱單詞符號(hào)或簡(jiǎn)稱符號(hào) chapter1 代碼優(yōu)化 Optimizationofcode 為了使生成的目標(biāo)代碼更為高效 可以對(duì)產(chǎn)生的中間代碼進(jìn)行變換或進(jìn)行改造 這就是代碼的優(yōu)化 代碼生成 Generationofcode 目標(biāo)代碼生成是編譯器的最后一個(gè)階段 在生成目標(biāo)代碼時(shí)要考慮以下幾個(gè)問(wèn)題 計(jì)算機(jī)的系統(tǒng)結(jié)構(gòu) 指令系統(tǒng) 寄存器的分配以及內(nèi)存的組織等 中間代碼生成 Generationofintermediatecode 完成語(yǔ)法分析和語(yǔ)義處理工作后 編譯程序?qū)⒃闯绦蜃兂梢环N內(nèi)部表示形式 這種內(nèi)部表示形式叫做中間語(yǔ)言或稱中間代碼 它是一種結(jié)構(gòu)簡(jiǎn)單 含義明確的記號(hào)系統(tǒng) chapter2 1 寫(xiě)出C語(yǔ)言和Java語(yǔ)言的輸入字母表 C語(yǔ)言 0 9數(shù)字 大小寫(xiě)英文字母 鍵盤(pán)上可見(jiàn)的字符 Java語(yǔ)言 Unicode可以包括的所有字符 6 文法G6為 N D NDD 0 1 2 3 4 5 6 7 8 9 1 G6的語(yǔ)言是什么 G6的語(yǔ)言是 0 9的數(shù)字組成的任意非空串 L G6 x x 0 1 2 3 4 5 6 7 8 9 2 給出句子0127 34和568的最左和最右推導(dǎo) 7 寫(xiě)一文法 使其語(yǔ)言是奇數(shù)集 要求 不以0打頭 復(fù)雜的情況 分三部分 末尾 以1 3 5 7 9結(jié)尾 一位 D 1 3 5 7 9 開(kāi)頭 除了0的任意數(shù)字 中間部分 空或者任意數(shù)字串 D 1 3 5 7 9 C CA A 0 B 所以題目要求的文法G N 可以寫(xiě)成 B 2 4 6 8 D 9 證明文法 S iSeS iS i是二義的 二義性的含義 如果文法存在某個(gè)句子對(duì)應(yīng)兩棵以上不同的語(yǔ)法樹(shù) 或者兩種以上不同的最左 右推導(dǎo) 則稱這個(gè)文法是二義的 首先 找到此文法對(duì)應(yīng)的一個(gè)句子iiiei 其次 構(gòu)造與之對(duì)應(yīng)的兩棵語(yǔ)法樹(shù) 結(jié)論 因?yàn)樵撐姆ù嬖诰渥觟iiei對(duì)應(yīng)兩棵不同的語(yǔ)法樹(shù) 因而該文法是二義的 11 給出下面語(yǔ)言的相應(yīng)文法 L1 anbnci n 1 i 0 G1 S S ABA aAb abB cB 從n i的不同取值來(lái)把L1分成兩部分 A aAb ab 前半部分是anbn 后半部分是ci B Bc 所以整個(gè)文法G1 S 可以寫(xiě)為 L2 aibncn n 1 i 0 G2 S S ABA aA B bBc bc L3 anbnambm m n 0 G3 S S ABA aAb B aBb L4 1n0m1m0n n m 0 可以看成是兩部分 剩下兩邊的部分就是 S 1S0 中間部分是0m1m A 0A1 所以G4 S 可以寫(xiě)為 S 1S0 AA 0A1 A chapter3 7 構(gòu)造下列正規(guī)式相應(yīng)的DFA 步驟 根據(jù)正規(guī)式畫(huà)出對(duì)應(yīng)的狀態(tài)轉(zhuǎn)換圖 根據(jù)狀態(tài)轉(zhuǎn)換圖畫(huà)出對(duì)應(yīng)的狀態(tài)轉(zhuǎn)換矩陣 根據(jù)狀態(tài)轉(zhuǎn)換矩陣得到重命名后的狀態(tài)轉(zhuǎn)換矩陣 根據(jù)重命名后的狀態(tài)轉(zhuǎn)換矩陣得出最后的DFA 問(wèn)題 將狀態(tài)轉(zhuǎn)換圖與DFA混淆 1 0 1 101 狀態(tài)轉(zhuǎn)換圖 a b a d b 1 0 1 101 a 1 0 1 101 d c e f 1 0 1 1 0 1 狀態(tài)轉(zhuǎn)換矩陣 I I0 I1 a b c d b c d c d c d e c d c d c d e c d e c d f c d e c d f c d c d e g c d e g c d f c d e 重命名后的狀態(tài)轉(zhuǎn)換矩陣 S 0 1 A 始態(tài) B B C D C C D D E D E C F 終態(tài) F 終態(tài) E D A B 1 0 C 1 D 0 1 0 E 1 0 1 0 1 DFA 1 1010 1 010 1 0 a b d c 1 0 0 1 0 1 f g h i 0 1 1 1 0 j k l m n 狀態(tài)轉(zhuǎn)換圖 狀態(tài)轉(zhuǎn)換矩陣 重命名后的狀態(tài)轉(zhuǎn)換矩陣 DFA 8 給出下面正規(guī)表達(dá)式 1 以01結(jié)尾的二進(jìn)制數(shù)串 0 1 01 2 能被5整除的十進(jìn)制數(shù) 0 5 0 5 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 4 英文字母組成的所有符號(hào)串 要求符號(hào)串中的字母按字典序排列 A a B b C c Z z 3 包含奇數(shù)個(gè)1或奇數(shù)個(gè)0的二進(jìn)制串 0 1 0 10 1 1 0 0 10 1 5 沒(méi)有重複出現(xiàn)的數(shù)字的數(shù)字符號(hào)串的全體 令ri i i 0 1 2 9R0 R1 R2 R9記為 Rii 0 1 2 9 P 0 1 2 9 表示0 1 2 9的全排列 ri0ri1 ri9ri0ri1 ri9 P 0 1 2 9 8 給出下面正規(guī)表達(dá)式 6 最多有一個(gè)重複出現(xiàn)的數(shù)字的數(shù)字符號(hào)串的全體 i ri0ri1 ri9i 0 1 2 9 ri0ri1 ri9 P 0 1 2 9 7 不包含字串a(chǎn)bb的由a和b組成的符號(hào)串的全體 b a ba 9 對(duì)下面情況給出DFA及正規(guī)表達(dá)式 1 0 1 上的含有子串010的所有串 正規(guī)式 0 1 010 0 1 DFA做法同第7題 2 0 1 上不含子串010的所有串 正規(guī)式 1 0 11 1 1 0 1 0 11 0 1 1 0 11 1 12 將圖3 18的 a 和 b 分別確定化和最少化 a 狀態(tài)轉(zhuǎn)換矩陣 0 0 1 1 1 0 1 0 1 1 0 重命名后的狀態(tài)轉(zhuǎn)換矩陣 0 1 2 2 1 1 2 0 a 2 b a b a DFA 最小化 0 0 1 2 0 1 a 1 0 1 b 2 因此 不能再分 2 b a a b 這道題實(shí)質(zhì)上已經(jīng)是確定化了的 所以我們只需最小化 2 3 4 5 0 1 2 3 4 5 a 0 1 3 5 分屬兩區(qū) 所以分為 2 4 3 5 0 1 a 1 0 1 b 2 4 所以0 1等價(jià) 2 4 a 0 1 2 4 b 3 5 所以2 4等價(jià) 3 5 a 3 5 3 5 b 2 4 所以3 5等價(jià) 所以分為 0 1 2 4 3 5 14 構(gòu)造一個(gè)DFA 它接受 0 1 上所有滿足如下條件的字符串 每個(gè)1都有0直接跟在右邊 思路 先寫(xiě)出滿足條件的正規(guī)式 由正規(guī)式構(gòu)造NFA 再把NFA確定化和最小化 滿足條件的正規(guī)式 0 10 確定化 給狀態(tài)編號(hào) 最小化 0 1 2 0 1 0 1 0 1 1 2 2 0 0 2 1 2 或 0 1 所以 0 1 不可分 用狀態(tài)0代表它們 15 給定右線性文法G 求一個(gè)與G等價(jià)的左線性文法 S 0S 1S 1A 0BA 1C 1B 0C 0C 0C 1C 0 1 G Z Z Z0 Z1 B0 A1B A0 0A B1 1 確定化 最小化后的DFA為 補(bǔ)充 構(gòu)造一右線性文法 使它與如下文法等價(jià) S ABA UTU a aUT b bTB c cB并根據(jù)所得右線性文法 構(gòu)造出相應(yīng)的狀態(tài)轉(zhuǎn)換圖 思路 先寫(xiě)出原文法所描述的語(yǔ)言L G ambnck m n k 1 G S S aS aBB bB bCC cC c chapter4 4 1 考慮下面文法G1 S a T T T S S 1 消去G1的左遞歸 S a T T ST T ST 2 經(jīng)改寫(xiě)后的文法是否是LL 1 文法 給出預(yù)測(cè)分析表 經(jīng)改寫(xiě)后的文法滿足3個(gè)條件 所以是LL 1 的 預(yù)測(cè)分析表構(gòu)造算法 1 對(duì)文法中的每個(gè)產(chǎn)生式A 執(zhí)行第二步和第三步 FIRST S a FIRST T a FIRST T FOLLOW S FOLLOW T FOLLOW T S a S S T T ST T ST T ST T ST T 預(yù)測(cè)分析表構(gòu)造算法 1 對(duì)文法中的每個(gè)產(chǎn)生式A 執(zhí)行第二步和第三步 2 對(duì)每個(gè)終結(jié)符a FIRST 把A a加到M A a 中 S a S S T T ST T ST T S a S S T T ST T ST T ST T ST 3 若 FIRST 則對(duì)于任何b FOLLOW A 把A 加至M A b 中 FOLLOW T FOLLOW T T 遞歸子程序 procedureS beginifsym a orsym thenabvanceelseifsym thenbeginadvance T ifsym thenadvance elseerror endelseerrorend procedureT beginS T EndprocedureT beginifsym thenbenginadvance S T endEnd sym 是輸入串指針I(yè)P所指的符號(hào)advance 是把IP調(diào)至下一個(gè)輸入符號(hào)error 是出錯(cuò)診察程序 補(bǔ)充題 有文法 E TE E ATE T FT T MFT F E iA M 1 求First Follow集 判斷是否是LL 1 文法 2 若是構(gòu)造LL 1 分析表 3 簡(jiǎn)述LL 1 分析器的工作原理 4 2 有文法 E TE E E T FT T T F PF F F P E a b 1 求First Follow集 判斷是否是LL 1 文法 2 若是構(gòu)造LL 1 分析表 3 簡(jiǎn)述LL 1 分析器的工作原理 E TE E ATE T FT T MFT F E iA M FIRST M FIRST A FIRST F i FIRST T FIRST T i FIRST E FIRST E i FOLLOW E FOLLOW E FOLLOW T FOLLOW T FOLLOW F FOLLOW A i FOLLOW M i P81 2 對(duì)文法G E TE E E T FT T T F PF F F P E a b 1 FIRST E FIRST T FIRST F FIRST P a b FIRST E FIRST T FIRST T a b FIRST F FOLLOW E FOLLOW E FOLLOW E FOLLOW T FIRST E FOLLOW E FOLLOW T FOLLOW T FOLLOW F FIRST T FOLLOW T a b FOLLOW F FOLLOW F a b FOLLOW P FIRST F FOLLOW F a b 2 考慮下列產(chǎn)生式 FIRST E FIRST FIRST E FOLLOW E FIRST T FIRST a b FIRST T FOLLOW T a b FIRST F FIRST FIRST F FOLLOW F a b FIRST E FIRST a FIRST b FIRST 所以 該文法式LL 1 文法 3 預(yù)測(cè)分析表 4 程序procedureE beginifsym orsym a orsym b orsym thenbeginT E endelseerrorendprocedureE beginifsym thenbeginadvance Eendelseifsym andsym thenerrorendprocedureT beginifsym orsym a orsym b orsym thenbeginF T endelseerrorend procedureT beginifsym orsym a orsym b orsym thenTelseifsym thenerrorendprocedureF beginifsym orsym a orsym b orsym thenbeginP F endelseerrorendprocedureF beginifsym thenbeginadvance F endend procedureP beginifsym a orsym b orsym thenadvanceelseifsym thenbeginadvance E ifsym thenadvanceelseerrorendelseerrorend 4 3下面文法中 那些是LL 1 文法的 說(shuō)明理由構(gòu)造不帶回溯的自上而下分析的文法條件1 文法不含左遞歸 2 對(duì)于文法中每一個(gè)非終結(jié)符A的各個(gè)產(chǎn)生式的候選首符集兩兩不相交 即 若A 1 2 n則FIRST i FIRST j i j 3 對(duì)文法中的每個(gè)非終結(jié)符A 若它存在某個(gè)候選首符集包含 則FIRST A FOLLOW A 如果一個(gè)文法G滿足以上條件 則稱該文法G為L(zhǎng)L 1 文法 4 3 1S AbcA a B b 是 滿足三個(gè)條件 4 3 2S AbA a B B b 對(duì)于A不滿足條件3 4 3 3S ABBAA a B b A B都不滿足條件3 4 3 4S aSe BB bBe C cCe d滿足條件3 解題思路 構(gòu)造文法的預(yù)測(cè)分析表 通常應(yīng)當(dāng)按下列步驟進(jìn)行 1 消除文法的左遞歸 包括所有直接左遞歸和間接左遞歸 2 對(duì)消除左遞歸后的文法 提取公因子3 對(duì)經(jīng)過(guò)上述改造后的文法 計(jì)算它的每個(gè)非終結(jié)符的FIRST集合和FOLLOW集合 4 根據(jù)FIRST集合和FOLLOW集合構(gòu)造預(yù)測(cè)分析表 第1步對(duì)文法G的每個(gè)產(chǎn)生式A 執(zhí)行第1步和第3步 第2步對(duì)每個(gè)終結(jié)符a FIRST 把A 加至M A a 中 第3步若 FIRST 則對(duì)任何b FIRST A 把A 加至M A b 中 第4步把所有無(wú)定義的M A a 標(biāo)上 出錯(cuò)標(biāo)誌 4 4對(duì)下面的文法 Expr ExprExpr Expr VarExprTailExprTail Expr Var idVarTailVarTail Expr 1 構(gòu)造LL 1 分析表 2 給出對(duì)句子id id id 分析過(guò)程 4 4對(duì)下面的文法 Expr ExprExpr Expr VarExprTailExprTail Expr Var idVarTailVarTail Expr 1 構(gòu)造LL 1 分析表 2 給出對(duì)句子id id id 分析過(guò)程 4 4對(duì)下面的文法 Expr ExprExpr Expr VarExprTailExprTail Expr Var idVarTailVarTail Expr 1 構(gòu)造LL 1 分析表 2 給出對(duì)句子id id id 分析過(guò)程 2 給出對(duì)句子id id id 分析過(guò)程 2 給出對(duì)句子id id id 分析過(guò)程 2 給出對(duì)句子id id id 分析過(guò)程 2 給出對(duì)句子id id id 分析過(guò)程 chapter5 1 令文法G1為 E E T TT T F FF E i證明E T F是它的一個(gè)句型 指出這個(gè)句型的所有短語(yǔ) 直接短語(yǔ)和句柄 T F是句型E T F相對(duì)于T的短語(yǔ) E T F句型E T F相對(duì)于E的短語(yǔ) T F是句型E T F相對(duì)于T的直接短語(yǔ) T F是句柄 2 考慮下面的表格結(jié)構(gòu)文法G2 S a T T T S S 1 給出 a a a 和 a a a a 的最左和最右推導(dǎo) 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 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 S S S S S S a S S S S a a S S S a a S S a a a S a a a a a a a a 的最右推導(dǎo) S T T S S S S a T a T S S S S 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 a S a a a a a a a 的最右推導(dǎo) S T T S T T T T S T T a T S a T a a S a a a a a 2 指出 a a a a 的規(guī)范歸約及每一步的句柄 S T T S a T S T S T S T S a T S T S a S a a S a S a a a S T S T a a a a S a T S a a T S T T S T a a T S T S a a S T S T a a S T S a a T S T T S 根據(jù)這個(gè)規(guī)范規(guī)約 給出 移進(jìn) 歸約 的過(guò)程 并給出它的語(yǔ)法樹(shù)的自下而上的構(gòu)造過(guò)程 符號(hào)棧 輸入串 a a a a S T T S a T S T S T S T S a T S T S a S a a S T a S S T S T a S T S S T a S T S 3 1 計(jì)算練習(xí)2文法G2的FIRSTVT和LASTVT G2 S a T T T S S FIRSTVT S a FIRSTVT T a LASTVT S a LASTVT T a T T S T T S S T S T 對(duì)待特殊地 把它看作句型的開(kāi)始和結(jié)束符 根據(jù) S 同理可得 1 文法是算術(shù)文法 且不含 產(chǎn)生式 2 由優(yōu)先關(guān)系矩陣可知 任何兩個(gè)終結(jié)符之間的優(yōu)先關(guān)系不多于一種 綜上 該文法是算術(shù)優(yōu)先文法 輸入串 a a a 的算符優(yōu)先過(guò)程 a