用 Python 从零开始写一个简单的解释器（2）
在《用 Python 从零开始写一个简单的解释器（1）》中，我们介绍了 IMP 语言以及我们为它打造的解释器的通用结构。也深入介绍了词法分析器。本文中，我们准备写一个小型的解析器组合子（parser combinator）的库。这个库将被用来创建 IMP 语法分析器，语法分析器的作用是从由词法分析器生成的标记符列表中提取一个抽象语法树（AST）。该解析器组合子的库是语言无关的，所以你可以用它来为任意语言写语法分析器。
什么是解析器组合子？
构建一个语法分析器/解析器有许多许多的方法。而组合子也许是编写一个能启动并运行的解析器的最简单、最快速的方法了。
你可以将一个解析器想象成一个函数。它接收一个标记符流作为输入。如果成功的话，语法分析器会「消耗」标记符流中的一部分标记符。它将返回最终抽象语法树（AST）的一部分，以及剩下的标记符。一个组合子本身也是一个函数，它生成解析器作为输出，一般情况下，它需要以一个或多个解析器作为输入，因此得名“组合子”。你可以先为语言的某些部分创建许多小的解析器，再用组合子来构建最终的解析器。 通过这种方式，你便能使用组合子来创建一个类似 IMP 的完整语言。
一个最小的组合子库
解析器组合子相对来说较为通用，且能用在任意语言上。就像我们在编写词法分析器时所做的一样，我们会先写一个语言无关的组合子库，之后用它来完成我们的 IMP 语法分析器。
首先，让我们定一个 Result 类。每个解析器在解析成功时都会返回一个 Result 对象，错误时则返回 None 。一个 Result 对象包括了一个值（作为 AST 的一部分）以及一个位置信息（标记符流中 一下个标记符的索引）。
| 1234567 | class Result: def __init__(self, value, pos): self.value = value self.pos = pos def __repr__(self): return \’Result(%s, %d)\’ % (self.value, self.pos) |
接着，我们将定义一个基类 Parser 。先前，我提到解析器本质上是以标记符流为输入的函数。实际上我们也把解析器定义成带有 call 方法的对象。这意味着一个语法分析器对象会表现得函数一样，但我们也可以通过定义其它的一些操作符来提供额外的功能。
| 123456789101112131415 | class Parser: def __call__(self, tokens, pos): return None # subclasses will override this def __add__(self, other): return Concat(self, other) def __mul__(self, other): return Exp(self, other) def __or__(self, other): return Alternate(self, other) def __xor__(self, function): return Process(self, function) |
实际执行解析的方法是 call 。它的输入是完整的标记符列表（由词法分析器返回）以及指向列表中的下一个标记符的索引。call 方法的默认实现将总是返回 None（即解析失败）。Parser 的子类将提供它们自己的 call 方法的实现。
其它的方法， add、mul、or、及 xor 分别定义了 + 、 * 、 | 、及 ^ 操 作符。每个操作符提供了调用不同组合子的快捷方法。我们不久就要介绍到它们。
接下来，我们来看看最简单的组合子，Reserved 。
Reserved 将被用来解析保留关键字及操作符；它将接受有特定值和标签的标记符。
请记住，标记符只是值-标签对。token[0] 代表值，token[1] 代表标签。
| 123456789101112 | class Reserved(Parser): def __init__(self, value, tag): self.value = value self.tag = tag def __call__(self, tokens, pos): if pos < len(tokens) and tokens[pos][0] == self.value and tokens[pos][1] is self.tag: return Result(tokens[pos][0], pos + 1) else: return None |
At this point, you might stop and say, “I thought combinators were going to be functions returning parsers. This subclass doesn’t look like a function.”
现在呢，你可能会停下说，“我还以为组合了会是返回解析器的函数。可这个子类并不像是函数啊”。如果你把组合子的构造函数当成是一个返回对象（在当前情况下它正好也是可调用的）的函数的话， 它组合子本身也就像是函数一样了。用子类化来定义新的组合子很简单，因为我们只需要提供一个构造函数和一个 call 方法，同时我们也还能获得其它的功能（比如那些重载的运算符）。
我们继续，Tag 组合子和 Reserved 十分相似。它匹配有某一特殊标签的任意标记符。标记符的值可以是任意值。
| 123456789 | class Tag(Parser): def __init__(self, tag): self.tag = tag def __call__(self, tokens, pos): if pos < len(tokens) and tokens[pos][1] is self.tag: return Result(tokens[pos][0], pos + 1) else:pan class=\”crayon-h\”> pos + 1) else: title=\”用 Python 从零开始写一个简单的解释器（1）\” href=\”http://python.jobbole.com/82206/\” target=\”_blank\”>用 Python 从零开始写一个简单的解释器（1）》中，我们介绍了 IMP 语言以及我们为它打造的解释器的通用结构。也深入介绍了词法分析器。本文中，我们准备写一个小型的解析器组合子（parser combinator）的库。这个库将被用来创建 IMP 语法分析器，语法分析器的作用是从由词法分析器生成的标记符列表中提取一个抽象语法树（AST）。该解析器组合子的库是语言无关的，所以你可以用它来为任意语言写语法分析器。
什么是解析器组合子？构建一个语法分析器/解析器有许多许多的方法。而组合子也许是编写一个能启动并运行的解析器的最简单、最快速的方法了。 你可以将一个解析器想象成一个函数。它接收一个标记符流作为输入。如果成功的话，语法分析器会「消耗」标记符流中的一部分标记符。它将返回最终抽象语法树（AST）的一部分，以及剩下的标记符。一个组合子本身也是一个函数，它生成解析器作为输出，一般情况下，它需要以一个或多个解析器作为输入，因此得名“组合子”。你可以先为语言的某些部分创建许多小的解析器，再用组合子来构建最终的解析器。 通过这种方式，你便能使用组合子来创建一个类似 IMP 的完整语言。 一个最小的组合子库解析器组合子相对来说较为通用，且能用在任意语言上。就像我们在编写词法分析器时所做的一样，我们会先写一个语言无关的组合子库，之后用它来完成我们的 IMP 语法分析器。 首先，让我们定一个 Result 类。每个解析器在解析成功时都会返回一个 Result 对象，错误时则返回 None 。一个 Result 对象包括了一个值（作为 AST 的一部分）以及一个位置信息（标记符流中 一下个标记符的索引）。
接着，我们将定义一个基类 Parser 。先前，我提到解析器本质上是以标记符流为输入的函数。实际上我们也把解析器定义成带有 call 方法的对象。这意味着一个语法分析器对象会表现得函数一样，但我们也可以通过定义其它的一些操作符来提供额外的功能。
实际执行解析的方法是 call 。它的输入是完整的标记符列表（由词法分析器返回）以及指向列表中的下一个标记符的索引。call 方法的默认实现将总是返回 None（即解析失败）。Parser 的子类将提供它们自己的 call 方法的实现。 其它的方法， add、mul、or、及 xor 分别定义了 + 、 * 、 | 、及 ^ 操 作符。每个操作符提供了调用不同组合子的快捷方法。我们不久就要介绍到它们。 接下来，我们来看看最简单的组合子，Reserved 。 Reserved 将被用来解析保留关键字及操作符；它将接受有特定值和标签的标记符。 请记住，标记符只是值-标签对。token[0] 代表值，token[1] 代表标签。
At this point, you might stop and say, “I thought combinators were going to be functions returning parsers. This subclass doesn’t look like a function.” 现在呢，你可能会停下说，“我还以为组合了会是返回解析器的函数。可这个子类并不像是函数啊”。如果你把组合子的构造函数当成是一个返回对象（在当前情况下它正好也是可调用的）的函数的话， 它组合子本身也就像是函数一样了。用子类化来定义新的组合子很简单，因为我们只需要提供一个构造函数和一个 call 方法，同时我们也还能获得其它的功能（比如那些重载的运算符）。 我们继续，Tag 组合子和 Reserved 十分相似。它匹配有某一特殊标签的任意标记符。标记符的值可以是任意值。
|