编译器结构

介绍

作为系统软体，编译器的设计与实现是非常複杂的。对于一个相对複杂的系统，通常的解决方法是将系统分解成若干较小且便于处理的小系统，分别实现后将其组织成一个完整的複杂系统，这就是"分治法"的思想。实际上，计算机科学家正是运用这种思想来设计与实现编译器、作业系统、网路通信协定等複杂的大型系统软体的。

工作过程

编译器的翻译过程是非常複杂的，但就过程本身而言，与自然语言翻译却有不少相近之处。例如，把英语句子翻译为汉语句子时，通常需要经过下列几个步骤：

1）对句子中的每个英语单词进行识别。

2）对句子的语法结构进行分析。

3）分析句子的基本含义，进行初步翻译。

4）修饰译文，使之更加符合汉语的表达习惯。

5）将译文整理书写记录。

编译器的工作过程与自然语言翻译过程比较类似，亦可划分为五个阶段：词法分析、语法分析、语义分析与中间表示生成、代码最佳化、代码生成。

1．词法分析

词法分析的任务就是对输入的源程式进行扫描分析，识别出一个个的单词（Token），并进行归类。这里的"单词"可以理解为源程式中具有独立含义的不可分割的字元序列，与自然语言中的单词概念有一定区别。一般而言，根据程式设计语言的特点，单词可以分为五类：关键字、标识符、常量、运算符、界符。以一个C语言的条件语句为例：

if(aa&&10==0)aa=100;

词法分析的结果是识别出如下的单词符号：

关键字

界符

标识符

运算符

常量

运算符

if

(

aa

&&

10

==

常量

界符

标识符

运算符

常量

界符

0

)

aa

=

100

;

2．语法分析

语法分析的任务就是在词法分析的基础上，根据程式设计语言的语法规则（文法），把单词流分解成各类语法单位（语法範畴），如"语句"、"表达式"等。理论上讲，通过语法分析，编译器可以準确无误地判断输入源程式是否满足语言的语法规则。例如，语法分析可以判断如下语句是错误的。

ifaa%%10==9aa=100; for(i<0)i++;

不过，实际情况并非完全如此，这主要与文法定义的细化程度有直接的关係。当程式设计语言的设计人员把文法定义得比较宽泛时，也就意味着依据此语法规则，编译器不能在语法分析阶段发现所有的语法错误，只能将错误遗留给后续阶段处理。表面上看，语法分析并不像词法分析有直观的输出结果，而仅仅完成了输入源程式的语法判定工作。实际上，语法分析是编译器前面三个阶段（合称为前端）的主控模组。

3．语义分析与中间表示生成

语义分析与中间表示生成的任务就是在语法分析的基础上，分析各语法单位的含义，并进行初步的翻译，即生成中间表示形式。有时，这两个任务是密不可分的，故通常将其合併为一个阶段讨论。语义分析主要是检查输入源程式的语义是否正确，例如，变数使用前是否定义、同一作用域内变数是否重名等。中间表示生成将根据输入源程式的语义生成语义等价中间表示形式。中间表示是一种由编译器设计人员定义、使用的形式，对于用户是完全透明的。中间表示形式的定义是值得深入研究的，因为它直接决定了编译器前、后端的设计複杂度，也决定了编译器前端与目标语言之间的耦合程度。中间表示的形式也非常多，包括四元组、三元组、语法树、DAG图等，并不一定是读者理解的通常的代码形式。例如，lcc的中间表示就是一种DAG的形式。当然，近似于彙编指令形式的四元组、三元组可能是最为常见的中间表示形式。