编译原理--引论（二）

一个编译器的结构

• 把编译器看作一个黑盒子，能够把源程序映射为在语义上等价的目标程序
• 映射过程，分成两部分，分析部分和综合部分

分析（analysis）

• 把源程序分解成为多个组成要素，在这些要素之上加上语法结构
• 使用这个结构创建该源程序的一个中间表示
• 分析部分检查出源程序没有按照正确的语法构成，或者语义不一致，就必须提供有用信息，使得用户改正
• 分析部分还会收集有关源程序的信息，并把信息存放在一个称为符号表（symbol table） 的数据结构中，符号表将和中间表示形式一起传送给综合部分

综合（synthesis）

• 根据中间表示和符号表中的信息来构造用户期待的目标程序
• 分析部分经常被称为编译器的前端（front end），综合部分称为后端（back end）

编译过程顺序执行了一组步骤

• 每个步骤的源程序的一种表示方式转换称另一种表示方向
• 一个典型的编译程序分解成多个步骤的方式
• 在实践中，多个步骤可能被组合在一起，而这些组合在一起的步骤间中间表示不需要被明确构造出来
• 存放整个源程序的信息的符号表可由编译器的各个步骤使用
• 有些编译器在前端和后端之间有一个与机器无关的优化步骤，目的在中间表示之上进行转换，以便后端程序能够生成更好的目标程序

1. 词法分析

• 编译器的第一个步骤称为词法分析（lexical analysis）或扫描（scanning）
• 词法分析器读入组成源程序的字符流并将它们组织成为有意义的词素（lexeme）的序列
• 对于每个词素，词法分析器产生如下形式的词法单元（token）作为输出：<token-name, attribute-value>　
• 这个词法单元被传送给下一个步骤，即语法分析
• 第一个分量 token-name 是一个由语法分析步骤使用的抽象符号
• 第二个分量 attribute-value 指向符号表中关于这个词法单元的条目
• 符号表条目的信息会被语义分析和代码生成步骤使用

position   =    initial   +   rate   *   60   词素    词素     词素    词素   词素 词素 词素

 这个赋值语句的字符组合成如下词素，映射成为如下词法单元，这些词法单元被传递给语法分析阶段

• position是一个词素，被映射成词法单元<id, 1>，其中id是表示标识符(identifier)的抽象符号，而1指向符号表中position对应的条目
• 一个标识符对应的符号条目存放在该标识符有关的信息，比如它的名字和类型
• 赋值符号 = 是一个词素，被映射成词法单元< = >，这个词法单元不需要属性值，省略了第二个分量
• 也可以使用assign这样的抽象符号作为词法单元的名字，为了标记上的方便，选择使用词素本身作为抽象符号的名字
• initial 是一个词素，被映射成此法单元 <id, 2>，其中2指向对应的符号条目
• + 是一个词素，被映射成词法单元 <+>
• rate是一个词素，被映射成词法单元<id, 3>，其中3指向rate对应的符号表条目
• * 是一个词素，被映射成词法单元<*>
• 60是一个词素，被映射成词法单元<60>
• 分隔词素的空格会被词法分析器忽略掉

经过词法分析后，赋值语句表示成如下的词法单元序列

2. 语法分析

• 编译器的第2个步骤称为语法分析（syntax analysis）或解析（parsing）
• 语法分析器由词法分析器生成的各个词法单元的第一个分量来创建树形的中间表示
• 该中间表示给出了词法分析产生的词法单元流的语法结构
• 一个常用的表示方法是 语法树（syntax tree），树中的每个内部结点表示一个运算，而该结点的子结点表示该运算的分量
• 编译器的后续步骤使用这个语法结构来帮助分析源程序，生成目标程序

以上面的语法树为例

• 如图1-7的这棵语法树，有一个标号为 * 的内部结点，<id, 3>是它的左子节点，整数60是它的右子结点，<id, 3>表示标识符rate
• * 结点指明了必须把rate的值与60相乘，标号为 + 的结点表明必须把相乘的结果和 initial 的值相加
• 这棵树根节点标号为 = ，它表明我们必须把相加的结果存储到标识符 position 对应的位置
• 该运算与运算顺序和通常的算术规则相同，即乘法的优先级高于加法，乘法应该在加法前计算

