编译器与解释器

• 编译器：（相当于一次性翻译完）
  程序设计语言是向人以及计算机描述计算过程的记号。但是，在一个程序可以运行之前，它首先需要被翻译成一种能够被计算机执行的形式。完成这项翻译工作的软件系统成为编译器(Compiler)。
  简单地说，一个编译器就是一个程序，它可以阅读以某一种语言（源语言）编写的程序，并把程序翻译成为一个等价的、用另一种语言（目标语言）编写的程序。
  编译器的重要任务之一是报告它在翻译过程中发现的源程序中的错误。
  如果目标程序是一个可执行的机器语言程序，那么它就可以被用户调用，处理输入并产生输出。

• 解释器：（相当于同声传译）
  解释器(Interpreter)是另一种常见的语言处理器。它并不通过翻译的方式生成目标程序。从用户的角度看，解释器直接利用用户提供的输入执行源程序中指定的操作。

在把用户输入映射成为输出的过程中，由一个编译器产生的机器语言目标程序通常比一个解释器快很多。然而，解释器的错误诊断效果通常比编译器更好，因为它逐个语句地执行源程序。

语言处理过程

如上图所示，除了编译器之外，创建一个可执行的目标程序还需要一些其他程序。

1. 一个源程序可能被分割成为多个模块，并存放于独立的文件中，把源文件聚合在一起的任务有时会由一个被称为预处理器(Preprocessor)的程序独立完成。预处理器还负责把那些称为宏的缩写形式转换为源语言的语句、删除注释等。
2. 然后，将经过预处理的源程序作为输入传递给一个编译器(Compiler)。编译器可能产生生一个汇编语言程序作为其输出，因为汇编语言比较容易输出和调试。
3. 接着，这个汇编语言程序由称为汇编器(Assembler)的程序进行处理，并生成可重定位的机器代码。
4. 大型程序经常被分成多个部分进行编译，因此，可重定位的机器代码有必要和其他可重定位的目标文件以及库文件连接到一起，形成真正在机器上运行的代码。一个文件的代码可能指向另一个文件中的位置，而链接器(Linker)能够解决外部内存地址的问题。
5. 最后加载器(Loader)把所有的可执行目标文件放到内存中执行。

语言处理实例

由上面我们可以了解到语言处理的整个过程，那么放到实际的例子当中是怎么处理的呢？
下面我们以C语言打印Hello,World!为例子。

预处理→编译→汇编→链接

1. 预处理阶段(.c→.i)：编译器将C程序的头文件编译进来，还有宏的替换、删除注释等。

   科普：头文件作为一种包含功能函数、数据接口声明的载体文件，主要用于保存程序的声明，而定义文件用于保存程序的实现。

2. 编译(.i→.s)：转换为汇编语言文件：这个阶段编译器主要做词法分析、语法分析、语义分析等，在检查无错误后，把代码翻译成汇编语言。
3. 汇编阶段(.s→.o)得到机器语言：汇编器将hello.s翻译成机器语言保存在hello.o中（二进制文本形式）。

4. 链接阶段(.s→.exe)：printf函数存在于一个名为printf.o的单独预编译目标文件中。必须得将其并入到hello.o的程序中，链接器就是负责处理这两个的并入，结果得到hello.exe文件，他就是一个可执行的目标文件。

编译器编译的过程

我们把编译器看作一个黑盒子，它能够把源程序映射为在语义上等价的目标程序。如果把黑盒子稍微打开一点，我们就会看到这个映射过程由两个部分组成：前端部分和后端部分。

• 分析(analysis)部分：通常被称为编译器的前端(front end)，它把源程序分解成为多个组成要素，并在这些要素之上加上语法结构。然后，它使用这个结构来创建该源程序的一个中间表示。如果分析部分检查出源程序没有按照正确的语法构成，或者语义上不一致，它就必须提供有用的信息，使得用户可以按此进行改正。分析部分还会收集有关源程序的信息，并把信息存放在一个成为符号表(symbol table)的数据结构中。符号表将和中间表示形式一起传送给综合部分。
  

