实现 PEG 特性

2024-10-05 本文已影响0人 fatshi

【翻译】https://medium.com/@gvanrossum_83706/implementing-peg-features-76caa4b2151f

在上一篇文章中使我的 PEG 解析器生成器自托管之后，我现在准备展示如何实现其他各种 PEG 功能。

我们将介绍以下 PEG 功能：

命名项目：（NAME=item名称可以在操作中使用）
前瞻：（&item正）和!item（负）
将项目分组放在括号中：(item item ...)
可选项目：[item item ...]和item?
重复项：（item*零个或多个）和item+（一个或多个）

让我们从命名项开始。当我们在一个替代方案中有多个引用相同规则的项时，这些很方便，如下所示：

expr: term '+' term

term我们的生成器允许我们通过在变量名后附加一个数字来引用秒1，因此我们可以像这样编写操作：

expr: term '+' term { term + term1 }

但这并不是每个人都喜欢的，我个人更愿意写这样的东西：

expr: left=term '+' right=term { left + right }

通过更改规则，可以轻松地在元语法中支持这一点，item如下所示：

item:
    | NAME = atom { NamedItem(name.string, atom) }
    | atom { atom }
atom:
    | NAME { name.string }
    | STRING { string.string }

（atom刚才旧的在哪里item。）

NamedItem这就要求我们向中添加类的定义grammar.py，这是您经常听说的另一个数据类——具有属性name和item。

我们还需要对代码生成器进行一些小改动，我将把它留给读者作为练习（或者您可以查看我的仓库 :-)。生成的代码现在将把匹配每个项目的结果分配给具有指定名称的变量，而不是从项目的规则名称派生的名称。这也适用于作为标记的项目（形式NAME或字符串文字，如':='）。

接下来是前瞻。您可能在正则表达式中熟悉这些。前瞻可以根据其后的内容拒绝或接受当前替代方案，而无需进一步输入指针。如果其项被识别，则正向前瞻会接受；如果其项未被识别，则负向前瞻会接受。

实际上，前瞻可以作为一种更简洁的方法来解决我在上一集中写到的解析操作带来的混乱：与其让操作通过返回来拒绝已经接受的替代方案None，不如OP在项目前面加上前瞻，以确保它不是"}"。旧规则的结尾是这样的：

    | OP { None if op.string in ("{", "}") else op.string }

新版本如下所示：

    | !"}" OP { op.string }

这将花括号的特殊情况从操作移到了语法中，这也是它应有的位置。我们不需要检查"{"，因为它与之前的替代方案相匹配（实际上，这对旧版本也是如此，但我忘了 :-)。

我们将前瞻语法添加到的规则中item，如下所示：

item:
    | NAME = atom { NamedItem(name.string, atom) }
    | atom { atom }
    | "&" atom { Lookahead(atom, True) }
    | "!" atom { Lookahead(atom, False) }

再次，我们必须添加一个Lookahead数据类grammar.py（并将其导入@subheader！），并稍微调整一下生成器。生成的代码使用以下辅助方法：

    def lookahead(self, positive, func, *args):
        mark = self.mark()
        ok = func(*args) is not None
        self.reset(mark)
        return ok == positive

在我们的例子中，此替代方案的生成代码如下所示：

        if (True
            and self.lookahead(False, self.expect, "}")
            and (op := self.expect(OP))
        ):
            return op . string

正如上面的语法片段所暗示的，前瞻无法命名。这很容易改变，但我想不出与值有关的任何有用的东西；此外，对于负前瞻，值始终是None。

接下来让我们添加括号组。将它们添加到元语法的最佳位置是在规则中atom：

atom:
    | NAME { name.string }
    | STRING { string.string }
    | "(" alts ")" { self.synthetic_rule(alts) }

前两个替代方案保持不变。新替代方案的操作使用了一个 hack（其实现仍未解释），允许元解析器动态地向语法添加新规则。此辅助函数（在元解析器上定义）返回新对象的名称Rule。此名称是一个固定前缀，后跟一个数字以使其唯一，例如_synthetic_rule_1。

您可能想知道，如果由于元解析器回溯而导致合成规则最终被放弃，会发生什么情况。我看不出当前的元语法在哪里可以允许这种情况而不会失败，但它相当安全——最坏的情况是语法中有一个未使用的规则。而且由于记忆缓存，相同的操作永远不会对相同的输入位置执行两次，所以这也不是问题（但即使如此，最坏的情况也是我们有一个无效的规则）。

