摘要：計算器語言解釋器的核心是叫做的遞歸函數，它會求解樹形表達式對象。到目前為止，我們在描述求值過程中所引用的表達式樹，還是概念上的實體。解析器實際上由兩個組件組成，詞法分析器和語法分析器。標記序列由叫做的詞法分析器產生，并被叫做語法分析器使用。

來源：3.5   Interpreters for Languages with Combination
譯者：飛龍
協議：CC BY-NC-SA 4.0

運行在任何現代計算機上的軟件都以多種編程語言寫成。其中有物理語言，例如用于特定計算機的機器語言。這些語言涉及到基于獨立儲存位和原始機器指令的數據表示和控制。機器語言的程序員涉及到使用提供的硬件，為資源有限的計算構建系統和功能的高效實現。高階語言構建在機器語言之上，隱藏了表示為位集的數據，以及表示為原始指令序列的程序的細節。這些語言擁有例如過程定義的組合和抽象的手段，它們適用于組織大規模的軟件系統。

元語言抽象 -- 建立了新的語言 -- 并在所有工程設計分支中起到重要作用。它對于計算機編程尤其重要，因為我們不僅僅可以在編程中構想出新的語言，我們也能夠通過構建解釋器來實現它們。編程語言的解釋器是一個函數，它在語言的表達式上調用，執行求解表達式所需的操作。

我們現在已經開始了技術之旅，通過這種技術，編程語言可以建立在其它語言之上。我們首先會為計算器定義解釋器，它是一種受限的語言，和 Python 調用表達式具有相同的語法。我們之后會從零開始開發 Scheme 和 Logo 語言的解釋器，它們都是 Lisp 的方言，Lisp 是現在仍舊廣泛使用的第二老的語言。我們所創建的解釋器，在某種意義上，會讓我們使用 Logo 編寫完全通用的程序。為了這樣做，它會實現我們已經在這門課中開發的求值環境模型。

我們的第一種新語言叫做計算器，一種用于加減乘除的算術運算的表達式語言。計算器擁有 Python 調用表達式的語法，但是它的運算符對于所接受的參數數量更加靈活。例如，計算器運算符mul和add可接受任何數量的參數：

calc> add(1, 2, 3, 4)
10
calc> mul()
1

sub運算符擁有兩種行為：傳入一個運算符，它會對運算符取反。傳入至少兩個，它會從第一個參數中減掉剩余的參數。div運算符擁有 Python 的operator.truediv的語義，只接受兩個參數。

calc> sub(10, 1, 2, 3)
4
calc> sub(3)
-3
calc> div(15, 12)
1.25

就像 Python 中那樣，調用表達式的嵌套提供了計算器語言中的組合手段。為了精簡符號，我們使用運算符的標準符號來代替名稱：

calc> sub(100, mul(7, add(8, div(-12, -3))))
16.0
calc> -(100, *(7, +(8, /(-12, -3))))
16.0

我們會使用 Python 實現計算器解釋器。也就是說，我們會編寫 Python 程序來接受字符串作為輸入，并返回求值結果。如果輸入是符合要求的計算器表達式，結果為字符串，反之會產生合適的異常。計算器語言解釋器的核心是叫做calc_eval的遞歸函數，它會求解樹形表達式對象。

表達式樹。到目前為止，我們在描述求值過程中所引用的表達式樹，還是概念上的實體。我們從沒有顯式將表達式樹表示為程序中的數據。為了編寫解釋器，我們必須將表達式當做數據操作。在這一章中，許多我們之前介紹過的概念都會最終以代碼實現。

計算器中的基本表達式只是一個數值，類型為int或float。所有復合表達式都是調用表達式。調用表達式表示為擁有兩個屬性實例的Exp類。計算器的operator總是字符串：算數運算符的名稱或符號。operands要么是基本表達式，要么是Exp的實例本身。

>>> class Exp(object):
        """A call expression in Calculator."""
        def __init__(self, operator, operands):
            self.operator = operator
            self.operands = operands
        def __repr__(self):
            return "Exp({0}, {1})".format(repr(self.operator), repr(self.operands))
        def __str__(self):
            operand_strs = ", ".join(map(str, self.operands))
            return "{0}({1})".format(self.operator, operand_strs)

