1. 编译过程概览

编译步骤流程图

• Front End：用于确定程序含义的步骤
• Back End：构造等价目标语言的步骤
• Passes：
  • 另外一种描述编译过程的方式
  • Passes是相对于其余编译序列化的一个阶段或一组阶段：它在前一阶段完成之前不会启动，并且在任何后续阶段开始之前完成。
  • 编译器通常分为一系列Passes，因此编译器可以为多台机器共享前端（目标语言）

解释步骤流程图

• 一个解释器有着和编译器相似的Front End结构
• 但是没有Back End去翻译成目标语言，而是通过直接执行（解释）中间形式（Intermediate Form）

下面对寻找最大公约数的程序进行分析：

int main() { 
    int i = getint(), 
    j = getint(); 
    while (i != j) { 
        if (i > j) i = i - j; 
        else j = j - I; 
    } 
    putint(i); 
}

2. 词法和语义分析

Phrase I：词法分析（Scan/Lexical analysis）

• 扫描器（Scaner）逐个阅读字符 (‘i’ , ‘n’ , ‘t’ , ‘ ’ , ‘m’ , ‘a’ , ‘i’ , ‘n’ , ‘(’ , ‘)’ , etc.)，然后将它们分类成Token
• 扫描过程（Scanning）也称为词法分析。扫描程序的主要目的是通过减小输入内容的大小（将原始内容转换为Token）并删除像空格这样的无关字符来简化解析器（Parser）的任务。扫描过程通常还会删除带有行号和列号的注释和标签Token。
• 任何格式错误的Token（例如C中的123abc或$@foo）都会导致扫描程序产生错误消息。
  Token

Phrase II：语法分析（Parsing/Syntax analysis）

• 解析（Paring）将Token组织到一个解析树（Paring Tree）中，该树表示更高级别的构造结构（语句，表达式，子函数（Subroutine）等）

• 构造解析树依赖于一种称为无上下文语法（Context-Free Grammer）的潜在递归规则。每个规则都有一个箭头符号（→），左侧是构造名称，右侧是可能的扩展名。（这里的ε代表空字符串，表示可以删除block-item-list_opt结构，假设不存在）
  

  样例递归规则

• GCD程序的解析树：

  
  Parse Tree（Part1）
  Parse Tree（Part2）
  • 每一个独立的枝干表示对某一语法规则的应用
  • 从左到右的叶节点就是Scanner接收到的Token
  • 每一个构造结构都是一个节点，组成它的部分就是它的子节点
  • Parse Tree的复杂性更多地反映了语法而不是输入程序。其中大部分是使用这样的像block-item-list_opt和block-item_opt一样的人为添加结构，或者是像assignment-expression, additive-expression, multiplicative-expression这样的为了捕获算术表达式中的优先级和关联性的结构。

• 任何语法上无效的Token序列（例如，C中的A = XYZ）都应该导致来自解析器的错误消息。

3. 语义分析和形成内部形式

Phrase III：语义分析（Semantic analysis）

• 语义分析是分析程序的含义。语义分析器识别同一标识符的多次出现，何时意味着相同的引用，并确保使用是一致的。在大多数语言中，它还跟踪标识符和表达式的类型，以验证是否类型匹配并指导Back End部分生成目标代码。

• 符号表（Symbol Table）：为了协助工作，语义分析器通常构建和维护一个符号表数据结构，该结构将每个标识符映射到已知的信息。在符号表中，语义分析器强制执行大量各种规则，这些规则不是由无上下文语法和解析树的层次结构捕获的。例如在C语言中：

  • 每一个标识符需要在使用前定义
  • 标识符被用在不恰当的地方（将String与整型进行计算等问题）
  • 对子函数传入错误的实参个数
  • 在void函数里返回值
  • ...

• 在许多Front End的实现中，语义分析器的工作采用语义动作例程（Semantic Action Routine）的形式，当语法分析器意识到它已到达语法规则中的特定点时，由语法动作例程调用。

• 并非所有语义规则都可以在编译时（或在解释器的解释阶段）进行检查，编译时检查被称为语言的静态语义。那些必须在运行时（或在解释器的解释阶段）检查的那些被称为语言的动态语义。例如：

  • 除非已为变量赋值，否则变量永远不会在表达式中使用。
  • 指针永远不会被解除引用，除非它们引用有效对象。
  • 数组下标表达式位于数组的范围内。
  • 算术运算不会溢出。

• 语义分析器通常通过移除树内部的大多数“人造”节点将解析树转换为抽象语法树（也称为AST，或简称为语法树）。语义分析器还使用有用信息注释剩余节点，例如从标识符到其符号表条目的指针。附加到特定节点的注释称为其属性。
  

  抽象语法树

• 在许多编译器中，带注释的语法树（AST）构成从前端传递到后端的中间形式。在其他编译器中，语义分析以树的遍历（通常是单遍）结束，并生成一些其他的中间形式，一种常见的这种形式包括控制流图。
  

  控制流图

• 解释器解释运行语法树将从根开始，并按顺序访问树主干上的语句。第一个“：=”节点，解释器会注意到正确的子节点是一个调用，因此它将调用getint函数（符号表3）并将结果分配给i（符号表5）。在第二个“：=”节点，解释器将类似地将getint的结果分配给j。在while节点，它将重复计算左（“？=”）子节点，如果结果为true，则递归地在右（if）子节点下遍历树。最后，一旦while节点的左子节点评估为false，解释器将移动到最终的调用节点，并输出其结果。

4. 生成目标语言代码

Phrase IV：目标代码生成

• 给定语法树中包含的信息，编译器的代码生成阶段将中间形式转换为目标语言。

• 为了生成汇编语言或机器语言，GCD程序汇编代码生成器遍历符号表以将位置分配给变量，然后遍历程序的中间形式，为变量引用生成加载和存储，穿插适当的算术运算，测试和分支。

  
  GCD的汇编代码
  • esp，ebp，eax，ebx和edi是寄存器（特殊存储位置，数量有限，可以非常快速地访问）。
  • -8（％ebp）是指地址在寄存器ebp中的位置之前的8个字节的存储单元
  • 在这个程序中，ebp作为一个基础指针，我们可以从中找到变量i和j。子程序调用指令的参数通过将其推入堆栈来传递，其中esp是堆栈顶部指针。
  • 返回值返回寄存器eax。算术运算用操作的结果覆盖它们的第二个参数。

• 通常汇编代码生成器保存符号表在目标代码的不可执行部分中以供符号调试器之后使用。

5*. 代码优化

Optional Phrase：代码优化

• 代码改进通常被称为优化，它是一个可选的编译阶段。其目标是将程序转换为优化后的版本，以更高效、更快速、使用更少内存来计算相同结果。
• 一些改进与机器无关，在语义分析和中间代码生成之后优化，例如对中间形式的优化。

• 另外一些改进需要理解目标机器（或者目标语言执行程序），在目标代码生成之后优化。

  
  优化后的汇编代码
• 与机器无关的代码优化能够指定在主循环执行期间i和j可以保存在寄存器中。（如果循环包含对这些可能重用的寄存器的子函数的调用，或者尝试修改i或j的情况，则不会出现这种代码优化）。
• 需要目标机器的代码优化能够分配i和j到目标机器的实际寄存器。对于具有复杂内部行为的现代微处理器，编译器通常可以生成比人类汇编语言程序员更好的汇编代码。