Python 之父的解析器系列之三：生成一个 PEG 解析器

Python猫

发布于 2019-08-15 07:53:04

79800

代码可运行

文章被收录于专栏：Python无止境Python无止境

运行总次数：0

代码可运行

? “Python猫” ，一个值得加星标的公众号

原题 | Generating a PEG Parser

作者 | Guido van Rossum（Python之父）

译者 | 豌豆花下猫（“Python猫”公众号作者）

声明 | 本翻译是出于交流学习的目的，基于 CC BY-NC-SA 4.0 授权协议。为便于阅读，内容略有改动。

我已经在本系列第二篇文章中简述了解析器的基础结构，并展示了一个简单的手写解析器，根据承诺，我们将转向从语法中生成解析器。我还将展示如何使用@memoize装饰器，以实现packrat 解析。

【这是 PEG 系列第 3 篇。参见第1篇、第2篇】

上篇文章我们以一个手写的解析器结束。给语法加上一些限制的话，我们很容易从语法中自动生成这样的解析器。（我们稍后会解除那些限制。）

我们需要两个东西：一个东西读取语法，并构造一个表现语法规则的数据结构；还有一个东西则用该数据结构来生成解析器。我们还需要无聊的胶水，我就不提啦。

所以我们在这创造的是一个简单的编译器编译器（compiler-compiler）。我将语法符号简化了一些，仅保留规则与备选项；这其实对于我在本系列的前面所用的玩具语法来说，已经足够了。

statement: assignment | expr | if_statement
expr: expr '+' term | expr '-' term | term
term: term '*' atom | term '/' atom | atom
atom: NAME | NUMBER | '(' expr ')'
assignment: target '=' expr
target: NAME
if_statement: 'if' expr ':' statement

使用完整的符号，我们为语法文件写出语法：

grammar: rule+ ENDMARKER
rule: NAME ':' alternative ('|' alternative)* NEWLINE
alternative: item+
item: NAME | STRING

用个花哨的叫法，这是我们的第一个元语法（语法的语法），而我们的解析器生成器将是一个元编译器（编译器是一个程序，将其它程序从一种语言转译为另一种语言；元编译器是一种编译器，其输入是一套语法，而输出是一个解析器）。

有个简单地表示元语法的方法，主要是使用内置的数据类型：一条规则的右侧只是由一系列的条目组成的列表，且这些条目只能是字符串。（Hack：通过检查第一个字符是否为引号，我们可以区分出NAME和STRING）

至于规则，我用了一个简单的 Rule 类，所以整个语法就是一些 Rule 对象。

这是 Rule 类，省略__repr__与__eq__：

class Rule:
    def __init__(self, name, alts):
        self.name = name
        self.alts = alts

调用它的是这个GrammarParser类（关于基类Parser ，请参阅我之前的帖子）：

class GrammarParser(Parser):
    def grammar(self):
        pos = self.mark()
        if rule := self.rule():
            rules = [rule]
            while rule := self.rule():
                rules.append(rule)
            if self.expect(ENDMARKER):
                return rules    # <------------- final result
        self.reset(pos)
        return None
    def rule(self):
        pos = self.mark()
        if name := self.expect(NAME):
            if self.expect(":"):
                if alt := self.alternative():
                    alts = [alt]
                    apos = self.mark()
                    while (self.expect("|")
                           and (alt := self.alternative())):
                        alts.append(alt)
                        apos = self.mark()
                    self.reset(apos)
                    if self.expect(NEWLINE):
                        return Rule(name.string, alts)
        self.reset(pos)
        return None
    def alternative(self):
        items = []
        while item := self.item():
            items.append(item)
        return items
    def item(self):
        if name := self.expect(NAME):
            return name.string
        if string := self.expect(STRING):
            return string.string
        return None

注意 ENDMARKER ，它用来确保在最后一条规则后没有遗漏任何东西（如果语法中出现拼写错误，可能会导致这种情况）。

我放了一个简单的箭头，指向了 grammar() 方法的返回值位置，返回结果是一个存储 Rule 的列表。