Exp實例定義了兩個字符串方法。__repr__方法返回 Python 表達式，而__str__方法返回計算器表達式。

>>> Exp("add", [1, 2])
Exp("add", [1, 2])
>>> str(Exp("add", [1, 2]))
"add(1, 2)"
>>> Exp("add", [1, Exp("mul", [2, 3, 4])])
Exp("add", [1, Exp("mul", [2, 3, 4])])
>>> str(Exp("add", [1, Exp("mul", [2, 3, 4])]))
"add(1, mul(2, 3, 4))"

最后的例子演示了Exp類如何通過包含作為operands元素的Exp的實例，來表示表達式樹中的層次結構。

求值。calc_eval函數接受表達式作為參數，并返回它的值。它根據表達式的形式為表達式分類，并且指導它的求值。對于計算器來說，表達式的兩種句法形式是數值或調用表達式，后者是Exp的實例。數值是自求值的，它們可以直接從calc_eval中返回。調用表達式需要使用函數。

調用表達式首先通過將calc_eval函數遞歸映射到操作數的列表，計算出參數列表來求值。之后，在第二個函數calc_apply中，運算符會作用于這些參數上。

計算器語言足夠簡單，我們可以輕易地在單一函數中表達每個運算符的使用邏輯。在calc_apply中，每種條件子句對應一個運算符。

>>> from operator import mul
>>> from functools import reduce
>>> def calc_apply(operator, args):
        """Apply the named operator to a list of args."""
        if operator in ("add", "+"):
            return sum(args)
        if operator in ("sub", "-"):
            if len(args) == 0:
                raise TypeError(operator + " requires at least 1 argument")
            if len(args) == 1:
                return -args[0]
            return sum(args[:1] + [-arg for arg in args[1:]])
        if operator in ("mul", "*"):
            return reduce(mul, args, 1)
        if operator in ("div", "/"):
            if len(args) != 2:
                raise TypeError(operator + " requires exactly 2 arguments")
            numer, denom = args
            return numer/denom

上面，每個語句組計算了不同運算符的結果，或者當參數錯誤時產生合適的TypeError。calc_apply函數可以直接調用，但是必須傳入值的列表作為參數，而不是運算符表達式的列表。

>>> calc_apply("+", [1, 2, 3])
6
>>> calc_apply("-", [10, 1, 2, 3])
4
>>> calc_apply("*", [])
1
>>> calc_apply("/", [40, 5])
8.0

calc_eval的作用是，執行合適的calc_apply調用，通過首先計算操作數子表達式的值，之后將它們作為參數傳入calc_apply。于是，calc_eval可以接受嵌套表達式。

>>> e = Exp("add", [2, Exp("mul", [4, 6])])
>>> str(e)
"add(2, mul(4, 6))"
>>> calc_eval(e)
26

calc_eval的結構是個類型（表達式的形式）分發的例子。第一種表達式是數值，不需要任何的額外求值步驟。通常，基本表達式不需要任何額外的求值步驟，這叫做自求值。計算器語言中唯一的自求值表達式就是數值，但是在通用語言中可能也包括字符串、布爾值，以及其它。

“讀取-求值-打印”循環。和解釋器交互的典型方式是“讀取-求值-打印”循環（REPL），它是一種交互模式，讀取表達式、對其求值，之后為用戶打印出結果。Python 交互式會話就是這種循環的例子。

REPL 的實現與所使用的解釋器無關。下面的read_eval_print_loop函數使用內建的input函數，從用戶接受一行文本作為輸入。它使用語言特定的calc_parse函數構建表達式樹。calc_parse在隨后的解析一節中定義。最后，它打印出對由calc_parse返回的表達式樹調用calc_eval的結果。

>>> def read_eval_print_loop():
        """Run a read-eval-print loop for calculator."""
        while True:
            expression_tree = calc_parse(input("calc> "))
            print(calc_eval(expression_tree))

