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

本文涉及的产品
全局流量管理 GTM,标准版 1个月
云解析 DNS,旗舰版 1个月
公共DNS(含HTTPDNS解析),每月1000万次HTTP解析
简介: Python 之父的解析器系列之三:生成一个 PEG 解析器


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

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

所以我们在这创造的是一个简单的编译器编译器(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


目录
相关文章
|
3天前
|
机器学习/深度学习 人工智能 TensorFlow
深入骨髓的解析:Python中神经网络如何学会‘思考’,解锁AI新纪元
【9月更文挑战第11天】随着科技的发展,人工智能(AI)成为推动社会进步的关键力量,而神经网络作为AI的核心,正以其强大的学习和模式识别能力开启AI新纪元。本文将探讨Python中神经网络的工作原理,并通过示例代码展示其“思考”过程。神经网络模仿生物神经系统,通过加权连接传递信息并优化输出。Python凭借其丰富的科学计算库如TensorFlow和PyTorch,成为神经网络研究的首选语言。
10 1
|
6天前
|
存储 JSON API
Python编程:解析HTTP请求返回的JSON数据
使用Python处理HTTP请求和解析JSON数据既直接又高效。`requests`库的简洁性和强大功能使得发送请求、接收和解析响应变得异常简单。以上步骤和示例提供了一个基础的框架,可以根据你的具体需求进行调整和扩展。通过合适的异常处理,你的代码将更加健壮和可靠,为用户提供更加流畅的体验。
26 0
|
14天前
|
Java 缓存 数据库连接
揭秘!Struts 2性能翻倍的秘诀:不可思议的优化技巧大公开
【8月更文挑战第31天】《Struts 2性能优化技巧》介绍了提升Struts 2 Web应用响应速度的关键策略,包括减少配置开销、优化Action处理、合理使用拦截器、精简标签库使用、改进数据访问方式、利用缓存机制以及浏览器与网络层面的优化。通过实施这些技巧,如懒加载配置、异步请求处理、高效数据库连接管理和启用GZIP压缩等,可显著提高应用性能,为用户提供更快的体验。性能优化需根据实际场景持续调整。
40 0
|
14天前
|
数据采集 存储 数据库
Python中实现简单爬虫与数据解析
【8月更文挑战第31天】在数字化时代的浪潮中,数据成为了新的石油。本文将带领读者通过Python编程语言,从零开始构建一个简单的网络爬虫,并展示如何对爬取的数据进行解析和处理。我们将一起探索请求网站、解析HTML以及存储数据的基础知识,让每个人都能成为自己数据故事的讲述者。
|
14天前
|
数据采集 JavaScript 前端开发
Python 爬虫实战:抓取和解析网页数据
【8月更文挑战第31天】本文将引导你通过Python编写一个简单的网络爬虫,从网页中抓取并解析数据。我们将使用requests库获取网页内容,然后利用BeautifulSoup进行解析。通过本教程,你不仅能够学习到如何自动化地从网站收集信息,还能理解数据处理的基本概念。无论你是编程新手还是希望扩展你的技术工具箱,这篇文章都将为你提供有价值的见解。
|
15天前
|
监控 网络协议 Java
Tomcat源码解析】整体架构组成及核心组件
Tomcat,原名Catalina,是一款优雅轻盈的Web服务器,自4.x版本起扩展了JSP、EL等功能,超越了单纯的Servlet容器范畴。Servlet是Sun公司为Java编程Web应用制定的规范,Tomcat作为Servlet容器,负责构建Request与Response对象,并执行业务逻辑。
Tomcat源码解析】整体架构组成及核心组件
|
1月前
|
存储 NoSQL Redis
redis 6源码解析之 object
redis 6源码解析之 object
53 6
|
4天前
|
开发工具
Flutter-AnimatedWidget组件源码解析
Flutter-AnimatedWidget组件源码解析
|
22天前
|
测试技术 Python
python自动化测试中装饰器@ddt与@data源码深入解析
综上所述,使用 `@ddt`和 `@data`可以大大简化写作测试用例的过程,让我们能专注于测试逻辑的本身,而无需编写重复的测试方法。通过讲解了 `@ddt`和 `@data`源码的关键部分,我们可以更深入地理解其背后的工作原理。
19 1
|
1月前
|
开发者 Python
深入解析Python `httpx`源码,探索现代HTTP客户端的秘密!
深入解析Python `httpx`源码,探索现代HTTP客户端的秘密!
64 1