<jupyter_start><jupyter_text>[3.5 组合语言的解释器](http://www-inst.eecs.berkeley.edu/~cs61a/sp12/book/interpretation.htmlinterpreters-for-languages-with-combination)运行在任何现代计算机上的软件都以多种编程语言写成。其中有物理语言，例如用于特定计算机的机器语言。这些语言涉及到基于独立储存位和原始机器指令的数据表示和控制。机器语言的程序员涉及到使用提供的硬件，为资源有限的计算构建系统和功能的高效实现。高阶语言构建在机器语言之上，隐藏了表示为位集的数据，以及表示为原始指令序列的程序的细节。这些语言拥有例如过程定义的组合和抽象的手段，它们适用于组织大规模的软件系统。元语言抽象 -- 建立了新的语言 -- 并在所有工程设计分支中起到重要作用。它对于计算机编程尤其重要，因为我们不仅仅可以在编程中构想出新的语言，我们也能够通过构建解释器来实现它们。编程语言的解释器是一个函数，它在语言的表达式上调用，执行求解表达式所需的操作。我们现在已经开始了技术之旅，通过这种技术，编程语言可以建立在其它语言之上。我们首先会为计算器定义解释器，它是一种受限的语言，和 Python 调用表达式具有相同的语法。我们之后会从零开始开发 Scheme 和 Logo 语言的解释器，它们都是 Lisp 的方言，Lisp 是现在仍旧广泛使用的第二老的语言。我们所创建的解释器，在某种意义上，会让我们使用 Logo 编写完全通用的程序。为了这样做，它会实现我们已经在这门课中开发的求值环境模型。 3.5.1 计算器我们的第一种新语言叫做计算器，一种用于加减乘除的算术运算的表达式语言。计算器拥有 Python 调用表达式的语法，但是它的运算符对于所接受的参数数量更加灵活。例如，计算器运算符`mul`和`add`可接受任何数量的参数：<jupyter_code>calc> add(1, 2, 3, 4)
10
calc> mul()
1<jupyter_output><empty_output><jupyter_text>`sub`运算符拥有两种行为：传入一个运算符，它会对运算符取反。传入至少两个，它会从第一个参数中减掉剩余的参数。`div`运算符拥有 Python 的`operator.truediv`的语义，只接受两个参数。<jupyter_code>calc> sub(10, 1, 2, 3)
4
calc> sub(3)
-3
calc> div(15, 12)
1.25<jupyter_output><empty_output><jupyter_text>就像 Python 中那样，调用表达式的嵌套提供了计算器语言中的组合手段。为了精简符号，我们使用运算符的标准符号来代替名称：<jupyter_code>calc> sub(100, mul(7, add(8, div(-12, -3))))
16.0
calc> -(100, *(7, +(8, /(-12, -3))))
16.0<jupyter_output><empty_output><jupyter_text>我们会使用 Python 实现计算器解释器。也就是说，我们会编写 Python 程序来接受字符串作为输入，并返回求值结果。如果输入是符合要求的计算器表达式，结果为字符串，反之会产生合适的异常。计算器语言解释器的核心是叫做`calc_eval`的递归函数，它会求解树形表达式对象。**表达式树。**到目前为止，我们在描述求值过程中所引用的表达式树，还是概念上的实体。我们从没有显式将表达式树表示为程序中的数据。为了编写解释器，我们必须将表达式当做数据操作。在这一章中，许多我们之前介绍过的概念都会最终以代码实现。计算器中的基本表达式只是一个数值，类型为`int`或`float`。所有复合表达式都是调用表达式。调用表达式表示为拥有两个属性实例的`Exp`类。计算器的`operator`总是字符串：算数运算符的名称或符号。`operands`要么是基本表达式，要么是`Exp`的实例本身。<jupyter_code>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)<jupyter_output><empty_output><jupyter_text>`Exp`实例定义了两个字符串方法。`__repr__`方法返回 Python 表达式，而`__str__`方法返回计算器表达式。<jupyter_code>Exp('add', [1, 2])
str(Exp('add', [1, 2]))
Exp('add', [1, Exp('mul', [2, 3, 4])])
str(Exp('add', [1, Exp('mul', [2, 3, 4])]))<jupyter_output><empty_output><jupyter_text>最后的例子演示了`Exp`类如何通过包含作为`operands`元素的`Exp`的实例，来表示表达式树中的层次结构。<jupyter_code>def calc_eval(exp):
    """Evaluate a Calculator expression."""
    if type(exp) in (int, float):
        return exp
    elif type(exp) == Exp:
        arguments = list(map(calc_eval, exp.operands))
        return calc_apply(exp.operator, arguments)<jupyter_output><empty_output><jupyter_text>**求值。**`calc_eval`函数接受表达式作为参数，并返回它的值。它根据表达式的形式为表达式分类，并且指导它的求值。对于计算器来说，表达式的两种句法形式是数值或调用表达式，后者是`Exp`的实例。数值是自求值的，它们可以直接从`calc_eval`中返回。调用表达式需要使用函数。调用表达式首先通过将`calc_eval`函数递归映射到操作数的列表，计算出参数列表来求值。之后，在第二个函数`calc_apply`中，运算符会作用于这些参数上。计算器语言足够简单，我们可以轻易地在单一函数中表达每个运算符的使用逻辑。在`calc_apply`中，每种条件子句对应一个运算符。<jupyter_code>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<jupyter_output><empty_output><jupyter_text>上面，每个语句组计算了不同运算符的结果，或者当参数错误时产生合适的`TypeError`。`calc_apply`函数可以直接调用，但是必须传入值的列表作为参数，而不是运算符表达式的列表。<jupyter_code>calc_apply('+', [1, 2, 3])
