编译原理 | 一、 引论

1. 编译器的作用：

• 读入源语言编写的程序，输出目标语言编写的程序。
• 源程序 ---> (编译器) ---> 目标程序
• 区别于编译器，解释器的特点：不生成目标程序，根据源程序的语义直接运行。

2. 编译器的结构：

• 编译器 = 分析部分（前端） + 综合部分（后端）
  • 分析部分（前端）：
    • 把源程序分解成组成要素、相应的语法结构
    • 使用该结构创建源程序的中间表示
    • 收集和源程序相关的信息，存放到符号表
  • 综合部分（后端）：
    • 根据中间表示和符号表信息构造目标程序
• 编译器顺序执行的一组步骤：

  字符流  -> (词法分析器) ----------> 符号流 
        ---> (语法分析) ------------> 语法树 
        ---> (语义分析) ------------> 语法树 
        ---> (中间代码生成器) -------> 中间表示形式 
        ---> (机器无关代码优化器) ---> 中间表示形式 
        ---> (代码生成器) ----------> 目标机器语言 
        ---> (机器相关代码优化器) ---> 目标机器语言
  

(1) 词法分析：

• 读入源程序的字符流，输出词素 <token-name, attribute-value>
• token-name用于语法分析
• attribute-value指向相应的符号表条目，用于语义分析/代码生成
• 例：

  position = initial + rate * 60
  <id,1>  <=, >  <id, 2>   <+, >   <id,3>  <*, >  <number, 4>
  

(2) 语法分析：

• 根据各个词法单元的第一个分量来创建树形的中间表示形式（语法树）。
• 中间表示形式指出了词法单元流的语法结构。

(3) 语义分析：

• 利用语法树和符号表，检查源程序是否满足语言的语义约束。
• 收集类型信息，用于代码生成、类型检查、类型转换。

(4) 中间代码生成：

• 生成类机器语言的中间表示
• 三地址代码：
  • 每个指令最多包含三个运算分量，易于生成机器语言指令

(5) 代码优化：

• 改进中间代码的质量

(6) 代码生成：

• 把中间表示形式映射到机器语言
  • 寄存器分配、指令选择、内存分配

3. 相关概念：

• 静态/动态语言：
  • 静态：语言策略支持编译器静态决定某个问题
  • 动态：只允许在程序运行时刻作出决定
• 环境 && 状态:
  • 环境：从名字到存储位置的映射
  • 状态：从内存位置到它们的值的映射
• C族语言使用静态作用域。
• 参数传递机制：
  • 值调用：对实在参数求值/拷贝，再存放到被调用过程的形参的内存位置上。
  • 引用调用：实际传递的是实在参数的地址。
• 别名：两个指针指向同一个位置，看起来不同的形式参数实际上是对方的别名。