其余部分跟上篇文章中的 ToyParser 类很相似，所以我不作解释。

只需留意，item() 返回一个字符串，alternative() 返回一个字符串列表，而 rule() 中的 alts 变量，则是一个由字符串列表组成的列表。

然后，rule() 方法将规则名称（一个字符串）与 alts 结合，放入 Rule 对象。

如果把这份代码用到包含了我们的玩具语法的文件上，则 grammar() 方法会返回以下的由 Rule 对象组成的列表：

[
  Rule('statement', [['assignment'], ['expr'], ['if_statement']]),
  Rule('expr', [['term', "'+'", 'expr'],
                ['term', "'-'", 'term'],
                ['term']]),
  Rule('term', [['atom', "'*'", 'term'],
                ['atom', "'/'", 'atom'],
                ['atom']]),
  Rule('atom', [['NAME'], ['NUMBER'], ["'('", 'expr', "')'"]]),
  Rule('assignment', [['target', "'='", 'expr']]),
  Rule('target', [['NAME']]),
  Rule('if_statement', [["'if'", 'expr', "':'", 'statement']]),
]

既然我们已经有了元编译器的解析部分，那就创建代码生成器吧。

把这些聚合起来，就形成了一个基本的元编译器：

def generate_parser_class(rules):
    print(f"class ToyParser(Parser):")
    for rule in rules:
        print()
        print(f"    @memoize")
        print(f"    def {rule.name}(self):")
        print(f"        pos = self.mark()")
        for alt in rule.alts:
            items = []
            print(f"        if (True")
            for item in alt:
                if item[0] in ('"', "'"):
                    print(f"            and self.expect({item})")
                else:
                    var = item.lower()
                    if var in items:
                        var += str(len(items))
                    items.append(var)
                    if item.isupper():
                        print("            " +
                              f"and ({var} := self.expect({item}))")
                    else:
                        print(f"            " +
                              f"and ({var} := self.{item}())")
            print(f"        ):")
            print(f"            " +
              f"return Node({rule.name!r}, [{', '.join(items)}])")
            print(f"        self.reset(pos)")
        print(f"        return None")

这段代码非常难看，但它管用（某种程度上），不管怎样，我打算将来重写它。

在"for alt in rule.alts"循环中，有些代码细节可能需要作出解释：对于备选项中的每个条目，我们有三种选择的可能：

如果该条目是字符串字面量，例如'+' ，我们生成self.expect('+')
如果该条目全部是大写，例如NAME ，我们生成(name := self.expect(NAME))
其它情况，例如该条目是expr，我们生成 (expr := self.expr())

如果在单个备选项中出现多个相同名称的条目（例如term '-' term），我们会在第二个条目后附加一个数字。这里还有个小小的 bug，我会在以后的内容中修复。

这只是它的一部分输出（完整的类非常无聊）。不用担心那些零散的、冗长的 if (True and … ) 语句，我使用它们，以便每个生成的条件都能够以and 开头。Python 的字节码编译器会优化它。

class ToyParser(Parser):
    @memoize
    def statement(self):
        pos = self.mark()
        if (True
            and (assignment := self.assignment())
        ):
            return Node('statement', [assignment])
        self.reset(pos)
        if (True
            and (expr := self.expr())
        ):
            return Node('statement', [expr])
        self.reset(pos)
        if (True
            and (if_statement := self.if_statement())
        ):
            return Node('statement', [if_statement])
        self.reset(pos)
        return None
    ...

注意@memoize 装饰器：我“偷运”（smuggle）它进来，以便转向另一个主题：使用记忆法（memoization）来加速生成的解析器。

这是实现该装饰器的 memoize() 函数：

def memoize(func):
    def memoize_wrapper(self, *args):
        pos = self.mark()
        memo = self.memos.get(pos)
        if memo is None:
            memo = self.memos[pos] = {}
        key = (func, args)
        if key in memo:
            res, endpos = memo[key]
            self.reset(endpos)
        else:
            res = func(self, *args)
            endpos = self.mark()
            memo[key] = res, endpos
        return res
return memoize_wrapper