编译器构建中涉及的算法

编写一个优秀的编译器确实涉及大量经典算法它们贯穿于编译器的各个阶段。下面我将按编译流程为你详细解释这些核心算法。一、词法分析阶段1. 正则表达式 → NFA → DFA 的转换Thompson 构造法将正则表达式转换为等价的非确定有限自动机。算法递归地处理正则表达式的每个子表达式用 ε-转移将它们拼接起来。子集构造法将 NFA 转换为确定有限自动机。核心思想是 DFA 的每个状态对应 NFA 的一个状态集合通过计算 ε-闭包和转移闭包来消除不确定性。DFA 最小化Hopcroft 算法将 DFA 的状态数压缩到最少。算法通过不断划分状态组直到每个组内的状态对所有输入符号的行为完全一致。2. 扫描器生成表驱动词法分析将 DFA 编码为二维状态转移表输入字符驱动状态机运行。高效的实现会用“转移压缩”技术如将字符分类为若干等价类来减小表的大小。二、语法分析阶段1. 自顶向下分析递归下降分析为每个非终结符编写一个递归函数通过向前看符号决定采用哪个产生式。简单直接但需要左递归消除和提取左公因子。LL(1) 分析使用分析表通过计算FIRST 集和FOLLOW 集来构建预测分析表。如果表中每个格子最多有一个产生式则文法是 LL(1) 的。2. 自底向上分析LR(0)、SLR、LR(1)、LALR 分析这是最强大的语法分析技术家族。LR(0) 项集族构造通过闭包运算和转移函数生成所有“项集”带位置标记的产生式。Lookahead 计算在 LR(1) 中每个项携带一个向前看符号大大增强了分析能力。LALR(1) 合并将 LR(1) 中同心核心相同的项集合并在保持分析能力的同时大幅压缩表的大小。Yacc/Bison 使用的正是 LALR(1)。3. 歧义文法的处理运算符优先级与结合性通过为产生式赋予优先级和结合性来消除表达式文法中的歧义而不必改写文法。悬空 else 问题通过“最近匹配”规则解决在分析表中明确选择将 else 与最近的 if 结合。三、语义分析与中间代码生成1. 符号表管理哈希表 作用域链用哈希表实现快速名称查找用栈式作用域链表处理嵌套作用域的进入和退出。树形作用域支持模块、类等更复杂的嵌套结构查找时沿父链向上搜索。2. 类型检查与推导类型统一算法基于 Hindley-Milner 类型推导的变体通过生成类型变量并求解约束方程来推导表达式的类型。类型等价判断区分结构等价类型结构相同即等价和名称等价类型名相同才等价不同语言选择不同策略。3. 中间代码生成语法制导翻译在语法分析过程中为每个产生式附加语义动作即时生成三地址码如t1 a b、静态单赋值形式或抽象语法树。SSA 构造通过插入 Φ 函数并重命名变量来构建静态单赋值形式为后续优化打下基础。常用算法有 Cytron 等人提出的基于支配边界的算法。四、优化阶段核心算法群1. 控制流分析基本块划分识别直线代码段以基本块为优化单位。控制流图构造基本块为节点跳转关系为有向边。支配关系与支配树计算节点 A 是否支配节点 B所有从入口到 B 的路径都经过 A用于识别循环和决定变量提升位置。循环检测基于支配关系识别自然循环有唯一入口节点的循环。2. 数据流分析迭代数据流方程通过求解数据流方程如到达定值、活跃变量、可用表达式等在 CFG 上迭代传播信息直到不动点。格理论与单调框架数据流分析本质上是格上的单调函数迭代保证了算法的终止和正确性。3. 经典优化算法死代码消除标记无用定义并删除。常量传播在 SSA 形式上通过“常量格”上的解释执行将已知常量的变量替换为常量值。复制传播用变量原来的值替换复制语句的目标变量。公共子表达式消除利用可用表达式信息将重复计算的表达式复用。循环不变式外提将循环内计算结果不变的表达式移至循环前。强度削弱将循环中乘除运算转换为更快的加减运算如将i*4替换为t 4。函数内联将被调用函数的体复制到调用点消除调用开销并为后续优化创造机会。4. 寄存器分配图着色寄存器分配Chaitin 算法构建干扰图节点为变量边表示不能共用寄存器用 K 种颜色K 为物理寄存器数着色无法着色的变量溢出到内存。核心包括合并、简化、溢出、选择阶段。线性扫描寄存器分配在变量的活跃区间按顺序排列上进行一次扫描用活跃区间集合分配寄存器。实现简单适合 JIT 编译器。5. 指令调度列表调度在有向无环图表示的数据依赖约束下按启发式优先级如最长路径依次调度指令尽可能填充分支延迟槽或提高指令级并行度。五、代码生成阶段1. 指令选择树覆盖与动态规划将抽象语法树或中间表示树用目标机的指令模式覆盖通过动态规划寻找代价最小的覆盖方案。常用工具如 BURG。宏扩展简单直接的指令模板匹配现代编译器多采用结合了机器描述语言的自动生成方法。2. 窥孔优化滑动窗口模式匹配在生成的指令序列上用一个固定大小的窗口滑动对窗口内的指令序列匹配优化模式如push a; push b; pop b; pop a交换为xchg a,b并反复迭代直到稳定。六、现代编译器中新增的算法1. 基于 SSA 的优化条件常量传播结合控制流信息在 SSA 图上传播常量同时进行不可达代码消除。全局值编号为表达式赋予全局唯一的编号识别所有等价的计算是更强大的公共子表达式消除。部分冗余消除在 SSA 框架下通过插入和移动计算消除所有路径上的冗余同时避免在其他路径上引入新计算。2. 过程间分析过程间数据流分析通过构建调用图在函数边界传播常量、别名等信息。逃逸分析分析指针对象是否逃逸出函数或线程决定能否在栈上分配或进行标量替换。3. 链接时优化跨模块内联与去虚化在链接阶段将多个中间表示模块合并进行全程序分析实现跨文件的内联、虚函数调用转换为直接调用等优化。七、JIT 编译器特有的算法分层编译先用开销小的编译器生成快速但未优化的代码监测热点方法后再用高级优化编译器重新编译。基于采样/计数器的热点检测通过方法调用计数或循环回边计数识别热点代码。内联缓存动态地为多态调用点缓存实际类型加速后续调用。这些算法大多有成熟的理论基础并在实际编译器GCC、LLVM、HotSpot、V8中得到精妙实现。