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

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

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

元語言抽象 -- 建立了新的語言 -- 并在所有工程設(shè)計(jì)分支中起到重要作用。它對于計(jì)算機(jī)編程尤其重要，因?yàn)槲覀儾粌H僅可以在編程中構(gòu)想出新的語言，我們也能夠通過構(gòu)建解釋器來實(shí)現(xiàn)它們。編程語言的解釋器是一個函數(shù)，它在語言的表達(dá)式上調(diào)用，執(zhí)行求解表達(dá)式所需的操作。

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

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

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

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

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

就像 Python 中那樣，調(diào)用表達(dá)式的嵌套提供了計(jì)算器語言中的組合手段。為了精簡符號，我們使用運(yùn)算符的標(biāo)準(zhǔn)符號來代替名稱：

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

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

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

計(jì)算器中的基本表達(dá)式只是一個數(shù)值，類型為int或float。所有復(fù)合表達(dá)式都是調(diào)用表達(dá)式。調(diào)用表達(dá)式表示為擁有兩個屬性實(shí)例的Exp類。計(jì)算器的operator總是字符串：算數(shù)運(yùn)算符的名稱或符號。operands要么是基本表達(dá)式，要么是Exp的實(shí)例本身。

>>> 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實(shí)例定義了兩個字符串方法。__repr__方法返回 Python 表達(dá)式，而__str__方法返回計(jì)算器表達(dá)式。

>>> 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的實(shí)例，來表示表達(dá)式樹中的層次結(jié)構(gòu)。

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

調(diào)用表達(dá)式首先通過將calc_eval函數(shù)遞歸映射到操作數(shù)的列表，計(jì)算出參數(shù)列表來求值。之后，在第二個函數(shù)calc_apply中，運(yùn)算符會作用于這些參數(shù)上。

計(jì)算器語言足夠簡單，我們可以輕易地在單一函數(shù)中表達(dá)每個運(yùn)算符的使用邏輯。在calc_apply中，每種條件子句對應(yīng)一個運(yùn)算符。

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

上面，每個語句組計(jì)算了不同運(yùn)算符的結(jié)果，或者當(dāng)參數(shù)錯誤時產(chǎn)生合適的TypeError。calc_apply函數(shù)可以直接調(diào)用，但是必須傳入值的列表作為參數(shù)，而不是運(yùn)算符表達(dá)式的列表。

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

calc_eval的作用是，執(zhí)行合適的calc_apply調(diào)用，通過首先計(jì)算操作數(shù)子表達(dá)式的值，之后將它們作為參數(shù)傳入calc_apply。于是，calc_eval可以接受嵌套表達(dá)式。

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

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

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

REPL 的實(shí)現(xiàn)與所使用的解釋器無關(guān)。下面的read_eval_print_loop函數(shù)使用內(nèi)建的input函數(shù)，從用戶接受一行文本作為輸入。它使用語言特定的calc_parse函數(shù)構(gòu)建表達(dá)式樹。calc_parse在隨后的解析一節(jié)中定義。最后，它打印出對由calc_parse返回的表達(dá)式樹調(diào)用calc_eval的結(jié)果。

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

這個循環(huán)沒有實(shí)現(xiàn)終端或者錯誤處理機(jī)制。我們可以通過向用戶報(bào)告錯誤來改進(jìn)這個界面。我們也可以允許用戶通過發(fā)射鍵盤中斷信號（Control-C），或文件末尾信號（Control-D）來退出循環(huán)。為了實(shí)現(xiàn)這些改進(jìn)，我們將原始的while語句組放在try語句中。第一個except子句處理了由calc_parse產(chǎn)生的SyntaxError異常，也處理了由calc_eval產(chǎn)生的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

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

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.

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

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

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

標(biāo)記序列由叫做tokenize的詞法分析器產(chǎn)生，并被叫做analyze語法分析器使用。這里，我們定義了calc_parse，它只接受符合格式的計(jì)算器表達(dá)式。一些語言的解析器為接受以換行符、分號或空格分隔的多種表達(dá)式而設(shè)計(jì)。我們在引入 Logo 語言之前會推遲實(shí)現(xiàn)這種復(fù)雜性。

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

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

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

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

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

語法分析。將標(biāo)記序列解釋為表達(dá)式樹的組件叫做語法分析器。在我們的實(shí)現(xiàn)中，語法分析由叫做analyze的遞歸函數(shù)完成。它是遞歸的，因?yàn)榉治鰳?biāo)記序列經(jīng)常涉及到分析這些表達(dá)式樹中的標(biāo)記子序列，它本身作為更大的表達(dá)式樹的子分支（比如操作數(shù)）。遞歸會生成由求值器使用的層次結(jié)構(gòu)。

analyze函數(shù)接受標(biāo)記列表，以符合格式的表達(dá)式開始。它會分析第一個標(biāo)記，將表示數(shù)值的字符串強(qiáng)制轉(zhuǎn)換為數(shù)字的值。之后要考慮計(jì)算機(jī)中的兩個合法表達(dá)式類型。數(shù)字標(biāo)記本身就是完整的基本表達(dá)式樹。復(fù)合表達(dá)式以運(yùn)算符開始，之后是操作數(shù)表達(dá)式的列表，由圓括號分隔。我們以一個不檢查語法錯誤的實(shí)現(xiàn)開始。

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

最后，我們需要實(shí)現(xiàn)analyze_token。analyze_token函數(shù)將數(shù)值文本轉(zhuǎn)換為數(shù)值。我們并不自己實(shí)現(xiàn)這個邏輯，而是依靠內(nèi)建的 Python 類型轉(zhuǎn)換，使用int和float構(gòu)造器來將標(biāo)記轉(zhuǎn)換為這種類型。

>>> 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實(shí)現(xiàn)就完成了。它能夠正確將符合格式的計(jì)算器表達(dá)式解析為表達(dá)式樹。這些樹由str函數(shù)轉(zhuǎn)換回計(jì)算器表達(dá)式。

>>> 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函數(shù)只會返回符合格式的表達(dá)式樹，并且它必須檢測輸入中的語法錯誤。特別是，它必須檢測表達(dá)式是否完整、正確分隔，以及只含有已知的運(yùn)算符。下面的修訂版本確保了語法分析的每一步都找到了預(yù)期的標(biāo)記。

>>> 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")

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

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