编译器与程序设计语言

编译器

编译器是一个 程序，它可以阅读以某一 源语言 编写的程序，并把该程序翻译成一个 等价的、用 目标语言 编写的程序; 解释器是另一种语言处理器，它直接利用用户提供的输入执行源程序中指定的操作。

编译器产生的机器语言目标程序通常比一个解释器 快 得多，但是解释器的 错误诊断效果 比编译器更好，因为解释器是逐个语句地执行源程序。

基本组成

编译器是由 预处理器 (preprocessor)、编译器 (compiler)、汇编器 (assembler)、链接器 (linker) 这几大主要部分组成，最后生成一个可执行程序 (executable)。

• 预处理器：主要负责文本替换或巨集展开
• 编译器：可能产生一个汇编语言的中间代码作为其输出，因为汇编语言比较容易 输出 和 调试
• 汇编器：将编译器产生的中间结果生成 可重新定位的 机器代码
• 链接器：将一个或多个由编译器或汇编器生成的目标文件外加库，链接为一个可执行文件

现代编译器中，基本可以分步骤调用编译器的各个部分，生成所需要的阶段输出，以 gcc 和 clang 为例

• 预处理 (-E)：输出文件经过预处理器生成的源代码，一般以 .i 作为文件扩展名
• 编译 (-S)：将源代码或预处理文件编译生成汇编代码，汇编代码后缀名 .s
• 汇编 (-c)：将源代码或之前步骤生成的中间代码汇编生成可重新定位的机器码，文件后缀名为 .o
• 链接：将源文件或之前步骤生成的中间代码链接生成可执行程序

结构

编译器由两部分组成，分析 部分和 综合 部分

• 分析：将源程序分解成为多个组成元素，并在要素之上加上语法结构。分析部分被称为编译器的 前端
• 综合：根据中间表示和符号表中的信息来构造用户期待的目标程序。综合部分被称为编译器的 后端

现代编译器，比如 LLVM 以设计精良的 IR 作为中端输出，语言只需要实现前端和中端，最终由 LLVM 实现 IR 到二进制的转换，可以做到只优化 LLVM 就完成对其上所有语言的优化。

词法分析 (lexical analysis)

词法分析器读入组成源程序的字符流，并将它们组成成为有意义的 词素 (lexeme) 的序列。对于每个词素，词法分析器产生如下形式的 词法单元 (token) 作为输出 <token-name，attribute-value>

语法分析 (syntax analysis)

语法分析器使用由词法分析器生成的各个词法单元的第一个分量来创建树形的中间表示，该中间表示给出了词法分析产生的词法单元流的语法结构。常用表示方法为 语法树 (syntax tree)，树中的每个内部接点表示一个运算，而该结点的子结点表示该运算的分量

语义分析 (semantic analysis)

使用语法树和符号表中的信息来检查源程序是否和语言定义的语义一致。同时也会收集类型信息，并把这些信息存放在语法树或符号表中

中间代码生成

编译器一般在语法分析、语义分析结束之后，会生成一个明确的低级的或类机器语言的中间表示，该中间表示应该 易于生成、且可以被 轻松翻译 为目标机器语言

代码优化

机器无关的代码优化步骤试图改进中间代码，以便生成 更好 的目标代码

代码生成

以源程序的中间表示形式作为输入，并把它映射到目标语言，代码生成必须要 合理分配寄存器

符号表管理

记录源程序中使用的变量名称，并收集和每个名字的各种属性有关的信息，这些属性一般包含 存储分配、类型、作用域 等

构造工具

除通用软件开发工具外，编译器的实现一般需要专业的工具来实现，这些专用工具使用专用的语言来 描述 和 实现 特定的组件，这些生成器会隐藏相当复杂的生成算法细节，并生成易于与其他部分集成的组件

语法分析器的生成器

可以根据一个程序设计语言的语法描述自动生成语法分析器

扫描器的生成器

可以根据一个语言的语法单元的正则表达式描述生成词法分析器

语法执导的翻译引擎

可以生成一组用于遍历分析树并生成中间代码的程序

代码生成器的生成器

根据一组关于如何把中间语言的每个运算翻译成为目标机上的机器语言的规则，生成一个代码生成器

数据流分析引擎

