python 之父的解析器系列之三:生成一个 peg 解析器 - 编程思维

原题 | Generating a PEG Parser

作者 | Guido van Rossum(Python之父)

译者 | 豌豆花下猫(“Python猫”公众号作者)

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

首发地址:https://mp.weixin.qq.com/s/oj...

我已经在本系列第二篇文章中简述了解析器的基础结构,并展示了一个简单的手写解析器,根据承诺,我们将转向从语法中生成解析器。我还将展示如何使用@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:通过检查第一个字符是否为引号,我们可以区分出NAMESTRING

至于规则,我用了一个简单的 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

对于典型的装饰器来说,它的嵌套函数(nested function)会替换(或包装)被装饰的函数(decorated function),例如 memoize_wrapper() 会包装 ToyParser 类的 statement() 方法。

因为被包装的函数(wrapped function)是一个方法,所以包装器实际上也是一个方法:它的第一个参数是 self ,指向 ToyParser 实例,后者会调用被装饰的函数。

包装器会缓存每次调用解析方法后的结果——这就是为什么它会被称为“口袋老鼠解析”(packrat parsing)!

这缓存是一个字典,元素是存储在 Parser 实例上的那些字典。

外部字典的 key 是输入的位置;我将 self.memos = {} 添加到 Parser.__init__() ,以初始化它。

内部字典按需添加,它们的 key 由方法及其参数组成。(在当前的设计中没有参数,但我们应该记得 expect(),它恰好有一个参数,而且给它新增通用性,几乎不需要成本。 )

一个解析方法的结果被表示成一个元组,因为它正好有两个结果:一个显式的返回值(对于我们生成的解析器,它是一个 Node,表示所匹配的规则),以及我们从 self.mark() 中获得的一个新的输入位置。

在调用解析方法后,我们会在内部的记忆字典中同时存储它的返回值(res)以及新的输入位置(endpos)。

再次调用相同的解析方法时(在相同的位置,使用相同的参数),我们会从缓存中取出那两个结果,并用 self.reset() 来向前移动输入位置,最后返回那缓存中的返回值。

缓存负数的结果也很重要——实际上大多数对解析方法的调用都是负数的结果。在此情况下,返回值为 None,而输入位置不会变。你可以加一个assert 断言来检查它。

注意:Python 中常用的记忆法是在 memoize() 函数中将缓存定义成一个局部变量。但我们不这么做:因为我在一个最后时刻的调试会话中发现,每个 Parser 实例都必须拥有自己的缓存。然而,你可以用(pos, func, args) 作为 key,以摆脱嵌套字典的设计。

下周我将统览代码,演示在解析示例程序时,所有这些模块实际是如何配合工作的。

我仍然在抓头发中(译注:极度发愁),如何以最佳的方式将协同工作的标记生成器缓冲、解析器和记忆缓存作出可视化。或许我会设法生成动画的 ASCII 作品,而不仅仅是跟踪日志的输出。(译注:感觉他像是在开玩笑,但很难译出这句话的原味。建议阅读原文。)

本文及示例代码的授权协议: CC BY-NC-SA 4.0

英文原文: https://medium.com/@gvanrossum_83706/generating-a-peg-parser-520057d642a9

作者简介: Guido van Rossum,是 Python 的创造者,一直是“终身仁慈独裁者”,直到2018年7月12日退位。目前,他是新的最高决策层的五位成员之一,依然活跃在社区中。

译者简介: 豌豆花下猫,生于广东毕业于武大,现为苏漂程序员,有一些极客思维,也有一些人文情怀,有一些温度,还有一些态度。公众号:「Python猫」(python_cat)。

公众号【Python猫】, 本号连载优质的系列文章,有喵星哲学猫系列、Python进阶系列、好书推荐系列、技术写作、优质英文推荐与翻译等等,欢迎关注哦。

版权声明:本文版权归作者所有,遵循 CC 4.0 BY-SA 许可协议, 转载请注明原文链接
https://segmentfault.com/a/1190000020031609

