编译原理

• 什么是编译器，解释器？

一个程序在运行之前，需要翻译成一种能被计算机执行的形式，完成这项翻译工作的软件系统称为编译器。

源程序被分割成多个模块，需要一个预处理的程序聚合源程序，包括把宏定义转为源语言语句。

经过预处理的源程序传给编译程序，生成汇编语言程序。

汇编语言程序由汇编器处理，生成可重定位的机器代码。

大型程序分割成多个部分编译，可重定位的机器代码有必要和其它可重定位的机器代码以及库文件连接，形成真正的机器代码。链接器解决外部内存地址问题。

加载器把所有可执行目标文件放到内存运行。

解释器并不通过翻译的方式产生目标程序，从用户角度看，直接利用用户提供的输入执行源程序的操作。

由一个编译器产生机器目标代码比解释器快很多，但是解释器的错误诊断比编译器更好。

• 编译过程的具体步骤？

我们把编译器当做一个黑盒子，把源程序映射成一个语义上等价的目标程序，映射过程由两部分组成，分析部分和综合部分。

分析就是把源程序分解为多个组成要素，在这些要素之上加入语法结构，使用这些结构创建源程序的中间表示。分析部分还会收集源程序信息，存放于符号表这种数据结构，符号表和中间表示一起传送给综合部分。

综合就是利用分析到的中间表示和符号表信息构造用户期待的目标程序。

词法分析读入组成源程序的字符流，并组成有意义的词素序列。词法分析器产生如下形式的词法单元(token)作为输出：(token-name,attribute-value)

源程序包含 position=inital+60*rate赋值语句。词法分析有下列表示。

position是一个词素，映射成词法单元<id,1>，id是标识符的抽象符号，1符号表中position对应的条目。剩余在符号表中类似表示。

语法分析。使用词法分析器生成的各个词法单元的第一个分量创建树形中间表示。给出了词法分析产生词法单元流的语法结构。

语义分析。使用语法树和符号表中的信息检查源程序是否和语言定义的语义一致。同时也收集类型信息，存放于语法树或符号表中，以便在中间代码生成过程使用。

语义分析很重要的部分是类型检查，检查每个运算符是否有匹配的运算分量。

中间代码生成。在翻译过程中，一个编译器可以构造出多个中间表示，这些中间表示可以有多种形式。

语法分析和语义分析后，编译器产生明确的低级的或类机器语言的中间表示，看做某个抽象机器的程序，这种程序易于生成，轻松翻译成目标机器上的语言。

也可以考虑一种类似于汇编指令序列的三地址代码的中间表示。

代码优化。试图改进中间代码，得到更好的目标代码。更好意味着更快，更短或能耗更低的目标代码。

代码生成。以源程序的中间表示作为输入，映射到目标语言。如果目标语言是机器代码，那就要为变量选择寄存器或内存地址。然后，中间指令翻译成完成相同任务的机器指令，代码生成重要的方面是合理分配寄存器存放变量。

符号表管理。编译器重要的功能就是记录源程序中的变量名，并收集属性。提供对名字的存储分配，类型，作用域等信息。对于过程名字，包括参数变量和类型，参数传递方法和返回值类型。

符号表管理为每个变量名提供一个记录条目，记录各名字的属性。这种数据结构允许编译器迅速查到每个名字的记录，并快速存放或获取记录数据。

多个步骤组合成趟。前面的各步骤就是一个编译器的逻辑组织方式。多个步骤的活动被称为一趟。前面的词法分析，语法分析，语义分析，中间代码生成组合在一起可以成为一趟。代码优化作为一个可选的趟，特定目标机生成代码的后端趟。