编译原理期末实战：从NFA到代码优化的完整复盘与避坑指南

1. 词法分析NFA到最小化DFA的实战拆解第一次接触NFA转DFA时我被那些密密麻麻的状态转移箭头搞得头晕眼花。直到考前一周才突然开窍——其实这就是个状态集合打包的游戏。以这次期末考题为例题目给的NFA有5个状态用子集构造法处理后发现得到的DFA竟然已经是最小化的。这种情况在实际操作中并不罕见主要原因是原NFA本身结构就比较精简。子集构造法的核心操作可以拆解为三个步骤首先找出所有ε闭包然后对每个输入符号计算move操作最后将新生成的状态集合作为DFA的新状态。我习惯用表格来记录这个过程左边列出现有状态集合上方列出输入符号每个单元格填写转移后的状态集合。这样不仅不容易漏掉转移检查时也一目了然。关于DFA最小化Hopcroft算法比教材讲的划分法更高效。它的精髓在于不断用当前划分去劈开其他分组。具体实现时我建立了一个工作队列存放待处理的划分每次取出一个划分尝试劈开其他组。虽然考题中的DFA已经最小化但我还是用Hopcroft算法走了一遍流程初始化分为终态和非终态两组经过几次劈分尝试后发现确实无法继续划分这验证了最初的判断。注意考试时如果遇到DFA已经最小化的情况一定要写明判断依据不能直接说无法划分就结束。2. 语法分析LL文法的陷阱与技巧LL文法分析看似简单但有几个隐蔽的坑特别容易踩。这次考的是一个不含ε产生式的文法相对简单但倒序入栈这个操作还是让不少同学栽了跟头。分析表构建的关键在于正确计算FIRST集和FOLLOW集。我总结了一个快速验证的方法对于每个产生式A→α检查FIRST(α)中的每个终结符是否都指向这个产生式。如果同一个终结符出现在多个产生式的FIRST集中就可能存在冲突。这次考题的文法设计得很好每个单元格都只有一个产生式所以构建分析表很顺利。在模拟分析过程时很多人会忘记栈的操作顺序。正确的做法是当使用产生式A→XYZ时要把Z、Y、X按顺序压栈即倒序入栈。我亲眼看到邻座同学因为正序入栈导致整个分析过程出错。一个实用的debug技巧是在纸上同时维护栈和剩余输入串每步操作后都画出当前状态这样能快速定位问题。3. 语法制导翻译三进制转十进制的实现这道10分的题目考察了属性文法的设计能力。题目要求将三进制数转换为十进制看似简单但需要设计合适的综合属性来传递数值信息。我设计的产生式如下N → L { N.val L.val } L → L1 d { L.val L1.val * 3 d.val } L → d { L.val d.val }关键点在于权值的传递每向左扩展一位之前数字的权值都要×3。这通过综合属性L.val实现它是一个自底向上计算的过程。在写语义动作时要特别注意运算符的优先级——乘法要在加法之前计算这个细节决定了最终结果的正确性。实际考试中有些同学尝试用继承属性来实现结果导致属性计算顺序混乱。我的经验是能用综合属性解决的问题就不要用继承属性前者不仅实现简单而且不容易出错。4. 寄存器分配活性分析与图着色寄存器分配是本次考试的重头戏占了30分。题目给出了一个基本块要求先进行活性分析然后构造冲突图最后分配寄存器。活性分析的诀窍是从后向前计算。我习惯用不同颜色的笔在代码旁边标注每个变量的生存区间。具体操作时先初始化最后一条指令的out集然后逆向计算每个语句的in和out集。这个过程要注意控制流的变化点比如跳转指令会合并不同路径的活性信息。构造冲突图时我发现了几个常见的错误做法一是把生存期重叠但不冲突的变量也连上边比如两个变量虽然都存活但从不同时使用二是漏掉了隐含的冲突关系。正确的做法是只有当两个变量的生存期有重叠并且它们可能同时占用寄存器时才需要画边。考题的冲突图比较简单用贪心算法就能完成着色。我采用的策略是每次选择度数最高的节点分配寄存器如果冲突就换下一个可用寄存器。最终只用了3个寄存器就完成了分配比题目要求的最少寄存器数还少一个。5. 代码优化从繁琐到精简的蜕变最后的代码优化题非常有意思初始代码看起来杂乱无章经过几步优化后竟然能看出是一个数组交换操作。这部分的20分可以说是送分题只要掌握基本优化技术就能拿满分。公共子表达式消除是第一个要做的优化。我先把所有表达式编号然后找出重复计算的子表达式。比如题目中的j-2和j2都出现了多次可以用临时变量保存这些值。这里有个小技巧先处理最内层的子表达式由内向外逐步替换。常量传播的效果立竿见影。在替换掉公共子表达式后我发现有些表达式中的变量已经被常量替换这样又可以进一步简化。比如T4T3-2而T3j2所以T4实际上就是j。这种连续的替换需要耐心建议在草稿纸上画出依赖关系图。强度削弱在这个例子中效果不明显但我还是尝试用移位代替乘法如用2代替*4。不过最终代码并没有因此变得更高效这说明优化不是越多越好要看实际效果。最终化简后的代码清晰地展示了一个数组元素交换操作验证了优化过程的正确性。