东北大学编译原理实验：代码优化与DAG构建

“东北大学编译原理实验报告，涉及中间代码优化，包括基本块的有向图DAG构建、常值表达式、公共表达式和无用赋值的优化，以及四元式的重组。” 在这次东北大学编译原理实验中，学生被要求掌握编译器设计中的一个重要环节——代码优化。代码优化是为了提升程序执行效率，通过等价变换来减少计算量或内存占用，而不改变程序的逻辑结果。实验主要关注的是在生成的目标代码或中间代码阶段进行的优化。 首先，实验介绍了基本块的有向图DAG（Directed Acyclic Graph）。DAG是一种无环的有向图，这种结构在编译器优化中用于表示程序中的控制流。每个节点代表一个基本块，即一组在执行过程中没有分支进入或退出的指令序列。通过DAG，可以更直观地识别和处理代码中的局部优化问题。 实验内容涵盖了以下三个方面： 1. 常值表达式的优化：这是消除计算已知常数值的表达式的过程。例如，如果一个表达式的结果在编译时就可以确定，那么这个表达式可以被其结果所替换，从而避免了运行时的计算。 2. 公共表达式的优化：这种优化旨在识别并消除重复计算。如果一个表达式在多个位置被重复计算，可以将计算结果存储在一个临时变量中，然后在后续使用时引用这个变量，以减少不必要的计算。 3. 无用赋值的优化：有时，变量的赋值可能不会影响程序的后续行为。识别并删除这些无用的赋值可以简化代码并提高执行效率。 实验要求学生实现以上三种类型的优化，并基于优化后的DAG重组四元式。四元式是一种表示算术或逻辑运算的抽象语法树的展开形式，通常用于中间代码表示。重组四元式是将优化后的操作顺序转换回可执行的形式。 程序代码示例中，包含了几个函数定义，如`E()`、`T()`、`F()`、`S()`和`H()`，这些可能是解析表达式和构造DAG的辅助函数。此外，还有数据结构的定义，如`shuju`、`siyuanshi`和`you`，它们可能分别用于存储语法分析的符号信息、四元式操作和DAG节点信息。 这个实验是关于编译原理中代码优化实践的一个重要实例，通过实际操作，学生可以深入理解如何运用局部优化技术来提高程序性能。这不仅有助于理解和应用编译原理，也为未来开发高效编译器或解释器打下了坚实的基础。