解释器与编译器

Interpreter & Compiler.

这一节可以说是整套系列课程中含金量最高的一部分，学习的时候甚至能感受到获取知识的快感……！

• 一方面，在我们已经建立起对 ML 与 Racket 相当认识的基础之上，这一节由浅入深的展示了 static typing system 与 dynamic typing system 之间的区别与联系。
• 另一方面，本节的作业是用 Racket 写一个 MUPL (made-up programming language) 的解释器。

We can describe a typical workflow for a language implementation as follows.

• We take a string holding the concrete syntax of a program in the language. Typically this string would be the contents of one or more files.
• The parser (解析器，语法分析器) gives errors if this string is not syntactically well-formed. (no misused keywords, misplaced parentheses, etc.)
• If there are no such errors, the parser produces a tree that represents the program. This is called abstract-syntax tree (抽象语法树), or AST for short.
• If our language includes type-checking rules, the type-checker will use this AST to either produce error messages or not.

解析器将代码解析为 AST；这是源代码语言结构的一种树形抽象表示，树上的每一个节点代表源代码中的一种结构。若语言有类型检查规则，类型检查器将对 AST 进行类型检查。若通过检查，AST 将被进一步处理。

There are basically two approaches to this rest-of-the-implementation for implementing some programming language B, or sometimes of the mix.

• interpreter (解释器)：我们用另一种语言 A 编写语言 B 的解释器。解释器读入 B 语言程序的 AST 并生成结果。更好的名字 (但并非学术共识)：executor for B 或 evaluator for B.
• compiler (编译器)：我们用另一种语言 A 编写语言 B 的编译器。编译器读入 B 语言程序的 AST 并生成一段与其完全等价的 C 语言 (not necessarily the language C) 程序，再利用某些已有的 C 语言实现 (pre-existing implementation for C) 生成结果。更好的名字 (但并非学术共识)：translator for B.

无论采用解释器还是编译器，我们把语言 A 称之为 metalanguage (元语言)。For compilation, 我们把语言 B 称为 source language (源语言)，语言 C 称为 target language (目标语言)。

采用编译器或解释器是语言实现的两种方式，与语言本身无关。我们不能将使用编译器或解释器当作语言本身的 feature。

我们常说的所谓编译型语言 (compiled languages) 与解释型语言 (interpreted languages) 其实是毫无道理的：这种分类方法的出现有着很复杂的历史原因，例如 C 语言长期以来都是采用编译器实现，函数式语言通常采用解释器实现。(因此 C 语言常被称作编译型语言，而函数式语言常被称作解释型语言)。

但这并不代表我们不能编写 C 语言的解释器，或是编写函数式语言的编译器 (事实上，SML/NJ 就采用了部分编译器实现)：无论采用哪一种实现方式，都与源语言本身无关。