编译原理期末自救指南：从NFA到LR(1)，手把手带你搞定六大必考大题

编译原理六大核心题型速通手册从NFA到LR(1)的实战拆解1. NFA确定化与DFA化简的标准化流程面对NFA到DFA的转换题型90%的失分源于子集构造法的步骤混乱。以下是经过验证的解题流水线步骤一构建状态转移矩阵计算初始状态I的ε闭包ε_CLOSURE({S0})对每个输入符号a计算ε_CLOSURE(Move(I,a))将新状态加入状态集重复直到无新状态产生关键陷阱忘记处理空转移ε边遗漏未标注的死亡状态错误标记终止状态必须包含原NFA的终止状态DFA化简的黄金法则1. 初始划分终态组 vs 非终态组 2. 对每个分组G和输入符号a - 如果状态s和t在a上的转移目标不在同一组 - 则将s和t拆分到不同子组 3. 重复直到不可再分注意最小化后的DFA状态数通常比原始少30%-50%这是快速验证结果合理性的依据2. LL(1)文法分析的三大武器库2.1 首符集构造的递归策略def FIRST(X): if X是终结符: return {X} result set() for 产生式 X→Y1Y2...Yn: for i from 1 to n: first FIRST(Yi) result.update(first - {ε}) if ε not in first: break else: # 所有Yi都能推导出ε result.add(ε) return result2.2 后继符集的传播算法初始化FOLLOW(S) {#}对每个产生式A→αBβ将FIRST(β)-{ε}加入FOLLOW(B)如果β能推导出ε将FOLLOW(A)加入FOLLOW(B)典型错误案例忽略产生式右端非终结符的连锁反应忘记处理#符号的特殊地位2.3 预测分析表的冲突检测表条件是否LL(1)不同产生式的FIRST集相交×可空产生式与FOLLOW集相交×分析表有多重入口×3. 算符优先分析的二元关系矩阵FIRSTVT/LASVVT的快速计算法FIRSTVT(P)构建 1. P→a... ⇒ a∈FIRSTVT(P) 2. P→Qa... ⇒ a∈FIRSTVT(P) 3. P→Q... ⇒ FIRSTVT(Q)⊆FIRSTVT(P) LASTVT(P)构建 1. P→...a ⇒ a∈LASTVT(P) 2. P→...aQ ⇒ a∈LASTVT(P) 3. P→...Q ⇒ LASTVT(Q)⊆LASTVT(P)优先关系矩阵的构造口诀并列出现a≖b中间有非终结符a≖b先a后Ra⋖FIRSTVT(R)先R后bLASTVT(R)⋗b实战技巧使用三角矩阵存储可节省50%空间优先函数存在当且仅当关系矩阵无冲突环4. LR(1)项目集族的构造秘籍4.1 项目集闭包的计算模板def closure(I): repeat: for [A→α·Bβ, a] in I: for B→γ in productions: for b in FIRST(βa): I.add([B→·γ, b]) until I不再变化 return I4.2 四种LR分析法的核心区别类型展望符冲突解决状态数LR(0)无不能解决最少SLRFOLLOW集部分解决同LR(0)LR(1)精确1个完全解决最多LALRLR(1)合并折中方案同SLR项目集规范族的构建陷阱LR(1)中相同核心不同展望符的项目要分开LALR合并时可能引入新的归约-归约冲突忘记拓广文法会导致初态不唯一5. 数组引用的地址计算模型多维数组地址计算公式对于A[d1][d2]...[dn] 地址 base ((i1-l1)*d2*d3*...*dn (i2-l2)*d3*...*dn ... (in-1-ln-1)*dn (in-ln)) * w四元式生成模式计算各维下标表达式如有逐维计算VARPART(*, 下标, 因子, temp1) (, temp1, 前序结果, temp2)最终计算CONSTPART(, CONST, VARPART, 最终地址)6. 控制流语句的翻译蓝图6.1 关键四元式模式库结构特征四元式数量if-then(jz, A, _, L1)1if-then-else(j, _, _, L2)2while(j, _, _, L1)3逻辑与(jnz, A, _, L2)26.2 回填技术的三要素链式管理用BP记录未完成跳转的指令地址合并策略相同出口点的链需要合并回填时机遇到终结符时立即回填典型错误模式忘记处理短路计算的跳转逻辑错误合并不同层级的BP链遗漏循环结束后的无条件跳转实战检验真题破解示范案例NFA确定化给定NFA状态图 0 --a-- 1 1 --ε-- 2 2 --b-- 3 3 --ε-- 4 4 --c-- [5]解题步骤初态闭包ε_CLOSURE({0}) {0}计算Move(0,a)并求闭包Move({0},a) {1}ε_CLOSURE({1}) {1,2}新状态{1,2}加入队列继续处理直到无新状态...最终DFA状态转换表状态abc{0}{1,2}∅∅{1,2}∅{3}∅{3}∅∅{4,5}{4,5}∅∅∅效率优化技巧使用二进制编码表示状态集如{1,2}→0b0110提前标记终止状态包含原NFA终止状态的集合采用拓扑排序处理状态避免重复计算掌握这六大题型的标准化解题路径配合真题反复演练3-5遍完全可以在72小时内实现从及格线到优秀级的跨越。记住编译原理的题型套路性极强精准把握每个知识点的出题角度和评分要点比泛泛而谈的全面复习更有效。