read_eval_print_loop的這個版本包含所有交互式界面的必要組件。一個樣例會話可能像這樣：

calc> mul(1, 2, 3)
6
calc> add()
0
calc> add(2, div(4, 8))
2.5

這個循環沒有實現終端或者錯誤處理機制。我們可以通過向用戶報告錯誤來改進這個界面。我們也可以允許用戶通過發射鍵盤中斷信號（Control-C），或文件末尾信號（Control-D）來退出循環。為了實現這些改進，我們將原始的while語句組放在try語句中。第一個except子句處理了由calc_parse產生的SyntaxError異常，也處理了由calc_eval產生的TypeError和ZeroDivisionError異常。

>>> def read_eval_print_loop():
        """Run a read-eval-print loop for calculator."""
        while True:
            try:
                expression_tree = calc_parse(input("calc> "))
                print(calc_eval(expression_tree))
            except (SyntaxError, TypeError, ZeroDivisionError) as err:
                print(type(err).__name__ + ":", err)
            except (KeyboardInterrupt, EOFError):  # -D, etc.
                print("Calculation completed.")
                return

這個循環實現報告錯誤而不退出循環。發生錯誤時不退出程序，而是在錯誤消息之后重新開始循環可以讓用戶回顧他們的表達式。通過導入readline模塊，用戶甚至可以使用上箭頭或Control-P來回憶他們之前的輸入。最終的結果提供了錯誤信息報告的界面：

