编译原理期末实战：从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和j+2都出现了多次，可以用临时变量保存这些值。这里有个小技巧：先处理最内层的子表达式，由内向外逐步替换。

常量传播的效果立竿见影。在替换掉公共子表达式后，我发现有些表达式中的变量已经被常量替换，这样又可以进一步简化。比如T4=T3-2，而T3=j+2，所以T4实际上就是j。这种连续的替换需要耐心，建议在草稿纸上画出依赖关系图。

强度削弱在这个例子中效果不明显，但我还是尝试用移位代替乘法（如用<<2代替*4）。不过最终代码并没有因此变得更高效，这说明优化不是越多越好，要看实际效果。最终化简后的代码清晰地展示了一个数组元素交换操作，验证了优化过程的正确性。