1.2 TheStructure of a Compiler

compiler的两个重要组成部分：analysis（分析） and synthesis（合成）

• analysis：将source program分成一些组成部分，给它们加上一些语法分析结构（grammatical structure），然后用这些结构去创造出一些源程序的中间表达方式。如果分析时发现源程序在句法组成(syntactically formed)或语义(semanitically)上有错误，那么它就会提供一些情报信息，让用户能够采取正确的行动。在分析阶段，也会搜集源程序的信息并将它们存储进一个叫做symbol table的数据结构中，与中间表示一起传递到合成部分。
• synthesis：用中间表达和symbol table中的信息构建希望的目标程序。

analysis part通常被称为compiler的前端，synthesis part通常被成为compiler的后端。

在实际中，几个阶段可能会被组织在一起，两个被组织的阶段之间的表达方式并不需要被构造地非常精确。symbol table被所有阶段所共用。有的编译器在前端和后端之间有机器依赖的优化阶段(optimization phases)，这个优化阶段的目的执行中间表达的转换，使得后端可以创造出更好的目标程序。

Phases of a compiler

1.2.1 Lexical Analysis(词法分析)：

compiler的第一个阶段，被称为lexical analysis或者scanning。
词法分析器读取组成源程序的字符流(stream of characters)并将这些字符分组为有意义的序列，lexemes。对每个lexeme，词法分析器会产生这样一种形式的标记：
<token-name,attribute-value> 以这个形式传递给下一个阶段，syntax analysis（语法分析）
token name是一个抽象符号在syntax analysis阶段被使用,attribute value在这个symbol table中的这个标记的入口。来自symbol table入口的信息对semantic analysis和code generation来说是需要的。
比如源程序有这样一句赋值语句：

position = initial + rate * 60 （1.1）

1. position是一个lexeme被映射到标记<id , 1>，其中id是一个代表标识符(identifier)的抽象符号，1指向symbol-table中position的入口。一个identifier的symbol-table entry拥有这个identifier的信息，包括它的名字和类型。
2. 赋值符号 = 是一个lexeme，映射到标记<=>。因为这个标记不需要attribute-value，所以我们忽略了第二个组成部分。我们可以用任何抽象符号比如assign来作为token-name，但是为了计数的方便，我们使用这个lexeme本身作为抽象符号的名字。

• 为什么它不需要attribute-value？

3. initial是一个lexeme映射到标记<id，2>，2指向initial的symbol-table entry。
4. • 是一个lexeme映射到标记< + >
5. rate是一个lexeme映射到标记<id ，3>，3指向rate的symbol-table entry。
6. 是一个lexeme映射到标记<>
7. 60是一个lexeme映射到<60>
   lexemes之间的空格会被lexical analyzer丢弃。
   这是上述赋值语句经过了lexical analysis后的表示：
   <id,1> <=> <id,2> <+> <id,3> <*> <60> （1.2）
   在这个表达式中，token names：=，+ 和 * 分别是赋值、加法、乘法运算符的抽象标识。
   
   Translation of an assignment statement Fig.1

1.2.2 Syntax Analysis（语法分析）

compiler的第二个阶段是syntax或parsing，语法分析器使用lexical analyzer创造的标记的第一个部分来生成一个树状的中间表达，用来描述这个标记流在语法上的结构。一种典型的表示方法就是syntax tree，它的内部节点表示一个操作，而节点的孩子表示这个操作的参数。（参见上图Fig.1）
compiler后面的阶段会用到这个语法结构去帮助分析源程序和产生目标程序。

1.2.3 Semantic Analysis（语义分析）

语义分析使用了syntax tree和symbol table里面的信息，根据语言的定义，来检查源程序的连贯性。
语义分析的一个重要部分是类型检测（type checking），compiler会检查每个操作符是否有匹配的操作数。比如，许多编程语言的定义要求一个数组的数据必须是integer，当数组中出现了浮点数的时候，compiler就必须报告这个错误。
语言规范也许会允许一些强制的类型转换，这被叫做coercions。比如，一个二进制运算符被用在一对整数或一对浮点数之间。如果运算符被用在一个整数和一个浮点数之间时，compiler也许会转换或强制转换使整数变为浮点数。
如图Fig.1中的rate被看作一个浮点数，而就被应用在一个浮点数rate和整数60之间，此时发现semantic analyzer有一个额外的节点inttofloat*，这明确表示将它的整数参数转换为了浮点数参数。

1.2.4 Intermediate Code Generation（中间代码生成）

在将源程序转化为目标程序的过程中，compiler也许会构造出一个或多个具有多种多样形式的中间表达方式，它们通常在syntax和semantic analysis中使用。
对源程序执行完语法和语义分析后，许多compiler会生成一个低级的或机器有好的（machine-like）中间表达，我们可以把这看作是代表了一个抽象机器的程序。这个中间表达应该有两个重要性质：它应该是易于产生的而且应该易于被转化为目标机器。
在Chapter 6中，我们会考虑一种叫做three-address code（三地址代码）的中间表达形式，它由一系列，一个指令带着三个操作数的装配式指令（assembly-like instructions）组成。每个操作数都可以表现得像一个寄存器一样。Fig.1的中间代码的输出由三地址代码序列组成。