• 综合(synthesis)部分：通常被称为编译器的后端(back end)，它根据中间表示和符号表中的信息来构造用户期待的目标程序。
  • 词法分析器：（也称为扫描器）词法分析是编译过程的基础，任务是扫描源程序，根据语言的词法规则分解和识别出每个单词，并把单词翻译成相应的机内表示。在识别单词的过程中同时也做词法检查。
  • 语法分析器：（有时简称为分析器）语法分析是在词法分析的基础上进行的。任务是根据语言的语法规则把单词符号流分解成格内语法单位，如 表达式、语句等。通过语法分析确定整个输入符号流是否构成一个语法正确的程序。
  • 语义分析器：任务是对源程序进行语义检查，其目的是保证标识符和常数的正常使用，把必要的信息收集保存到符号表或中间代码程序中，并进行相应的处理。
  • 中间代码生成器：必不可少的阶段，任务是在语法分析和语义分析基础上把语法成分的语义对其继续翻译，翻译的结果是某种中间代码形式，这种中间代码的结果简单，接近计算机的指令形式，能够很容易被翻泽成计算机指令，常用的中间代码有三元式、四元式和逆波兰式。
  • 代码优化器：对程序代码进行等价（即 不改变程字的运行中间表示形式结果）变换。程序代码可以是中间代码（如 四元式代码），也可以是目标代码。等价的含义是使得交换后的代码运行结果与变换前代码运行结果相同，优化的含义是使最终生成的目标代码短（运行时间更知、占用空间更小），时空效率优化。原则上，优化可以在编译的各个阶段进行，但最主要的一类是对中间代码进行优化，这类优化不依赖于具体的计算机。
  • 目标代码生成器：将中间代码或优化之后的中间代码转换为等价的目标代码，即 机器指令或汇编语言。由中间代码很容易生成目标程序（地址指令序列），这部分工作与机器关系密切，所以要根据机器进行。在做这部分工作时（要注意充分利用累加器），也可以进行优化处理。

  • 表格管理：编译过程中源程序的各种信息被保留在种种不同的表格，编译各阶段的工作都涉及到构造、查找、或更新有关的表格。编译程序的公共辅助部分，对源程序中的各种量进行管理，登记在相应的表格。编译程序处理时通过查表得到所需的信息。

    还记得Debug调试的时候观察变量值的变化的那个表格吗？

  • 出错处理：如果编译过程中发现源程序有错误，编译程序应报告错误的性质和错误的发生的地点，并且将错误所造成的影响限制在尽可能小的范围内，使得源程序的其余部分能继续被编译下去，有些编译程序还能自动纠正错误，这些工作由错误处理程序完成。需要注意的是，一般编译器只做语法检查和最简单的语义检查，而不检查程序的逻辑。

词法分析器

词法分析器的任务是将程序的字符流转换到记号流。
字符流:被编译的语言例如C、JAVA、ASCII、Inicode.
记号流:编译器内部定义的数据结构，编码所识别出的词法单元。

例如读入一个程序语句:

if (x>0)
    y="NEMO";   //词法分析器设置成自动忽略空格，以下空格用\x20表示

词法分析器依次读入：i、f、\x20. (、x、)、0、)、\n、y、=、”NEMO”、;。
进行分析后得到:

IF LPARE IDENT(x) GT INT (0) RPAREN
    IDENT(y) ASSIGN STRING ( "NEMO" ) SEMICOLON EOF

我们对这些“词语记号“进行数据结构定义:

enum type {IF. LPAREN. ID. INLIT,...}
struct token {
enum type k;
char *lexeme;   //单词
};  //例如if (x>0)， 我们就可以编程为: token{k= IF, lexeme =0};
token{k= LPAREN. lexeme=0}; token{k = ID, lexeme= “x”};

目前至少有两种实现方案:

• 手工编码实现法（相对复杂，且容易出错目前非常流行的GCC、LLVM 等）；
• 词法分析器的生成器（自动的，可以快速原型、代码量较少，但是控制细节难）

语法分析器

语法分析器的主要任务是对词法分析的输出结果记号流单词序列进行分析，识别合法的语法单元并将其转换输出为下一阶段可以识别的语法树。

实现方法:

• 手工方式:递归下降分析器
• 使用语法分析器的自动生成著: LL(1)、 LR(1)

两种方式在实际的编译器中都有广泛的应用，其中自动的方式更适合快速对系统进行原型开发，手工的方式更适台对系统进行调优。

语义分析器

语法树（分析树）是句子结构的图形表示，它代表了句子的推导结果，有利于理解句子语法结构的层次。简单来说，语法树就是按照某一规则进行推导时所形成的树。和推导所用的顺序无关（最左、最右、其他）
特点：

• 树中每个内部节点代表非终结符
• 每个叶子节点代表终结符
• 每一步推导代表如何从双亲结点生成它的直接孩子节点

二义性：若对于一个文法的某一句子存在两颗不同的语法树，则该文法是二义性文法；否则是无二义性文法。（包含二义性的句子）
从编译器角度，二义性文法存在的问题：
同一个程序会有不同的含义，因此程序运行的结果不是唯一的。
解决方法：文法的重写