可以帮助收集数据流信息，即程序中的值如何从程序的一部分传递到另一部分，这是代码优化的重要部分

编译器构造工具集

用于构造编译器不同阶段的例程的完整集合

程序设计语言

20 世纪 40 年代，第一台计算机问世，它使用 01 序列组成的机器语言编程，直到现在计算机的最底层依然以这种方式运行。但这种编程速度 慢 且 枯燥，容易出错，写出的程序 难以 修改与理解。

20 世纪 50 年代早期，人们开始对助记汇编语言开发，汇编语言已开始仅是对机器语言的助记表示，后来加入了 宏指令，可以为频繁使用的机器指令序列定义带有参数的缩写。

之后，程序设计语言从汇编语言开始走向高级语言，用于科学计算的 Fortran、用于商业数据处理的 Cobol、用于符号计算的 Lisp 等等，随着时间的推移，越来越多带着新特性的高级语言被开发出来，它们更加 简单、自然、强大。

根据时间与应用关系，龙书将程序设计语言分为了 5 代

• 第一代：机器语言
• 第二代：汇编语言
• 第三代：高级程序设计语言，例如 Fortran、C、C++、Java 等
• 第四代：为特定应用设计的语言，例如用于数据库查询的 SQL，用于文字排版的 Postscript
• 第五代：基于逻辑和约束的语言，例如 Prolog 和 OPS5

根据程序编程范式的不同，分为 2 种

强制式 (imperative)

又称 命令式，程序指明如何完成一个计算任务，所有强制式语言都有表示 程序状态 和 语句 的表示方法，语句可以改变程序状态，例如 C、C++等

声明式 (declarative)

程序指明需要进行哪些运算，例如 函数式程序设计语言 和 Prolog 等

环境与状态

标识符 (identifier) 是一个字符串，它通常由子母、数字和下划线组成，它被用来标记一个 实体，例如 数据对象、过程、类型 等。变量指向存储中的某一个特定位置，同一个标识符可能被多次声明 (例如在递归过程中的局部变量)，每一个这样的声明都会引入一个新的变量。所有的标识符都是名字，不过名字不一定是标识符，比如 x.y 这样的名字被称为 受限名字 (qualified name)，表示变量 x 所指向结构中的字段 y。

名字和内存 (存储) 位置的关联，以及之后和值的关联可以用两个映射来描述，这两个映射随着程序的运行而改变。环境 (environment) 是从一个名字到存储位置的映射，例如 C 语言中的右值；状态 (state) 是一个内存位置到它们值的映射，例如 C 语言中左值所对应的右值

大多数环境和状态是 动态绑定 的，一般全局变量的环境映射是静态的，编译器可以在生成目标代码的时候为其分配一个地址；常量的声明一般其状态是静态绑定的，我们看到这个语句时就能确定绑定关系，并且在程序的运行时这个绑定不能改变。

静态与动态

允许编译器静态决定某个问题时，或者说这个问题可以在 编译时 (compile time) 决定，我们称这个语言使用了 静态策略 (static policy)。一个问题只允许在 运行时 (run time) 做出决定，那么称之为 动态策略 (dynamic policy)。比如 C++中的模板计算就是静态策略，而多继承中的多态则是动态策略。

作用域 (scope) 也需要关注静态还是动态，如果仅通过阅读程序即可确定一个声明的作用域，即在编译时就可确定其作用域，那么这个语言使用 静态作用域，或者说是 词法作用域 (lexical scope)。否则，这个语言使用 动态作用域，如果使用动态作用域，在程序运行时，同一个对 x 的使用会指向 x 的几个声明之一。或者简单的说，静态作用域关注在 何处定义，动态作用域关注 何处声明 或 何处调用

1
2
3
4
5
6
7
8
9

a=1;
function foo() {
  echo $a;  # 静态作用域输出1，动态作用域输出2
}
function bar() {
  a=2;
  foo;
}
bar;

参数的传递机制

值调用 (call-by-value)

在调用过程中会对实参进行求值或拷贝，被调用过程中所有有关形式参数的计算被局限于这一过程中，实参本身不会被影响

引用调用 (call-by-reference)

在调用过程中，以实参的地址作为形参的值传递给被调用者，在使用时就会直接使用这个内存地址，因此形参被修改会影响到实参本身