簡(jiǎn)介這份資源是南京信息工程大學(xué)2021—2022學(xué)年第一學(xué)期編譯原理期末試卷B卷的完整文檔由凌妙根老師出卷含標(biāo)準(zhǔn)答案面向正在備考編譯原理的高校學(xué)生與需要梳理知識(shí)點(diǎn)的自學(xué)者。試卷覆蓋詞法分析、語(yǔ)法分析、錯(cuò)誤處理、非遞歸預(yù)測(cè)分析、語(yǔ)法制導(dǎo)翻譯、代碼優(yōu)化及自動(dòng)機(jī)理論等核心內(nèi)容題型包括選擇題、畫(huà)圖題、計(jì)算分析題與綜合題可幫助讀者檢驗(yàn)對(duì)編譯器設(shè)計(jì)各環(huán)節(jié)的掌握程度。資源包共1個(gè)docx文件約1.11MB內(nèi)容完整、排版清晰便于打印練習(xí)或?qū)φ諒?fù)習(xí)。目前已有1022人學(xué)習(xí)下載適合需要真題演練、查漏補(bǔ)缺的讀者使用。通過(guò)這份試卷讀者可熟悉南信大編譯原理的命題風(fēng)格與難度掌握最左推導(dǎo)、語(yǔ)法分析樹(shù)、DAG優(yōu)化、FIRST與FOLLOW集、預(yù)測(cè)分析表、SLR分析及NFA與DFA構(gòu)造等典型題型的解題思路是期末沖刺階段的高效復(fù)習(xí)材料。1. 一份能當(dāng)“錯(cuò)題本”用的編譯原理期末卷凌妙根 2021-2022 B 卷拆解如果你正在搜“南京信息工程大學(xué) 編譯原理 期末試卷 2021-2022 凌妙根”大概率不是想隨便看看而是手里缺一份能對(duì)著復(fù)盤(pán)、能摸清出題人套路的真題。這份 B 卷共 2 頁(yè)、考試時(shí)間 120 分鐘任課教師凌妙根出卷時(shí)間 2021 年 12 月覆蓋計(jì)算機(jī)與軟件學(xué)院。它最值錢的地方不在“有答案”而在于題型分布非常典型選擇 10 分、畫(huà)圖 25 分、計(jì)算分析 20 分、綜合 45 分把詞法分析、語(yǔ)法分析、錯(cuò)誤處理、語(yǔ)法制導(dǎo)翻譯、DAG 優(yōu)化、SLR 分析、NFA 到 DFA 確定化全串了一遍。適合正在期末沖刺的本科生也適合想用一套卷子快速定位自己編譯原理薄弱環(huán)節(jié)的人。下面我按“這卷子考什么 → 每類題怎么下手 → 哪里最容易翻車”的順序拆開(kāi)講。2. 選擇題與非遞歸預(yù)測(cè)分析10 分里藏著 4 個(gè)高頻判斷點(diǎn)2.1 從 5 道選擇看凌妙根的出題偏好這 5 道選擇題不是隨便湊的每一道都卡在編譯原理的“概念邊界”上。第 1 題問(wèn)“哪個(gè)不是編譯程序的組成部分”答案 C 設(shè)備管理程序——這是操作系統(tǒng)的東西混進(jìn)來(lái)考你分不分得清編譯器前端后端。第 2 題文法定義的語(yǔ)言答案 C考的是文法生成語(yǔ)言的形式化定義。第 3 題遇到錯(cuò)誤怎么辦答案 C“跳過(guò)錯(cuò)誤所在的語(yǔ)法單位繼續(xù)分析”這是典型的錯(cuò)誤恢復(fù)策略不是“立即停止”。第 4 題非遞歸預(yù)測(cè)分析中翻譯的說(shuō)法答案 D“綜合屬性在 A 出現(xiàn)之前就可以計(jì)算”——錯(cuò)綜合屬性必須等 A 歸約完才能算。第 5 題語(yǔ)法制導(dǎo)翻譯方案答案 A“只限自底向上”——錯(cuò)自頂向下也能用。把這 5 題連起來(lái)看出題人真正想篩的是你有沒(méi)有把“編譯器組件”“錯(cuò)誤恢復(fù)”“屬性計(jì)算時(shí)機(jī)”“SDD 與 SDT 的適用方向”這幾個(gè)概念真正分清。很多人背了 LR、LL 的流程卻在這些判斷上栽跟頭。2.2 非遞歸預(yù)測(cè)分析里屬性棧怎么擴(kuò)第 4 題背后是 LL(1) 非遞歸預(yù)測(cè)分析做翻譯的核心機(jī)制。普通預(yù)測(cè)分析只有狀態(tài)棧和輸入指針要做屬性翻譯就得擴(kuò)展語(yǔ)法分析棧把繼承屬性和綜合屬性分開(kāi)存放。常見(jiàn)做法是棧里每個(gè)記錄帶一個(gè)屬性槽非終結(jié)符 A 的繼承屬性在 A 展開(kāi)時(shí)由父產(chǎn)生式傳入綜合屬性在 A 歸約時(shí)回填。下面用 Python 模擬一個(gè)極簡(jiǎn)的擴(kuò)展棧記錄結(jié)構(gòu)幫你把“繼承屬性先算、綜合屬性后算”這個(gè)時(shí)機(jī)差異看明白class StackRecord: def __init__(self, symbol, inheritedNone): self.symbol symbol # 棧中符號(hào)終結(jié)符或非終結(jié)符 self.inherited inherited # 繼承屬性展開(kāi)時(shí)由父產(chǎn)生式傳入 self.synthesized None # 綜合屬性歸約完成時(shí)才回填 def expand_nonterminal(stack, A, prod, inherited_vals): # 用產(chǎn)生式右部替換棧頂 A繼承屬性在此刻分配 stack.pop() for sym in reversed(prod.right): rec StackRecord(sym) if sym in prod.inherited_map: rec.inherited inherited_vals[prod.inherited_map[sym]] stack.append(rec) def reduce_nonterminal(stack, A, semantic_rule): # 歸約時(shí)計(jì)算 A 的綜合屬性此時(shí)右部符號(hào)的綜合屬性已就緒 children [] while stack[-1].symbol ! A: children.append(stack.pop()) rec stack.pop() rec.synthesized semantic_rule(children[::-1]) stack.append(rec)邏輯說(shuō)明StackRecord把繼承屬性和綜合屬性放在同一條記錄的不同字段對(duì)應(yīng)試卷第 4 題 C 選項(xiàng)“存放在不同的紀(jì)錄中”的說(shuō)法。expand_nonterminal在展開(kāi)時(shí)給繼承屬性賦值reduce_nonterminal在歸約時(shí)才算綜合屬性。參數(shù)上inherited_vals是父產(chǎn)生式傳下來(lái)的屬性字典semantic_rule是產(chǎn)生式對(duì)應(yīng)的語(yǔ)義動(dòng)作。如果你把綜合屬性提前到展開(kāi)階段算就會(huì)踩中第 4 題 D 選項(xiàng)那個(gè)坑。提示考試?yán)镉龅健胺沁f歸預(yù)測(cè)分析 翻譯”的組合先問(wèn)自己一句——這個(gè)屬性是往下傳的還是往上傳的往下傳的繼承屬性在展開(kāi)時(shí)算往上傳的綜合屬性在歸約時(shí)算時(shí)機(jī)搞反必錯(cuò)。3. 畫(huà)圖題語(yǔ)法分析樹(shù)、短語(yǔ)句柄與 DAG 優(yōu)化的手算流程3.1 最左推導(dǎo)、語(yǔ)法分析樹(shù)、短語(yǔ)直接短語(yǔ)句柄一條龍畫(huà)圖題第 1 題給了一個(gè)文法 G(S)要求對(duì)句子(a,(a,a))給出最左推導(dǎo)并畫(huà)語(yǔ)法分析樹(shù)再對(duì)句型((T,S),a)求短語(yǔ)、直接短語(yǔ)和句柄。這類題看著簡(jiǎn)單但每年都有人把“短語(yǔ)”和“直接短語(yǔ)”搞混。短語(yǔ)是語(yǔ)法樹(shù)中任意一棵子樹(shù)葉子組成的串直接短語(yǔ)是只有父子兩代的子樹(shù)葉子串句柄是最左直接短語(yǔ)。手算步驟我一般這么走先按最左推導(dǎo)把樹(shù)畫(huà)出來(lái)標(biāo)好每個(gè)內(nèi)部節(jié)點(diǎn)對(duì)應(yīng)的產(chǎn)生式然后從葉子往上找每棵子樹(shù)列出所有短語(yǔ)再篩出深度為 1 的子樹(shù)得到直接短語(yǔ)最后取最左邊那個(gè)直接短語(yǔ)就是句柄。注意句型((T,S),a)里 T、S、a 都是終結(jié)符還是非終結(jié)符要看文法定義別想當(dāng)然。3.2 基本塊 DAG 與三地址指令優(yōu)化畫(huà)圖題第 2 題給了一個(gè)基本塊包含DA-C、EA*C、FD*E、S2、TA-C、QA*C、G2*S、JT*Q、KG*5、LKJ、ML要求畫(huà) DAG 并寫(xiě)出優(yōu)化后的三地址指令序列。這題的命門是公共子表達(dá)式消除TA-C和DA-C是同一個(gè)表達(dá)式QA*C和EA*C也是同一個(gè)S2和G2*S里的 2 是常量。DAG 畫(huà)法每個(gè)變量和常量作為葉子運(yùn)算符作為內(nèi)部節(jié)點(diǎn)相同子節(jié)點(diǎn)和相同運(yùn)算符的節(jié)點(diǎn)合并。優(yōu)化后只保留對(duì)出口活躍變量 M 有貢獻(xiàn)的計(jì)算。參考答案給的是DA-C、EA*C、FD*E、MF20這里20來(lái)自2*S中 S2 再乘 5 再乘 2 的常量折疊。下面用一段 Python 演示常量折疊和公共子表達(dá)式合并的判斷邏輯def optimize_block(instructions): expr_map {} # 表達(dá)式 - 結(jié)果變量 const_map {} # 變量 - 常量值 optimized [] for op, arg1, arg2, res in instructions: # 常量折疊兩個(gè)操作數(shù)都是常量時(shí)直接算 if arg1 in const_map and arg2 in const_map: val eval(f{const_map[arg1]} {op} {const_map[arg2]}) const_map[res] val continue key (op, arg1, arg2) if key in expr_map: # 公共子表達(dá)式復(fù)用已有結(jié)果 const_map[res] const_map.get(expr_map[key]) continue expr_map[key] res optimized.append((op, arg1, arg2, res)) return optimized邏輯說(shuō)明expr_map記錄已經(jīng)算過(guò)的表達(dá)式遇到相同(op, arg1, arg2)就跳過(guò)實(shí)現(xiàn)公共子表達(dá)式消除。const_map記錄常量傳播結(jié)果兩個(gè)操作數(shù)都是常量時(shí)直接折疊。參數(shù)上instructions是四元組列表(運(yùn)算符, 左操作數(shù), 右操作數(shù), 結(jié)果)。實(shí)際考試手算時(shí)你不需要寫(xiě)代碼但要有這個(gè)“先折疊常量、再合并相同表達(dá)式、最后只保留活躍變量相關(guān)計(jì)算”的順序意識(shí)。注意DAG 優(yōu)化題最容易翻車的地方是“出口活躍變量”判斷。題目說(shuō)“假設(shè)所有基本塊出口時(shí)只有 M 還被引用”那所有對(duì) M 沒(méi)有貢獻(xiàn)的指令都可以刪。如果你把中間變量也當(dāng)成活躍的優(yōu)化結(jié)果就會(huì)多出好幾條無(wú)用指令。4. 計(jì)算分析題消除左遞歸、FIRST/FOLLOW 與預(yù)測(cè)分析表4.1 消除左遞歸的標(biāo)準(zhǔn)套路計(jì)算分析題第 2 題給了一個(gè)文法 G[S]要求消除左遞歸、構(gòu)造 FIRST 和 FOLLOW 集合、構(gòu)造預(yù)測(cè)分析表。消除左遞歸有固定公式對(duì)于產(chǎn)生式A → Aα | β改成A → βA、A → αA | ε。如果是間接左遞歸先代入再消除。這一步不能跳因?yàn)樽筮f歸不消除LL(1) 預(yù)測(cè)分析直接沒(méi)法做。我一般會(huì)先把文法寫(xiě)成產(chǎn)生式集合逐條檢查有沒(méi)有形如A → A...的直接左遞歸有就套公式。間接左遞歸比如A → B...、B → A...先把 B 的產(chǎn)生式代入 A再消除。消除完記得檢查有沒(méi)有引入新的 ε 產(chǎn)生式這會(huì)影響 FIRST 集計(jì)算。4.2 FIRST 與 FOLLOW 集合的填表法FIRST 集規(guī)則終結(jié)符的 FIRST 是它自己非終結(jié)符看它所有產(chǎn)生式右部第一個(gè)符號(hào)如果是終結(jié)符就加入如果是非終結(jié)符就遞歸求它的 FIRST如果該非終結(jié)符能推出 ε還要繼續(xù)看下一個(gè)符號(hào)。FOLLOW 集規(guī)則開(kāi)始符號(hào)的 FOLLOW 加$對(duì)于產(chǎn)生式A → αBβ把 FIRST(β) 去掉 ε 加入 FOLLOW(B)如果 β 能推出 ε把 FOLLOW(A) 加入 FOLLOW(B)。下面用 Python 實(shí)現(xiàn)一個(gè) FIRST/FOLLOW 計(jì)算器你可以直接拿它驗(yàn)證手算結(jié)果def compute_first(grammar, nonterminals, terminals): first {nt: set() for nt in nonterminals} for nt in nonterminals: for prod in grammar[nt]: if prod[0] in terminals: first[nt].add(prod[0]) changed True while changed: changed False for nt in nonterminals: for prod in grammar[nt]: if prod [ε]: if ε not in first[nt]: first[nt].add(ε); changed True continue for sym in prod: if sym in terminals: if sym not in first[nt]: first[nt].add(sym); changed True break else: before len(first[nt]) first[nt] | (first[sym] - {ε}) if ε not in first[sym]: break if len(first[nt]) ! before: changed True return first邏輯說(shuō)明grammar是字典鍵為非終結(jié)符值為產(chǎn)生式右部列表每個(gè)產(chǎn)生式是符號(hào)列表。terminals是終結(jié)符集合。外層while changed循環(huán)反復(fù)迭代直到 FIRST 集不再變化因?yàn)榉墙K結(jié)符之間可能相互依賴。參數(shù)上prod [ε]判斷空產(chǎn)生式first[sym] - {ε}去掉 ε 再加入當(dāng)前非終結(jié)符的 FIRST。FOLLOW 集計(jì)算類似但要多一步“把 FOLLOW(A) 傳給 FOLLOW(B)”的處理。4.3 預(yù)測(cè)分析表的構(gòu)造與沖突處理預(yù)測(cè)分析表行是非終結(jié)符列是終結(jié)符加$。對(duì)每個(gè)產(chǎn)生式A → α如果終結(jié)符 a 在 FIRST(α) 里就把A → α填進(jìn)M[A, a]如果 ε 在 FIRST(α) 里就對(duì) FOLLOW(A) 里每個(gè)符號(hào) b 填M[A, b] A → α。填完檢查有沒(méi)有一格多填有就是沖突說(shuō)明不是 LL(1) 文法。提示考試?yán)飿?gòu)造預(yù)測(cè)分析表先算 FIRST 再算 FOLLOW順序不能反。FOLLOW 集依賴 FIRST 集先算 FOLLOW 會(huì)漏符號(hào)。填表時(shí)逐條產(chǎn)生式填填完再檢查沖突比邊填邊檢查更穩(wěn)。5. 綜合題SLR 項(xiàng)集族、語(yǔ)法制導(dǎo)翻譯棧與 NFA 確定化5.1 SLR 自動(dòng)機(jī)與 75 的翻譯棧過(guò)程綜合題第 1 題要求對(duì) L 屬性文法用 SLR 自動(dòng)機(jī)做自底向上分析構(gòu)造 SLR 項(xiàng)集族和語(yǔ)法分析表并對(duì)輸入75畫(huà)出語(yǔ)法制導(dǎo)翻譯棧過(guò)程。SLR 在 LR(0) 項(xiàng)集族基礎(chǔ)上用 FOLLOW 集解決歸約沖突如果項(xiàng)A → α·在狀態(tài) I 中且a在 FOLLOW(A) 里就填歸約動(dòng)作。75的分析過(guò)程要跟蹤狀態(tài)棧、符號(hào)棧、輸入串和語(yǔ)義棧。每步 shift 把終結(jié)符壓棧reduce 時(shí)按產(chǎn)生式彈棧并計(jì)算屬性。語(yǔ)法制導(dǎo)翻譯棧里語(yǔ)義值跟著符號(hào)棧同步壓彈。手算時(shí)建議畫(huà)一張四列表狀態(tài)棧、符號(hào)棧、輸入、動(dòng)作動(dòng)作里標(biāo)注 shift/reduce 和語(yǔ)義計(jì)算。5.2 倒數(shù)第二字符為 1 的正則語(yǔ)言正則表達(dá)式到最小 DFA綜合題第 2 題定義在{0,1}上的正則語(yǔ)言 S 由倒數(shù)第二個(gè)字符為 1 的所有字符串組成。正則表達(dá)式是(0|1)*1(0|1)。構(gòu)造 NFA 時(shí)先畫(huà)一個(gè)接受(0|1)*的循環(huán)再串一個(gè)1再串一個(gè)(0|1)最后到終態(tài)。確定化用子集構(gòu)造法最小化用 Hopcroft 算法或填表法。下面用 Python 演示子集構(gòu)造法從 NFA 到 DFA 的核心步驟def subset_construction(nfa_states, nfa_trans, start, accepts): dfa_states [frozenset([start])] dfa_trans {} queue [frozenset([start])] while queue: current queue.pop(0) for sym in [0, 1]: next_set set() for state in current: next_set | nfa_trans.get((state, sym), set()) if not next_set: continue next_frozen frozenset(next_set) dfa_trans[(current, sym)] next_frozen if next_frozen not in dfa_states: dfa_states.append(next_frozen) queue.append(next_frozen) dfa_accepts [s for s in dfa_states if s accepts] return dfa_states, dfa_trans, dfa_accepts邏輯說(shuō)明nfa_states是 NFA 狀態(tài)集合nfa_trans是字典(狀態(tài), 符號(hào)) - 狀態(tài)集合start是初態(tài)accepts是終態(tài)集合。subset_construction用 BFS 遍歷所有可達(dá)子集每個(gè)子集成為一個(gè) DFA 狀態(tài)。dfa_accepts是包含任一 NFA 終態(tài)的子集。參數(shù)上frozenset用來(lái)做哈希鍵因?yàn)槠胀?set 不可哈希。最小化時(shí)先按“是否終態(tài)”分成兩組再逐步細(xì)分直到不可分。注意NFA 確定化時(shí)ε 閉包別漏。如果 NFA 里有 ε 轉(zhuǎn)移每次求 next_set 之前要先算當(dāng)前子集的 ε 閉包再對(duì)每個(gè)符號(hào)求轉(zhuǎn)移后的 ε 閉包。這題雖然沒(méi)明說(shuō)有沒(méi)有 ε 轉(zhuǎn)移但構(gòu)造時(shí)養(yǎng)成先算閉包的習(xí)慣考試不會(huì)吃虧。6. 用這套卷子做自測(cè)三個(gè)驗(yàn)證習(xí)慣和一條血淚教訓(xùn)這套卷子最大的價(jià)值不是“背答案”而是當(dāng)自測(cè)工具用。我建議你按下面三個(gè)習(xí)慣走一遍比單純看答案有效得多。第一個(gè)習(xí)慣限時(shí) 120 分鐘閉卷做一遍做完再對(duì)答案。選擇題 10 分控制在 10 分鐘內(nèi)畫(huà)圖題 25 分給 30 分鐘計(jì)算分析 20 分給 25 分鐘綜合 45 分留 55 分鐘。時(shí)間分配本身就是考試策略的一部分很多人不是不會(huì)是最后綜合題沒(méi)時(shí)間寫(xiě)。第二個(gè)習(xí)慣對(duì)完答案后把每道錯(cuò)題歸到具體知識(shí)點(diǎn)而不是只標(biāo)“錯(cuò)了”。比如第 4 題錯(cuò)了歸到“非遞歸預(yù)測(cè)分析屬性計(jì)算時(shí)機(jī)”DAG 優(yōu)化錯(cuò)了歸到“公共子表達(dá)式消除與常量折疊”。歸類的過(guò)程就是建錯(cuò)題本的過(guò)程。第三個(gè)習(xí)慣手算一遍 FIRST/FOLLOW 和預(yù)測(cè)分析表再用前面給的 Python 腳本驗(yàn)證。手算和代碼結(jié)果對(duì)不上說(shuō)明規(guī)則理解有偏差。這個(gè)交叉驗(yàn)證比反復(fù)看書(shū)快得多。下面這張表是我建議的自測(cè)記錄格式你可以直接抄題號(hào)題型分值我的得分錯(cuò)因歸類重做日期一.1選擇22無(wú)—二.2畫(huà)圖1510DAG 活躍變量判斷考前 3 天三.2計(jì)算158FOLLOW 集漏符號(hào)考前 5 天四.1綜合157SLR 歸約沖突處理考前 2 天最后說(shuō)一條血淚教訓(xùn)。我當(dāng)年第一次做這類卷子覺(jué)得選擇題簡(jiǎn)單先跳過(guò)結(jié)果最后綜合題時(shí)間不夠SLR 項(xiàng)集族畫(huà)了一半就交卷。從那以后我每次自測(cè)都強(qiáng)制按分值分配時(shí)間選擇題再簡(jiǎn)單也不超過(guò) 10 分鐘。這套凌妙根 2021-2022 B 卷的題型分布很典型拿它練時(shí)間分配和錯(cuò)題歸類比刷十套來(lái)源不明的模擬題都管用。希望幫到你。本文還有配套的精品資源點(diǎn)擊獲取