高效利用python内置的数据结构 - 编程思维

0x00:创建一键多值字典 字典是Python中的一种可变容器,通常以这种形式出现:d = {key1:value1, key2:value2, key3:value3}Python没有规定字典中值的类型,所以如果想让字典中的一个键对应多个值,只要把这些值放到列表这样的容器里就行了。 student = { '

一键分析你的上网行为, 看看你平时上网都在干嘛? - 编程思维

一键分析你的上网行为, 看看你平时上网都在干嘛? 简介 想看看你最近一年都在干嘛?看看你平时上网是在摸鱼还是认真工作?想写年度汇报总结,但是苦于没有数据?现在,它来了。 这是一个能让你了解自己的浏览历史的Chrome浏览历史记录分析程序,当然了,他仅适用于Chrome浏览器或者以Chrome为内核的浏览器。 在该页面中

简单的python循环知识 - 编程思维

我们在写代码时经常会用到循环,python中有for循环和while循环,我们来详细的了解一下这两种循环。 for循环 Python for循环可以遍历任何序列的项目,如一个列表或者一个字符串。 我们通过一个例子来看一下for循环的具体使用,我们通过range() 函数创建一个整数列表,然后将列表中的元素通过for循

leetcode 739:每日温度 daily temperatures - 编程思维

题目: 根据每日 气温 列表,请重新生成一个列表,对应位置的输入是你需要再等待多久温度才会升高超过该日的天数。如果之后都不会升高,请在该位置用 0 来代替。 例如,给定一个列表 temperatures = [73, 74, 75, 71, 69, 72, 76, 73],你的输出应该是 [1, 1, 4, 2, 1,

用python制作好玩的游戏 - 编程思维

炎炎夏日,独坐家中,闲来无事,便用Python写了2个简单的解闷小游戏,分享给你们,也希望大家通过这两个小游戏可以学习Python的编程知识。 1.用Python破解九宫格 九宫格最早叫「洛书」,现在也叫「幻方」。九宫格游戏对人们的思维锻炼有着极大的作用,千百年来对人们的思维训练影响巨大,从古时起人们便意识到九宫格的教

python协程与go协程的区别二 - 编程思维

写在前面 世界是复杂的,每一种思想都是为了解决某些现实问题而简化成的模型,想解决就得先面对,面对就需要选择角度,角度决定了模型的质量, 喜欢此UP主汤质看本质的哲学科普,其中简洁又不失细节的介绍了人类解决问题的思路,以及由概念搭建的思维模型对人类解决问题的重要性与限制.也认识到学习的本质就是: 认识获取(了解概念) -

当你学一个库的时候,怎么看到别人能玩出什么花样 - 编程思维

Dependents Spider 看看用这个Library的最好的项目 当你学一个库的时候,可能总想看看其他人在用这个库做什么 当你在用一种技术的时候,可能总想看看别人能玩出什么花样 只要你给出地址,我就帮你找到 先聊聊 当你在Github上看到一个库,你可能会在这里看到一个 Used by,这里就可以看到使用这个库

如何在github贡献板上创作自己的像素涂鸦 - 编程思维

工作劳累?身体发虚?没时间提交代码?看着自己的Github主页中 0 contributions in the last year 是不是很丧气?不用担心,现在你不仅可以补上你那些空缺的时光,还可以在上面创建属于自己独一无二的像素涂鸦作品,画个爱心对TA表白,涂个蛋糕纪念生日,尽情发挥你的创造力。 各位Gayhub,噢

强大的阿里云-云平台初体验,一款不可错过的云开发 - 编程思维

简介 云开发平台,是阿里云面向广大开发者提供的云上研发工作平台,助力研发团队实现工作的在线化(团队在线、环境在线、代码在线、协同在线)以及研发模式Serverless化,帮助研发团队实现对行业架构经验及架构服务的高效分享与传播,极致提升研发效率,极致降低研发成本。 功能介绍 在云开发平台的菜单栏里共有9个功能点(不分先