3.语义分析（类型检查是一个重要部分）

• 语法分析器（semantic analyzer）使用语法树和符号表中的信息来检查源程序是否和语言定义的定义的语义一致
• 它同时也收集类型信息，并把这些信息存放在语法树或符号表中，以便在随后的中间代码生成过程中使用
• 语法分析的一个重要部分是类型检查（type checking），编译器检查每个运算符是否具有匹配的运算分量
• 比如，很多程序设计语言的定义要求一个数组的下标必须是整数，若用一个浮点数作为数组下标，编译器必须报告错误
• 自动类型转换，比如，一个二元算术运算符可以应用于一对整数或者一对浮点数，若这个运算应用于一个浮点和一个整数，那么编译器可以把整数转换成为一个浮点数

以上面的语法树为例

• 如图1-7现实了一个这样的自动类型转换，假设 position、initial 和 rate已经被声明为浮点数类型，而词素60本身形成一个整数
• 检查发现运算符 * 被用于一个浮点数rate 和 一个整数 60，这种情况下，这个整数可以转换成为一个浮点数
• 语义分析器输出中有一个关于运算符 inttofloat 的额外结点，inttofloat明确地把它的整数参数转换为一个浮点数

4.中间的代码生成

• 在把一个源程序翻译成目标代码的过程中，一个编译器可能构造出一个或多个中间表示
• 这些中间表示可以有多种形式，语法树是一种中间表示形式，它们通常在语法分析和语义分析中使用
• 在源程序的语法分析和语义分析完成之后，很多编译器生成一个明确的低级的或类机器语言的中间表示
• 我们可以把这个表示看作是某个抽象机器的程序
• 该中间表示应该具有重要的性质：它易于生成，且能够轻松地翻译为目标机器上的语言

5.代码优化

• 机器无关的代码优化步骤试图改进中间代码，以便生成更好的目标代码
• 通常意味着更快，但是也可能会有其他目标，如更短的或能耗更低的目标代码
• 它由语义分析器得到的树形中间表示中的每个运算符都使用一个指令
• 使用一个简单的中间代码生成算法，然后进行代码优化步骤是生成优质目标代码的一个合理方法
• 不同的编译器所作的代码优化工作量相差很大，那些优化工作做得最多的编译器，"优化编译器"，会在优化结点花相当多的时间

6.代码生成

• 代码生成器以源程序的中间表示形式作为输入，并把它映射到目标语言，如果目标语言是机器代码，那么就必须为程序使用的每个变量选择寄存器或内存位置
• 中间指令被翻译成能够完成相同任务的机器指令序列，代码生成的一个至关重要的方面是合理分配寄存器以存放变量的值

7.符号表管理

• 编译器的重要功能之一是记录源程序中使用的变量的名字，并收集和每个名字有关的信息
• 这些属性可以提供一个名字的存储分配、它的类型、作用域等信息
• 对于过程名字，这些信息包括：它的参数数量和类型、每个参数的传递方法以及返回类型

8.将多个步骤组合成趟

• 在一个特定的实现中，多个步骤的活动可以被组合一趟（pass）
• 每趟读入一个输入文件并产生一个输出文件
• 比如，前端步骤中的词法分析、语法分析、语义分析，以及中间代码生成可以被组合在一起成为一趟
• 代码优化可以作为一个可选的趟，然后可以有一个为特定目标机生成代码的后端趟

9.编译器构造工具

1. 语法分析器的生成器，根据语法描述自动生成语法分析器
2. 扫描器的生成器，根据一个语言的语法单元的正则表达式描述生成词法分析器
3. 语法制导的翻译引擎，生成一组用于遍历分析树并生成中间代码的例程
4. 代码生成器的生成器，依据一组关于如何把中间语言的每个运算翻译成为目标机上的机器语言规则，生成一个代码生成器
5. 数据流分析引擎，可以帮助收集数据流信息，程序中的值如何从程序的一部分传递到另一部分，数据流分析是代码优化的一个重要部分
6. 编译构造工具集，提供了可用于构造编译器的不同阶段的历程