3.4 组合语言的解释器
接下来，我们开始一段技术之旅，看看语言如何建立在其他语言之上。元语言抽象（metalinguistic abstraction）——也就是建立新语言——在工程设计的各个分支里都扮演着重要角色。对计算机编程来说尤其如此，因为在编程中，我们不仅能制定新语言，还能通过构造解释器来实现它们。编程语言的解释器是一个函数：把它施加到该语言的某个表达式上，它就会执行对该表达式求值所需的操作。
我们先为一种语言定义解释器，它是 Scheme 的一个有限子集，叫计算器语言（Calculator）。然后，我们会为整个 Scheme 开发一个简略的解释器。我们创建的解释器将是完整的，因为它能让我们用 Scheme 编写完全通用的程序。为此，它会采用第 1 章为 Python 程序引入的同一套环境模型（environment model）。
本节许多示例都放在配套的 Scheme-Syntax Calculator 示例中，因为它们太复杂，没法自然地融进本书的排版。
3.4.1 基于 Scheme 语法的计算器
基于 Scheme 语法的计算器（或简称计算器语言）是一种表达式语言，用于加法、减法、乘法和除法运算。计算器语言沿用 Scheme 的调用表达式语法和运算符行为。加法（
> (+ 1 2 3 4)
10
> (+)
0
> (* 1 2 3 4)
24
> (*)
1减法（
> (- 10 1 2 3)
4
> (- 3)
-3
> (/ 15 12)
1.25
> (/ 30 5 2)
3
> (/ 10)
0.1调用表达式的求值方式是，先求值所有操作数子表达式，再把运算符施加到所得的参数上：
> (- 100 (* 7 (+ 8 (/ -12 -3))))
16.0我们将用 Python 实现计算器语言的解释器。也就是说，我们要写一个 Python 程序，接受字符串行作为输入，返回把这些行当作计算器表达式求值的结果。如果计算器表达式格式不正确，解释器会抛出相应的异常。
3.4.2 表达式树
到目前为止，表达式树（expression tree）只是我们在描述求值过程时提到的一个概念；我们从没在程序里把它显式表示成数据。要编写解释器，就必须把表达式当作数据来操作。
计算器语言中的基本表达式不过是数字或字符串：要么是 int、float，要么是运算符符号。所有复合表达式都是调用表达式。调用表达式是一个 Scheme 列表：第一个元素是运算符，后面跟零个或多个操作数表达式。
Scheme 对。在 Scheme 中，列表是嵌套对，但并非所有对都是列表。为了在 Python 中表示 Scheme 对和列表，我们会定义一个 Pair 类，它类似于本章前面的 Rlist 类。实现代码见 scheme_reader。
空列表由一个名为 nil 的对象表示，它是 nil 类的一个实例。我们假设整个运行期间只会创建一个 nil 实例。
Pair 类和 nil 对象是用 Python 表示的 Scheme 值。它们的 repr 字符串是 Python 表达式，str 字符串是 Scheme 表达式。
>>> s = Pair(1, Pair(2, nil))
>>> s
Pair(1, Pair(2, nil))
>>> print(s)
(1 2)它们实现了 Python 序列的基本接口——长度和元素选择——外加一个返回 Scheme 列表的 map 方法。
>>> len(s)
2
>>> s[1]
2
>>> print(s.map(lambda x: x+4))
(5 6)嵌套列表。嵌套对可以表示列表，而列表的元素本身也可以是列表。因此，嵌套对足以表示 Scheme 表达式，因为 Scheme 表达式实际上就是嵌套列表。
>>> expr = Pair('+', Pair(Pair('*', Pair(3, Pair(4, nil))), Pair(5, nil)))
>>> print(expr)
(+ (* 3 4) 5)
>>> print(expr.second.first)
(* 3 4)
>>> expr.second.first.second.first
3这个例子说明，所有计算器表达式都是嵌套的 Scheme 列表。计算器语言解释器会读入嵌套的 Scheme 列表，把它们转换成用嵌套 Pair 实例表示的表达式树（见下面的解析表达式），再对表达式树求值，得到值（见下面的计算器求值）。
3.4.3 解析表达式
解析是从原始文本输入生成表达式树的过程。解析器由两个组件构成：词法分析器（lexical analyzer）和语法分析器（syntactic analyzer）。首先，词法分析器把输入字符串划分成词元（token），词元是语言的最小语法单元，比如名称和符号。然后，语法分析器根据这个词元序列构建表达式树。语法分析器会消耗词法分析器生成的词元序列。
词法分析。把字符串解释成词元序列的组件称为分词器（tokenizer）或词法分析器。在我们的实现中，分词器是 scheme_tokens 里的函数 tokenize_line。Scheme 词元由空格、括号、点或单引号分隔。分隔符和运算符、数字一样，也是词元。分词器会逐字符分析一行，校验运算符和数字的格式。
对格式良好的计算器表达式分词，会把所有符号和分隔符分离开，同时识别出多字符数字（如 2.3），并转换成数字类型。
>>> tokenize_line('(+ 1 (* 2.3 45))')
['(', '+', 1, '(', '*', 2.3, 45, ')', ')']词法分析是迭代过程，可以逐行单独处理输入程序。
语法分析。把词元序列解释成表达式树的组件称为语法分析器。语法分析是树递归过程，必须考虑可能跨越多行的整个表达式。
语法分析由 scheme_reader 中的 scheme_read 函数实现。它是树递归的，因为分析一段词元序列，往往要把其中一部分词元分析成一个子表达式，而子表达式本身又可能是更大表达式树的一个分支（比如操作数）。递归生成了求值器（evaluator）所使用的层次结构。
scheme_read 函数期望它的输入 src 是一个 Buffer 实例，能访问一个词元序列。Buffer 定义在 buffer 模块中，它把跨多行的词元收集到一个对象里，供语法分析使用。
>>> lines = ['(+ 1', ' (* 2.3 45))']
>>> expression = scheme_read(Buffer(tokenize_lines(lines)))
>>> expression
Pair('+', Pair(1, Pair(Pair('*', Pair(2.3, Pair(45, nil))), nil)))
>>> print(expression)
(+ 1 (* 2.3 45))scheme_read 函数首先检查各种基本情况，包括空输入（这会引发文件结束异常，在 Python 中称为 EOFError）和基本表达式。每当 ( 词元出现在列表开头，就会递归调用 read_tail。
read_tail 函数继续从同一个输入 src 读取，但它被调用时，前提是一个列表已经开始。它的基本情况是输入为空（这是错误）或出现结束列表的右括号。它的递归调用用 scheme_read 读取列表的第一个元素，用 read_tail 读取列表的其余部分，最后返回一个用 Pair 表示的列表。
这个 scheme_read 实现能读取格式良好的 Scheme 列表，而这正是计算器语言所需要的。点列表和引号形式的解析留作练习。
信息丰富的语法错误能大幅提升解释器的可用性。抛出的 SyntaxError 异常会附带对所遇问题的描述。
3.4.4 计算器求值
scalc 模块为计算器语言实现了一个求值器。calc_eval 函数接受一个表达式作为参数并返回它的值。辅助函数 simplify、reduce 和 as_scheme_list 的定义也出现在模型中，下文会用到。
对计算器语言来说，表达式只有两种合法的语法形式：数字和调用表达式，它们都是 Pair 实例，表示格式良好的 Scheme 列表。数字是自求值的（self-evaluating），可以直接从 calc_eval 返回。调用表达式则需要函数应用。
>>> def calc_eval(exp):
"""求值一个计算器表达式。"""
if type(exp) in (int, float):
return simplify(exp)
elif isinstance(exp, Pair):
arguments = exp.second.map(calc_eval)
return simplify(calc_apply(exp.first, arguments))
else:
raise TypeError(exp + ' is not a number or call expression')调用表达式的求值方式是，先把 calc_eval 递归地映射到操作数列表上，算出参数列表。然后，在第二个函数 calc_apply 里把运算符施加到这些参数上。
计算器语言足够简单，每个运算符的应用逻辑都能轻松写在一个函数体里。在 calc_apply 中，每个条件子句对应一个运算符的应用。
>>> def calc_apply(operator, args):
"""把名为 operator 的运算符施加到参数列表 args 上。"""
if not isinstance(operator, str):
raise TypeError(str(operator) + ' is not a symbol')
if operator == '+':
return reduce(add, args, 0)
elif operator == '-':
if len(args) == 0:
raise TypeError(operator + ' requires at least 1 argument')
elif len(args) == 1:
return -args.first
else:
return reduce(sub, args.second, args.first)
elif operator == '*':
return reduce(mul, args, 1)
elif operator == '/':
if len(args) == 0:
raise TypeError(operator + ' requires at least 1 argument')
elif len(args) == 1:
return 1/args.first
else:
return reduce(truediv, args.second, args.first)
else:
raise TypeError(operator + ' is an unknown operator')上面，每个分支分别计算某个运算符的结果，或者在参数数量不对时抛出合适的 TypeError。calc_apply 函数可以直接调用，但必须传入值列表作为参数，而不是操作数表达式列表。
>>> calc_apply('+', as_scheme_list(1, 2, 3))
6
>>> calc_apply('-', as_scheme_list(10, 1, 2, 3))
4
>>> calc_apply('*', nil)
1
>>> calc_apply('*', as_scheme_list(1, 2, 3, 4, 5))
120
>>> calc_apply('/', as_scheme_list(40, 5))
8.0calc_eval 的作用是正确地调用 calc_apply：先算出操作数子表达式的值，再把它们作为参数传给 calc_apply。因此，calc_eval 能接受嵌套表达式。
>>> print(exp)
(+ (* 3 4) 5)
>>> calc_eval(exp)
17calc_eval 的结构是按类型分派的一个例子，这里的类型指表达式的形式。表达式的第一种形式是数字，它不需要额外的求值步骤。通常，不需要额外求值步骤的基本表达式称为自求值。在我们的计算器语言中，唯一的自求值表达式是数字，但通用编程语言还可能包含字符串、布尔值等。
读取-求值-打印循环。与解释器交互的一种常见方式，就是通过读取-求值-打印循环（read-eval-print loop），简称 REPL：它读取一个表达式，对其求值，再把结果打印给用户。Python 交互会话就是这种循环的一个例子。
REPL 的实现可以基本独立于它所用的解释器。下面的函数 read_eval_print_loop 会缓冲用户的输入，用语言特定的 scheme_read 函数构造表达式，再打印把 calc_eval 施加到该表达式上的结果。
>>> def read_eval_print_loop():
"""为计算器运行读取-求值-打印循环。"""
while True:
src = buffer_input()
while src.more_on_line:
expression = scheme_read(src)
print(calc_eval(expression))这个版本的 read_eval_print_loop 包含了交互式界面所需的全部基本组件。一次会话示例如下：
> (* 1 2 3)
6
> (+)
0
> (+ 2 (/ 4 8))
2.5
> (+ 2 2) (* 3 3)
4
9
> (+ 1
(- 23)
(* 4 2.5))
-12这个循环实现没有终止或错误处理机制。我们可以向用户报告错误，改进界面。也可以让用户用键盘中断（UNIX 上是 Control-C）或文件结束异常（UNIX 上是 Control-D）退出循环。为了做到这些，我们把 while 语句原来的语句体放进 try 语句里。第一个 except 子句处理 scheme_read 抛出的 SyntaxError 和 ValueError 异常，以及 calc_eval 抛出的 TypeError 和 ZeroDivisionError 异常。
>>> def read_eval_print_loop():
"""为计算器运行读取-求值-打印循环。"""
while True:
try:
src = buffer_input()
while src.more_on_line:
expression = scheme_read(src)
print(calc_eval(expression))
except (SyntaxError, TypeError, ValueError, ZeroDivisionError) as err:
print(type(err).__name__ + ':', err)
except (KeyboardInterrupt, EOFError): # <Control>-D, etc.
print('Calculation completed.')
return这个循环实现会报告错误，但不退出循环。出错时不退出程序，而是在给出错误信息后重新开始循环，用户就能修改自己的表达式。导入 readline 模块后，用户甚至可以用向上箭头或 Control-P 找回之前的输入。最终得到一个信息丰富的错误报告界面：
> )
SyntaxError: unexpected token: )
> 2.3.4
ValueError: invalid numeral: 2.3.4
> +
TypeError: + is not a number or call expression
> (/ 5)
TypeError: / requires exactly 2 arguments
> (/ 1 0)
ZeroDivisionError: division by zero当我们将解释器推广到计算器语言以外的新语言时，会看到 read_eval_print_loop 由解析函数、求值函数和 try 语句所处理的异常类型参数化。除此之外，所有 REPL 都可以用相同的结构实现。