编译器原理与实现：从理论到实战的全景指南

// 示例：C语言代码
int x = 10 + 5;
// 词法分析后生成的Token流
[KEYWORD: 'int'], [IDENTIFIER: 'x'], [OP: '='], [NUMBER: '10'], [OP: '+'], [NUMBER: '5'], [SEMICOLON: ';']

2. 语法分析（Syntax Analysis / Parsing）

语法分析器（Parser）接收词法分析器生成的Token流，根据语言的语法规则（通常由上下文无关文法CFG描述）检查Token序列是否合法，并构建抽象语法树（AST）。

核心任务：

• 检测语法错误（如括号不匹配、缺少分号）
• 确定程序的层次结构
• 生成AST，反映代码的逻辑结构

常见解析算法：

• 自顶向下解析：如递归下降解析、LL(1)解析。
• 自底向上解析：如LR(1)、LALR(1)、GLR解析。
• 工具：Yacc、Bison、ANTLR、JavaCC等。

// 语法树示意（AST）
        =
       / 
      x   +
         / 
        10  5

3. 语义分析（Semantic Analysis）

语义分析器检查AST是否符合语言的语义规则，如类型检查、作用域检查、变量声明检查等。这一阶段确保程序不仅在语法上正确，而且在逻辑上合理。

核心任务：

• 类型检查：确保操作数类型兼容（如不能将字符串与整数相加）。
• 作用域分析：确保变量在声明后才被使用，且访问权限正确。
• 函数调用检查：检查函数参数数量、类型是否匹配。
• 符号表管理：维护变量、函数、类的信息，用于后续代码生成。

// 语义错误示例
int x = 10;
String s = "hello";
int y = x + s; // 错误：不能将字符串与整数相加

4. 中间代码生成（Intermediate Code Generation）

中间代码是一种介于源代码和目标代码之间的表示形式，通常与具体机器无关。常见的中间表示（IR）包括三地址码（Three-Address Code）、字节码（Bytecode）和LLVM IR。

核心任务：

• 将AST转换为线性的、易于优化的中间表示。
• 简化复杂表达式，如将 a = b + c d 转换为 t1 = c d; a = b + t1;
• 为后续优化和代码生成提供统一的基础。

// 三地址码示例
t1 = c  d
a = b + t1

5. 代码优化（Code Optimization）

代码优化器对中间代码进行改进，以提高目标代码的执行效率或减小代码大小。优化可以分为局部优化、循环优化和全局优化。

常见优化技术：

• 常量折叠：将编译期可确定的表达式提前计算，如 int x = 2 + 3; 优化为 int x = 5;
• 死代码消除：移除永远不会被执行的代码或未被使用的变量。
• 循环优化：如循环展开、循环不变量外提、强度削弱等。
• 内联展开：将小函数直接嵌入调用处，减少函数调用开销。

6. 目标代码生成（Code Generation）

代码生成器将优化后的中间代码转换为特定目标架构的机器码或汇编代码。这一阶段需要考虑目标机器的寄存器分配、指令选择、内存布局等。

核心任务：

• 指令选择：将中间操作映射为目标机器的指令。
• 寄存器分配：决定变量存储在寄存器还是内存中。
• 指令调度：调整指令顺序以充分利用CPU流水线。
• 后端优化：针对特定硬件特性进行进一步优化。

// 汇编代码示例（x86）
mov eax, 10
add eax, 5
mov [x], eax