calc> add
SyntaxError: expected ( after add
calc> div(5)
TypeError: div requires exactly 2 arguments
calc> div(1, 0)
ZeroDivisionError: division by zero
calc> ^DCalculation completed.

在我們將解釋器推廣到計算器之外的語言時，我們會看到，read_eval_print_loop由解析函數、求值函數，和由try語句處理的異常類型參數化。除了這些修改之外，任何 REPL 都可以使用相同的結構來實現。

解析是從原始文本輸入生成表達式樹的過程。解釋這些表達式樹是求值函數的任務，但是解析器必須提供符合格式的表達式樹給求值器。解析器實際上由兩個組件組成，詞法分析器和語法分析器。首先，詞法分析器將輸入字符串拆成標記（token），它們是語言的最小語法單元，就像名稱和符號那樣。其次，語法分析器從這個標記序列中構建表達式樹。

>>> def calc_parse(line):
        """Parse a line of calculator input and return an expression tree."""
        tokens = tokenize(line)
        expression_tree = analyze(tokens)
        if len(tokens) > 0:
            raise SyntaxError("Extra token(s): " + " ".join(tokens))
        return expression_tree

標記序列由叫做tokenize的詞法分析器產生，并被叫做analyze語法分析器使用。這里，我們定義了calc_parse，它只接受符合格式的計算器表達式。一些語言的解析器為接受以換行符、分號或空格分隔的多種表達式而設計。我們在引入 Logo 語言之前會推遲實現這種復雜性。

詞法分析。用于將字符串解釋為標記序列的組件叫做分詞器（tokenizer ），或者詞法分析器。在我們的視線中，分詞器是個叫做tokenize的函數。計算器語言由包含數值、運算符名稱和運算符類型的符號（比如+）組成。這些符號總是由兩種分隔符劃分：逗號和圓括號。每個符號本身都是標記，就像每個逗號和圓括號那樣。標記可以通過向輸入字符串添加空格，之后在每個空格處分割字符串來分開。

>>> def tokenize(line):
        """Convert a string into a list of tokens."""
        spaced = line.replace("("," ( ").replace(")"," ) ").replace(",", " , ")
        return spaced.split()

對符合格式的計算器表達式分詞不會損壞名稱，但是會分開所有符號和分隔符。

>>> tokenize("add(2, mul(4, 6))")
["add", "(", "2", ",", "mul", "(", "4", ",", "6", ")", ")"]

擁有更加復合語法的語言可能需要更復雜的分詞器。特別是，許多分析器會解析每種返回標記的語法類型。例如，計算機中的標記類型可能是運算符、名稱、數值或分隔符。這個分類可以簡化標記序列的解析。

語法分析。將標記序列解釋為表達式樹的組件叫做語法分析器。在我們的實現中，語法分析由叫做analyze的遞歸函數完成。它是遞歸的，因為分析標記序列經常涉及到分析這些表達式樹中的標記子序列，它本身作為更大的表達式樹的子分支（比如操作數）。遞歸會生成由求值器使用的層次結構。

analyze函數接受標記列表，以符合格式的表達式開始。它會分析第一個標記，將表示數值的字符串強制轉換為數字的值。之后要考慮計算機中的兩個合法表達式類型。數字標記本身就是完整的基本表達式樹。復合表達式以運算符開始，之后是操作數表達式的列表，由圓括號分隔。我們以一個不檢查語法錯誤的實現開始。

>>> def analyze(tokens):
        """Create a tree of nested lists from a sequence of tokens."""
        token = analyze_token(tokens.pop(0))
        if type(token) in (int, float):
            return token
        else:
            tokens.pop(0)  # Remove (
            return Exp(token, analyze_operands(tokens))
>>> def analyze_operands(tokens):
        """Read a list of comma-separated operands."""
        operands = []
        while tokens[0] != ")":
            if operands:
                tokens.pop(0)  # Remove ,
            operands.append(analyze(tokens))
        tokens.pop(0)  # Remove )
        return operands

最后，我們需要實現analyze_token。analyze_token函數將數值文本轉換為數值。我們并不自己實現這個邏輯，而是依靠內建的 Python 類型轉換，使用int和float構造器來將標記轉換為這種類型。

>>> def analyze_token(token):
        """Return the value of token if it can be analyzed as a number, or token."""
        try:
            return int(token)
        except (TypeError, ValueError):
            try:
                return float(token)
            except (TypeError, ValueError):
                return token

我們的analyze實現就完成了。它能夠正確將符合格式的計算器表達式解析為表達式樹。這些樹由str函數轉換回計算器表達式。

>>> expression = "add(2, mul(4, 6))"
>>> analyze(tokenize(expression))
Exp("add", [2, Exp("mul", [4, 6])])
>>> str(analyze(tokenize(expression)))
"add(2, mul(4, 6))"

analyse函數只會返回符合格式的表達式樹，并且它必須檢測輸入中的語法錯誤。特別是，它必須檢測表達式是否完整、正確分隔，以及只含有已知的運算符。下面的修訂版本確保了語法分析的每一步都找到了預期的標記。

>>> known_operators = ["add", "sub", "mul", "div", "+", "-", "*", "/"]
>>> def analyze(tokens):
        """Create a tree of nested lists from a sequence of tokens."""
        assert_non_empty(tokens)
        token = analyze_token(tokens.pop(0))
        if type(token) in (int, float):
            return token
        if token in known_operators:
            if len(tokens) == 0 or tokens.pop(0) != "(":
                raise SyntaxError("expected ( after " + token)
            return Exp(token, analyze_operands(tokens))
        else:
            raise SyntaxError("unexpected " + token)
>>> def analyze_operands(tokens):
        """Analyze a sequence of comma-separated operands."""
        assert_non_empty(tokens)
        operands = []
        while tokens[0] != ")":
            if operands and tokens.pop(0) != ",":
                raise SyntaxError("expected ,")
            operands.append(analyze(tokens))
            assert_non_empty(tokens)
        tokens.pop(0)  # Remove )
        return elements
>>> def assert_non_empty(tokens):
        """Raise an exception if tokens is empty."""
        if len(tokens) == 0:
            raise SyntaxError("unexpected end of line")

大量的語法錯誤在本質上提升了解釋器的可用性。在上面，SyntaxError 異常包含所發生的問題描述。這些錯誤字符串也用作這些分析函數的定義文檔。

這個定義完成了我們的計算器解釋器。你可以獲取多帶帶的 Python 3 源碼 calc.py來測試。我們的解釋器對錯誤健壯，用戶在calc>提示符后面的每個輸入都會求值為數值，或者產生合適的錯誤，描述輸入為什么不是符合格式的計算器表達式。