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

简介: 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天前
|
数据采集 机器学习/深度学习 数据挖掘
Python数据清洗与预处理面试题解析
【4月更文挑战第17天】本文介绍了Python数据清洗与预处理在面试中的常见问题,包括Pandas基础操作、异常值处理和特征工程。通过示例代码展示了数据读取、筛选、合并、分组统计、离群点检测、缺失值和重复值处理、特征缩放、编码、转换和降维。强调了易错点,如忽视数据质量检查、盲目处理数据、数据隐私保护、过度简化特征关系和忽视模型输入要求。掌握这些技能和策略将有助于在面试中脱颖而出。
22 8
|
5天前
|
调度 Python
Python多线程、多进程与协程面试题解析
【4月更文挑战第14天】Python并发编程涉及多线程、多进程和协程。面试中,对这些概念的理解和应用是评估候选人的重要标准。本文介绍了它们的基础知识、常见问题和应对策略。多线程在同一进程中并发执行,多进程通过进程间通信实现并发,协程则使用`asyncio`进行轻量级线程控制。面试常遇到的问题包括并发并行混淆、GIL影响多线程性能、进程间通信不当和协程异步IO理解不清。要掌握并发模型,需明确其适用场景,理解GIL、进程间通信和协程调度机制。
20 0
|
5天前
|
API Python
Python模块化编程:面试题深度解析
【4月更文挑战第14天】了解Python模块化编程对于构建大型项目至关重要,它涉及代码组织、复用和维护。本文深入探讨了模块、包、导入机制、命名空间和作用域等基础概念,并列举了面试中常见的模块导入混乱、不适当星号导入等问题,强调了避免循环依赖、合理使用`__init__.py`以及理解模块作用域的重要性。掌握这些知识将有助于在面试中自信应对模块化编程的相关挑战。
18 0
|
9天前
|
SQL API 数据库
Python中的SQLAlchemy框架:深度解析与实战应用
【4月更文挑战第13天】在Python的众多ORM(对象关系映射)框架中,SQLAlchemy以其功能强大、灵活性和易扩展性脱颖而出,成为许多开发者首选的数据库操作工具。本文将深入探讨SQLAlchemy的核心概念、功能特点以及实战应用,帮助读者更好地理解和使用这一框架。
|
10天前
|
存储 JSON JavaScript
「Python系列」Python JSON数据解析
在Python中解析JSON数据通常使用`json`模块。`json`模块提供了将JSON格式的数据转换为Python对象(如列表、字典等)以及将Python对象转换为JSON格式的数据的方法。
27 0
|
12天前
|
安全 Java 数据处理
Python网络编程基础(Socket编程)多线程/多进程服务器编程
【4月更文挑战第11天】在网络编程中,随着客户端数量的增加,服务器的处理能力成为了一个重要的考量因素。为了处理多个客户端的并发请求,我们通常需要采用多线程或多进程的方式。在本章中,我们将探讨多线程/多进程服务器编程的概念,并通过一个多线程服务器的示例来演示其实现。
|
12天前
|
程序员 开发者 Python
Python网络编程基础(Socket编程) 错误处理和异常处理的最佳实践
【4月更文挑战第11天】在网络编程中,错误处理和异常管理不仅是为了程序的健壮性,也是为了提供清晰的用户反馈以及优雅的故障恢复。在前面的章节中,我们讨论了如何使用`try-except`语句来处理网络错误。现在,我们将深入探讨错误处理和异常处理的最佳实践。
|
16天前
|
缓存 监控 Python
解密Python中的装饰器:优雅而强大的编程利器
Python中的装饰器是一种强大而又优雅的编程工具,它能够在不改变原有代码结构的情况下,为函数或类添加新的功能和行为。本文将深入解析Python装饰器的原理、用法和实际应用,帮助读者更好地理解和利用这一技术,提升代码的可维护性和可扩展性。
|
1月前
|
编译器 测试技术 C++
【Python 基础教程 01 全面介绍】 Python编程基础全攻略:一文掌握Python语法精髓,从C/C++ 角度学习Python的差异
【Python 基础教程 01 全面介绍】 Python编程基础全攻略:一文掌握Python语法精髓,从C/C++ 角度学习Python的差异
164 0
|
4天前
|
安全 数据处理 开发者
《Python 简易速速上手小册》第7章:高级 Python 编程(2024 最新版)
《Python 简易速速上手小册》第7章:高级 Python 编程(2024 最新版)
17 1

推荐镜像

更多