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）。

什么是解釋器

解釋器（Inter

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