90分钟实现一门编程语言——极简解释器教程

关键字

解释器, C#, Scheme, 函数式编程

关于

本文介绍了如何使用C#实现一个简化但全功能的Scheme方言——iScheme及其解释器，通过从零开始逐步构建，展示了编程语言/解释器的工作原理。

作者

Lucidaa.k.aLuc

如果你是通过移动设备阅读本教程，或者认为本文的代码字体太小的，请使用该链接以获得更好的可读性（博客园的markdown解析器实在诡异，这里就不多吐槽了）。

提示

如果你对下面的内容感兴趣：

• 实现基本的词法分析，语法分析并生成抽象语法树。
• 实现嵌套作用域和函数调用。
• 解释器的基本原理。
• 以及一些C#编程技巧。

那么请继续阅读。

如果你对以下内容感兴趣：

• 高级的词法/语法分析技术。
• 类型推导/分析。
• 目标代码优化。

本文则过于初级，你可以跳过本文，但欢迎指出本文的错误 :-)

代码样例

代码示例

public static int Add(int a, int b) {    return a + b;}>> Add(3, 4)>> 7>> Add(5, 5)>> 10

这段代码定义了Add函数，接下来的>>符号表示对Add(3, 4)进行求值，再下一行的>> 7表示上一行的求值结果，不同的求值用换行分开。可以把这里的>>理解成控制台提示符（即Terminal中的PS）。

什么是解释器

解释器（InterPReter）是一种程序，能够读入程序并直接输出结果，如上图。相对于编译器（Compiler），解释器并不会生成目标机器代码，而是直接运行源程序，简单来说：

解释器是运行程序的程序。

计算器就是一个典型的解释器，我们把数学公式（源程序）给它，它通过运行它内部的"解释器"给我们答案。

iScheme编程语言

iScheme是什么？

• Scheme语言的一个极简子集。
• 虽然小，但变量，算术|比较|逻辑运算，列表，函数和递归这些编程语言元素一应俱全。
• 非常非常慢——可以说它只是为演示本文的概念而存在。

OK，那么Scheme是什么？

• 一种函数式程序设计语言。
• 一种Lisp方言。
• 麻省理工学院程序设计入门课程使用的语言（参见MIT 6.001和《计算机程序的构造与解释》）。

• 使用波兰表达式（Polish Notation）。
• 更多的介绍参见Scheme编程语言。

以计算阶乘为例：

C#版阶乘

public static int Factorial(int n) {    if (n == 1) {        return 1;    } else {        return n * Factorial(n - 1);    }}

iScheme版阶乘

(def factorial (lambda (n) (    if (= n 1)       1       (* n (factorial (- n 1))))))

数值类型

由于iScheme只是一个用于演示的语言，所以目前只提供对整数的支持。iScheme使用C#的Int64类型作为其内部的数值表示方法。

定义变量

iScheme使用def关键字定义变量

>> (def a 3)>> 3>> a>> 3

算术|逻辑|比较操作

与常见的编程语言（C#, java, C++, C）不同，Scheme使用波兰表达式，即前缀表示法。例如：

C#中的算术|逻辑|比较操作

// Arithmetic opsa + b * ca / (b + c + d)// Logical ops(cond1 && cond2) || cond3// Comparing opsa == b1 < a && a < 3

对应的iScheme代码

; Arithmetic ops(+ a (* b c))(/ a (+ b c d)); Logical ops(or (and cond1 cond2) cond3); Comparing ops(= a b)(< 1 a 3)

需要注意的几点：

1. iScheme中的操作符可以接受不止两个参数——这在一定程度上控制了括号的数量。
2. iScheme逻辑操作使用and,or和not代替了常见的&&,||和!——这在一定程度上增强了程序的可读性。

顺序语句

iScheme使用begin关键字标识顺序语句，并以最后一条语句的值作为返回结果。以求两个数的平均值为例：

C#的顺序语句

int a = 3;int b = 5;int c = (a + b) / 2;

iScheme的顺序语句

(def c (begin    (def a 3)    (def b 5)    (/ (+ a b) 2)))

控制流操作

iScheme中的控制流操作只包含if。

if语句示例

>> (define a (if (> 3 2) 1 2))>> 1>> a>> 1

列表类型

iScheme使用list关键字定义列表，并提供first关键字获取列表的第一个元素；提供rest关键字获取列表除第一个元素外的元素。

iScheme的列表示例

>> (define alist (list 1 2 3 4))>> (list 1 2 3 4)>> (first alist)>> 1>> (rest alist)>> (2 3 4)

定义函数

iScheme使用func关键字定义函数：

iScheme的函数定义

(def square (func (x) (* x x)))(def sum_square (func (a b) (+ (square a) (square b))))

对应的C#代码

