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

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