t1 = inttofloat(60)
t2 = id3 * tq
t3 = id2 + t2 
id1 = t3              （1.3）

几个值得注意的地方：

1. 每个三地址分配指令的右侧做多只能有一个操作符，因此，这些指令确定了执行操作的顺序；乘法在加法之前。
2. compiler必须生成一个临时的名字去代表被一条三地址指令计算出来的值。
3. 一些三地址指令，比如（1.3）所示的第一条和最后一条指令，拥有的操作数小于三个。

1.2.5 Code Optimization（代码优化）

机器依赖(machine-independent)的代码优化阶段尝试改善中间代码使得得到的目标代码的结果更好。通常来说这意味着更快，但是还有被期望的其他目的，比如更短的代码，或者目标代码消耗更少的能源。例如，一个简单的算法使用来自语义分析器的树表示中的每个操作符的指令来生成中间代码（1.3）。
一个简单的中间代码生成算法紧跟着一个代码优化，是一个产生良好目标代码的合理方法。优化器可以推导出，60从整数到浮点数的转换可以在编译时一次性完成，所以可以通过将整数60替换为浮点数60.0来消除操作inttofloat。更甚者，t3可以只使用一次来将其值传输到id1，因此优化器可以将(1.3)转换为较短的序列

t1 = id3 * 60.0
id1 = id2 + t1          (1.4)

不同编译器执行的代码优化量差别很大。在那些做得最多的，所谓“优化编译器”中，这一阶段花费了大量的时间。有一些简单的优化方法可以显著改善运行速度，而不会过多的减慢编译速度。

1.2.6 Code Generation（代码生成）

代码生成器将源程序的中间表示作为输入，并将其映射到目标语言。如果目标语言是机器代码，程序中所用到的每一个变量在寄存器或内存中的位置将会被选择。然后，中间指令会被翻译为一系列的机器指令来执行相同的任务。代码生成的一个重要方面是明智地分配寄存器来保存变量。
比如，使用寄存器R1和R2，（1.4）中的中间代码或许会被翻译为如下的机器代码

LDF      R2,     id3
MULF     R3,     R2,   #60.0
LDF      R1,     id2                     (1.5)
ADDF     R1,     R1,   R2
STF      id1,    R1

每个指令的第一个操作数指定了一个目的地。每个指令中的F告诉我们它处理的是浮点数。（1.5）中的代码将地址id3中的内容加载到寄存器R2中，然后将它与浮点常量60.0相乘。#代表60.0被作为一个中间常量。第三条指令将id2移动到寄存器R1中，第四条指令将它与之前计算出来存储在R2中的值相加。最终R1中的值被放入地址id1中，代码正确地完成了赋值语句（1.1）。
这个关于代码生成的讨论忽略了源程序中标识符的存储分配这一重要问题。我们将在Chapter 7中看到，运行时存储的组织取决于要编译的语言。存储分配决策是在中间代码生成或代码生成期间完成的。

1.2.7 Symbol-Table Management

compiler的一个基本功能是记录源程序中使用的变量名，并收集有关每个名称的各种属性的信息。这些属性可以提供有关为名称分配的存储的信息，它的类型、它的作用域（在程序中可以使用它的值），对于过程名，例如它的参数的数据和类型，传递每个参数的方法（例如，通过值或引用），和返回的类型。
symbol table是一个包含了每个变量名称的记录，并带有名称属性的字段的数据结构。这个数据结构应该被设计来允许编译器快速找到每个名称的记录，并快速地存储或检索该记录中的数据。

1.2.8 The Grouping of Phases into Passes

阶段的讨论涉及编译器的逻辑组织。在实现中，来自几个阶段地活动可以组合在一起成为读取输入文件和写入输入文件的pass。比如，在lexical analysis，syntactic analysis，semantic analysis和intermediate code generation这些前端阶段或许会被组合进一个pass。Code optimization或许会变成一个可选的pass。然后可能会有一个后端过程，包括为特定目标机器生成代码。
一些编译器集合是围绕着精心表示的中间表示创建的，这些表示允许特定语言的前端与特定目标机器的后端交互。使用这些集合，我们可以通过将目标计算机的不同前端与后端结合起来，为一台目标计算机生成针对不同源语言的编译器。

1.2.9 Compiler-Construction Tools

1. Parser generators：从编译语言的语法自动生成语法分析器的解析器生成器。
2. Scanner generator：从一种语言符号的常规表达式描述生成词法分析器的扫描生成器。
3. Syntax-directed translation：生成用于遍历解析树和生成中间代码的例程集合。
4. Code-generator generators：从用于将中间语言的每个操作翻译成用于目标机器的机器语言的规则集合生成代码生成器。
5. Data-flow analysis engines：有助于聚集有关值如何从程序的一个部分传递到另一个部分的信息。Data-flow analysis是code optimization的一个关键部分。
6. Compiler-construction toolkits：提供了一组集成的例程，用于构造编译器的各个阶段。