calc_apply('-', [10, 1, 2, 3])
calc_apply('*', [])
calc_apply('/', [40, 5])<jupyter_output><empty_output><jupyter_text>`calc_eval`的作用是，执行合适的`calc_apply`调用，通过首先计算操作数子表达式的值，之后将它们作为参数传入`calc_apply`。于是，`calc_eval`可以接受嵌套表达式。<jupyter_code>e = Exp('add', [2, Exp('mul', [4, 6])])
str(e)
calc_eval(e)<jupyter_output><empty_output><jupyter_text>`calc_eval`的结构是个类型（表达式的形式）分发的例子。第一种表达式是数值，不需要任何的额外求值步骤。通常，基本表达式不需要任何额外的求值步骤，这叫做自求值。计算器语言中唯一的自求值表达式就是数值，但是在通用语言中可能也包括字符串、布尔值，以及其它。**“读取-求值-打印”循环。**和解释器交互的典型方式是“读取-求值-打印”循环（REPL），它是一种交互模式，读取表达式、对其求值，之后为用户打印出结果。Python 交互式会话就是这种循环的例子。REPL 的实现与所使用的解释器无关。下面的`read_eval_print_loop`函数使用内建的`input`函数，从用户接受一行文本作为输入。它使用语言特定的`calc_parse`函数构建表达式树。`calc_parse`在随后的解析一节中定义。最后，它打印出对由`calc_parse`返回的表达式树调用`calc_eval`的结果。<jupyter_code>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))<jupyter_output><empty_output><jupyter_text>`read_eval_print_loop`的这个版本包含所有交互式界面的必要组件。一个样例会话可能像这样：<jupyter_code>calc> mul(1, 2, 3)
6
calc> add()
0
calc> add(2, div(4, 8))
2.5<jupyter_output><empty_output><jupyter_text>这个循环没有实现终端或者错误处理机制。我们可以通过向用户报告错误来改进这个界面。我们也可以允许用户通过发射键盘中断信号（`Control-C`），或文件末尾信号（`Control-D`）来退出循环。为了实现这些改进，我们将原始的`while`语句组放在`try`语句中。第一个`except`子句处理了由`calc_parse`产生的`SyntaxError`异常，也处理了由`calc_eval`产生的`TypeError`和`ZeroDivisionError`异常。<jupyter_code>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):  # <Control>-D, etc.
            print('Calculation completed.')
            return<jupyter_output><empty_output><jupyter_text>这个循环实现报告错误而不退出循环。发生错误时不退出程序，而是在错误消息之后重新开始循环可以让用户回顾他们的表达式。通过导入`readline`模块，用户甚至可以使用上箭头或`Control-P`来回忆他们之前的输入。最终的结果提供了错误信息报告的界面：<jupyter_code>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.<jupyter_output><empty_output><jupyter_text>在我们将解释器推广到计算器之外的语言时，我们会看到，`read_eval_print_loop`由解析函数、求值函数，和由`try`语句处理的异常类型参数化。除了这些修改之外，任何 REPL 都可以使用相同的结构来实现。 3.5.2 解析解析是从原始文本输入生成表达式树的过程。解释这些表达式树是求值函数的任务，但是解析器必须提供符合格式的表达式树给求值器。解析器实际上由两个组件组成，词法分析器和语法分析器。首先，词法分析器将输入字符串拆成标记（token），它们是语言的最小语法单元，就像名称和符号那样。其次，语法分析器从这个标记序列中构建表达式树。<jupyter_code>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<jupyter_output><empty_output><jupyter_text>标记序列由叫做`tokenize`的词法分析器产生，并被叫做`analyze`语法分析器使用。这里，我们定义了`calc_parse`，它只接受符合格式的计算器表达式。一些语言的解析器为接受以换行符、分号或空格分隔的多种表达式而设计。我们在引入 Logo 语言之前会推迟实现这种复杂性。**词法分析。**用于将字符串解释为标记序列的组件叫做分词器（tokenizer ），或者词法分析器。在我们的视线中，分词器是个叫做`tokenize`的函数。计算器语言由包含数值、运算符名称和运算符类型的符号（比如`+`）组成。这些符号总是由两种分隔符划分：逗号和圆括号。每个符号本身都是标记，就像每个逗号和圆括号那样。标记可以通过向输入字符串添加空格，之后在每个空格处分割字符串来分开。<jupyter_code>def tokenize(line):
    """Convert a string into a list of tokens."""
    spaced = line.replace('(',' ( ').replace(')',' ) ').replace(',', ' , ')
    return spaced.split()<jupyter_output><empty_output><jupyter_text>对符合格式的计算器表达式分词不会损坏名称，但是会分开所有符号和分隔符。<jupyter_code>tokenize('add(2, mul(4, 6))')<jupyter_output><empty_output><jupyter_text>拥有更加复合语法的语言可能需要更复杂的分词器。特别是，许多分析器会解析每种返回标记的语法类型。例如，计算机中的标记类型可能是运算符、名称、数值或分隔符。这个分类可以简化标记序列的解析。**语法分析。**将标记序列解释为表达式树的组件叫做语法分析器。在我们的实现中，语法分析由叫做`analyze`的递归函数完成。它是递归的，因为分析标记序列经常涉及到分析这些表达式树中的标记子序列，它本身作为更大的表达式树的子分支（比如操作数）。递归会生成由求值器使用的层次结构。`analyze`函数接受标记列表，以符合格式的表达式开始。它会分析第一个标记，将表示数值的字符串强制转换为数字的值。之后要考虑计算机中的两个合法表达式类型。数字标记本身就是完整的基本表达式树。复合表达式以运算符开始，之后是操作数表达式的列表，由圆括号分隔。我们以一个不检查语法错误的实现开始。<jupyter_code>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<jupyter_output><empty_output><jupyter_text>最后，我们需要实现`analyze_token`。`analyze_token`函数将数值文本转换为数值。我们并不自己实现这个逻辑，而是依靠内建的 Python 类型转换，使用`int`和`float`构造器来将标记转换为这种类型。<jupyter_code>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<jupyter_output><empty_output><jupyter_text>我们的`analyze`实现就完成了。它能够正确将符合格式的计算器表达式解析为表达式树。这些树由`str`函数转换回计算器表达式。<jupyter_code>expression = 'add(2, mul(4, 6))'
analyze(tokenize(expression))
str(analyze(tokenize(expression)))<jupyter_output><empty_output><jupyter_text>`analyse`函数只会返回符合格式的表达式树，并且它必须检测输入中的语法错误。特别是，它必须检测表达式是否完整、正确分隔，以及只含有已知的运算符。下面的修订版本确保了语法分析的每一步都找到了预期的标记。<jupyter_code>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')<jupyter_output><empty_output>
{'fraction_non_alphanumeric': 0.13759283945915063, 'fraction_numerical': 0.01218815463721196, 'mean_word_length': 6.672023374726077, 'pattern_counts': {'":': 0, '<': 82, '<?xml version=': 0, '>': 99, 'https://': 0, 'lorem ipsum': 0, 'www.': 1, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '20', 'dir': 'jupyter-structured-clean-dedup', 'id': '402547', 'license': 'MIT', 'n_tokens_mistral': 5851, 'n_tokens_neox': 6457, 'n_words': 523, 'path': 'Chapter 3/Section 3.5.ipynb', 'repo_name': 'allenwoods/sicp-jupyter', 'size': '10502'}