public static int Square (int x) {    return x * x;}public static int SumSquare(int a, int b) {    return Square(a) + Square(b);}

递归

由于iScheme中没有for或while这种命令式语言（Imperative Programming Language）的循环结构，递归成了重复操作的唯一选择。

以计算最大公约数为例：

iScheme计算最大公约数

(def gcd (func (a b)    (if (= b 0)        a        (func (b (% a b))))))

对应的C#代码

public static int GCD (int a, int b) {    if (b == 0) {        return a;    } else {        return GCD(b, a % b);    }}

高阶函数

和Scheme一样，函数在iScheme中是头等对象，这意味着：

• 可以定义一个变量为函数。
• 函数可以接受一个函数作为参数。
• 函数返回一个函数。

iScheme的高阶函数示例

; Defines a multiply function.(def mul (func (a b) (* a b))); Defines a list map function.(def map (func (f alist)    (if (empty? alist)        (list )        (append (list (f (first alist))) (map f (rest alist)))        ))); Doubles a list using map and mul.>> (map (mul 2) (list 1 2 3))>> (list 2 4 6)

小结

对iScheme的介绍就到这里——事实上这就是iScheme的所有元素，会不会太简单了？ -_-

接下来进入正题——从头开始构造iScheme的解释程序。

解释器构造

iScheme解释器主要分为两部分，解析（Parse）和求值（Evaluation）：

• 解析（Parse）：解析源程序，并生成解释器可以理解的中间（Intermediate）结构。这部分包含词法分析，语法分析，语义分析，生成语法树。
• 求值（Evaluation）：执行解析阶段得到的中介结构然后得到运行结果。这部分包含作用域，类型系统设计和语法树遍历。

词法分析

词法分析负责把源程序解析成一个个词法单元（Lex），以便之后的处理。

iScheme的词法分析极其简单——由于iScheme的词法元素只包含括号，空白，数字和变量名，因此C#自带的String#Split就足够。

iScheme的词法分析及测试

public static String[] Tokenize(String text) {    String[] tokens = text.Replace("(", " ( ").Replace(")", " ) ").Split(" /t/r/n".ToArray(), StringSplitOptions.RemoveEmptyEntries);    return tokens;}// Extends String.Join for a smooth API.public static String Join(this String separator, IEnumerable<Object> values) {    return String.Join(separator, values);}// Displays the lexes in a readable form.public static String PrettyPrint(String[] lexes) {    return "[" + ", ".Join(lexes.Select(s => "'" + s + "'") + "]";}// Some tests>> PrettyPrint(Tokenize("a"))>> ['a']>> PrettyPrint(Tokenize("(def a 3)"))>> ['(', 'def', 'a', '3', ')']>> PrettyPrint(Tokenize("(begin (def a 3) (* a a))"))>> ['begin', '(', 'def', 'a', '3', ')', '(', '*', 'a', 'a', ')', ')']

注意

• 个人不喜欢String.Join这个静态方法，所以这里使用C#的扩展方法（Extension Methods）对String类型做了一个扩展。
• 相对于LINQ Syntax，我个人更喜欢LINQ Extension Methods，接下来的代码也都会是这种风格。
• 不要以为词法分析都是这么离谱般简单！vczh的词法分析教程给出了一个完整编程语言的词法分析教程。

语法树生成

得到了词素之后，接下来就是进行语法分析。不过由于Lisp类语言的程序即是语法树，所以语法分析可以直接跳过。

以下面的程序为例：

程序即语法树

;(def x (if (> a 1) a 1)); 换一个角度看的话：(    def    x    (        if        (            >            a            1        )        a        1    ))

更加直观的图片：

这使得抽象语法树（Abstract Syntax Tree）的构建变得极其简单（无需考虑操作符优先级等问题），我们使用SExpression类型定义iScheme的语法树（事实上S Expression也是Lisp表达式的名字）。

抽象语法树的定义

public class SExpression {    public String Value { get; private set; }    public List<SExpression> Children { get; private set; }    public SExpression Parent { get; private set; }    public SExpression(String value, SExpression parent) {        this.Value = value;        this.Children = new List<SExpression>();        this.Parent = parent;    }    public override String ToString() {        if (this.Value == "(") {            return "(" + " ".Join(Children) + ")";        } else {            return this.Value;        }    }}

然后用下面的步骤构建语法树：

1. 碰到左括号，创建一个新的节点到当前节点（current），然后重设当前节点。
2. 碰到右括号，回退到当前节点的父节点。
3. 否则把为当前词素创建节点，添加到当前节点中。

抽象语法树的构建过程

public static SExpression ParseAsIScheme(this String code) {    SExpression program = new SExpression(value: "", parent: null);    SExpression current = program;    foreach (var lex in Tokenize(code)) {        if (lex == "(") {            SExpression newNode = new SExpr