在括号内使用alts意味着我们可以在组中使用竖线，这是分组的目的之一。例如，如果我们想确保我们的基于前瞻的“动作混乱”解决方案不会意外匹配{，我们可以像这样更新负前瞻：

    | !("{" | "}") OP { op.string }

更好的是，组还可以包含操作。这在“操作混乱”解决方案中没有用处，但在其他情况下很有用。而且因为我们无论如何都会生成合成规则，所以实施它不需要任何额外的工作（除了实施synthetic_rule:-)。

继续讨论可选项。就像我在旧pgen中所做的那样，我使用方括号来表示可选组。这通常很有用，例如，描述 Pythonfor循环的语法规则可能会使用它来表示存在可选else子句。语法可以再次添加到 for 规则中atom，如下所示：

atom:
    | NAME { name.string }
    | STRING { string.string }
    | "(" alts ")" { self.synthetic_rule(alts) }
    | "[" alts "]" { Maybe(self.synthetic_rule(alts)) }

这Maybe是另一个具有单个item属性的数据类。我们修改代码生成器以生成代码，该代码保留合成解析函数为所包含的替代方案返回的值，但如果该值为，则不会失败。我们通过在代码中None添加来实现这一点，例如以下代码：or True``[term]

if (True
    and ((term := self.term()) or True)
):
    return term

继续讨论重复，这是 PEG 的另一个有用功能（该符号借用自正则表达式，也用于pgen）。有两种形式：在原子后附加星号表示“零次或多次重复”，而附加加号表示“一次或多次重复”。出于各种原因，我最终重写了item和的语法规则atom，插入了一条我命名为的中间规则molecule：

item:
    | NAME '=' molecule { NamedItem(name.string, molecule) }
    | "&" atom { Lookahead(atom) }
    | "!" atom { Lookahead(atom, False) }

    | molecule { molecule }
molecule:
    | atom "?" { Maybe(atom) }
    | atom "*" { Loop(atom, False) }
    | atom "+" { Loop(atom, True) }
    | atom { atom }
    | "[" alts "]" { Maybe(self.synthetic_rule(alts)) }
atom:
    | NAME { name.string }
    | STRING {string.string }
    | "(" alts ")" { self.synthetic_rule(alts) }

请注意，这为可选值（atom?）引入了一种替代语法，它不需要额外的实施工作，因为它只是创建Maybe节点的另一种方式。

此处需要重构规则，因为我不想轻易允许异常，例如可选重复（因为那只是零次或多次重复）、重复重复（由于 PEG 始终使用急切匹配，内部重复将吞噬所有匹配）或重复可选项（如果可选项不匹配，解析器将停止运行）。请注意，这不是 100% 的解决方案，因为您仍然可以编写类似的东西(foo?)*。解析器生成器必须为这种情况添加检查，但这超出了本系列的范围。

数据类Loop有两个属性，item和nonempty。生成的代码在生成的解析器上使用辅助方法，loop()它具有与之前类似的签名lookahead()：

    def loop(self, nonempty, func, *args):
        mark = self.mark()
        nodes = []
        while node := func(*args) is not None:
            nodes.append(node)
        if len(nodes) >= nonempty:
            return nodes
        self.reset(mark)
        return None

如果 nonempty 为False（即使用的语法*），则永远不会失败 — 相反，当它没有看到该项目的出现时，它将返回一个空列表。为了实现这一点，我们让解析器生成器发出is not None检查，而不是我在上一篇文章中展示的更宽松的“真实性”检查 —False如果识别出空列表，则会返回“真实性”检查。

今天就讲到这里！我本来打算讨论~TatSu 中的“cut”运算符 ( )，但我还没有遇到过它的实际用例，所以我不是解释它的最佳人选——TatSu 文档只提供了一个玩具示例，这并没有给我太多启发。我也没有在其他 PEG 解析器生成器中找到它，所以也许这是 TatSu 的发明。也许我将来会解释它。（与此同时，我确实实现了它，以防它有用。:-)

我认为下一集将讲述我编写可以解析所有 Python 的 PEG 语法的经历。这主要是我参加本周在伦敦举行的 Python 核心开发人员冲刺活动的方式，得到了彭博社的后勤支持以及 PSF 和一些与会者的雇主的资金支持（例如 Dropbox 支付了我的酒店和机票）。特别感谢 Emily Morehouse 和 Pablo Galindo Salgado，他们在编写工具和测试方面非常有帮助。该项目的下一步是编写性能基准，然后我们将向此语法添加操作，以便它可以创建可由 CPython 字节码编译器编译的 AST 树。激动人心的时刻！

本文及代码的许可：CC BY-NC-SA 4.0

实现 PEG 特性

猜你喜欢

热点阅读