2026-04-11-编译原理

一、编译与解释

1.1 编译方式

编译方式的处理阶段：

词法分析 → 语法分析 → 语义分析 → 中间代码生成 → 代码优化 → 目标代码生成

• 编译器：翻译时将源程序翻译成独立保存的目标程序
• 机器上运行的是与源程序等价的目标程序
• 编译程序和源程序都不再参与目标程序的运行过程

1.2 解释方式

解释方式的处理阶段：

词法分析 → 语法分析 → 语义分析

• 解释器：翻译源程序时不生成独立的目标程序
• 解释程序和源程序要参与到程序的运行过程中

1.3 编译器与解释器的对比

重要结论：

• 编译器和解释器都不可省略词法分析、语法分析、语义分析，且顺序不可交换
• 编译器方式中，中间代码生成和代码优化不是必要的，可省略
• 即编译器方式可以在词法分析、语法分析、语义分析阶段后直接生成目标代码

二、编译过程各阶段详解

2.1 词法分析

• 输入：源程序
• 输出：记号流（Token Stream）
• 主要作用：分析构成程序的字符及由字符按照构造规则构成的符号是否符合程序语言的规定

相关工具：

• 正规式：用于描述词法规则
• 有限自动机：词法分析的一个工具，能正确地识别正规集
  • 确定的有限自动机（DFA）：对每一个状态来说识别字符后只有一个转移状态
  • 不确定的有限自动机（NFA）：对每一个状态来说识别字符后有一个以上的转移状态

2.2 语法分析

• 输入：记号流
• 输出：语法树（分析树）
• 主要作用：对各条语句的结构进行合法性分析；分析程序中的句子结构是否正确
• 重要结论：语法分析阶段可以发现程序中所有的语法错误

语法分析方法：

• 自顶向下语法分析方法：递归下降分析法、预测分析法
• 自底向上语法分析方法：移进—归约分析法、LR分析法

文法：

• 上下文无关文法：大多数程序设计语言的语法规则用上下文无关文法描述

2.3 语义分析

• 输入：语法树（分析树）
• 主要作用：进行类型分析和检查
• 重要结论：
  • 语义分析阶段不能发现程序中所有的语义错误
  • 语义分析阶段可以发现静态语义错误，不能发现动态语义错误
  • 动态语义错误运行时才能发现

2.4 中间代码生成

• 常见的中间代码形式：后缀式、三地址码、三元式、四元式和树（图）等形式
• 特点：
  • 中间代码与具体的机器无关（不依赖具体的机器）
  • 可以将不同的高级程序语言翻译成同一种中间代码
  • 中间代码可以跨平台
  • 因为与具体的机器无关，使用中间代码有利于进行与机器无关的优化处理和提高编译程序的可移植性

2.5 代码优化

• 对中间代码进行优化，提高目标代码的执行效率
• 与具体的机器无关的优化在中间代码上进行

2.6 目标代码生成

• 特点：目标代码生成阶段的工作与具体的机器密切相关
• 寄存器的分配工作处于目标代码生成阶段

三、符号表

• 作用：不断收集、记录和使用源程序中一些相关符号的类型和特征等信息，并将其存入符号表中
• 目的：记录源程序中各个字符的必要信息，以辅助语义的正确性检查和代码生成

四、中缀与后缀表达式

4.1 表达式形式

4.2 求值方法

• 后缀式利用栈进行求值
• 语法树的后缀式为后序遍历
• 语法树的中缀式为中序遍历

五、编译过程总结图

源程序
  ↓
词法分析（正规式、有限自动机）→ 记号流
  ↓
语法分析（上下文无关文法）→ 语法树/分析树
  ↓
语义分析（类型检查）→ 语法树
  ↓
中间代码生成（后缀式、三地址码、四元式等）→ 中间代码
  ↓
代码优化 → 优化后的中间代码
  ↓
目标代码生成（寄存器分配）→ 目标代码

六、关键考点速记

1. 编译器 vs 解释器：编译器生成独立目标程序，解释器不生成；解释器参与运行过程
2. 不可省略的阶段：词法分析、语法分析、语义分析（编译器和解释器都不可省略，顺序不可交换）
3. 语法分析：能发现所有语法错误
4. 语义分析：能发现静态语义错误，不能发现动态语义错误
5. 中间代码：与机器无关，可跨平台，有利于优化和移植
6. 目标代码生成：与机器密切相关，寄存器分配在此阶段
7. DFA vs NFA：DFA每个状态识别字符后只有一个转移状态，NFA有一个以上
8. 后缀式求值：利用栈进行求值