什么是packrat解析？

Question

我知道并使用野牛/ yacc.但是在解析世界时,有很多关于packrat解析的嗡嗡声.

它是什么？值得研究吗？

Answer 1

Packrat解析是一种为解析表达式语法(PEG)提供渐近更好的性能的方法; 特别是对于PEG,可以保证线性时间分析.

从本质上讲,Packrat解析只是意味着缓存子表达式是否在测试时在字符串中的当前位置匹配 - 这意味着如果当前尝试使字符串适合表达式失败,则尝试拟合其他可能的表达式可以从中受益字符串中已经过测试的点上的子表达式的已知通过/失败.

Answer 2

在高层次上：

• Packrat 解析器使用解析表达式文法(PEG) 而不是传统的上下文无关文法(CFG)。

• 通过使用 PEG 而不是 CFG，通常比传统的LR 解析器更容易设置和维护 Packrat解析器。

• 由于它们如何使用memoization，packrat 解析器在运行时通常比“经典”解析器（如 LALR(1) 和 LR(1) 解析器）使用更多的内存。

• 像经典的 LR 解析器一样，packrat 解析器以线性时间运行。

从这个意义上说，您可以将 Packrat 解析器视为与 LR 系列解析器的简单性/内存权衡。Packrat 解析器比 LR 系列解析器需要更少的解析器内部工作理论理解，但在运行时使用更多资源。如果您处于内存充足的环境中，并且只想将一个简单的解析器放在一起，那么 Packrat 解析可能是一个不错的选择。如果您使用的是内存受限的系统或想要获得最大性能，那么投资 LR 系列解析器可能是值得的。

此答案的其余部分对 Packrat 解析器和 PEG 进行了更详细的概述。

关于 CFG 和 PEG

许多传统解析器（和许多现代解析器）使用上下文无关文法。上下文无关文法由一系列规则组成，如下所示：

E -> E * E | E + E | (E) | N
N -> D | DN
D -> 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9

例如，第一行说非终结符E 可以用E * E、 或E + E、 或(E)、 或 替换N。第二行表示 N 可以替换为D或DN。最后一行说D可以用任何单个数字替换。

如果以字符串 E 开头并遵循上述语法中的规则，则可以使用 +、*、括号和单个数字生成任何数学表达式。

上下文无关文法是一种表示字符串集合的紧凑方式。他们有丰富且易于理解的理论。但是，它们有两个主要缺点。第一个是，CFG 本身定义了一组字符串，但没有告诉您如何检查特定字符串是否由语法生成。这意味着一个特定的 CFG 是否适合一个好的解析器取决于解析器如何工作的细节，这意味着语法作者可能需要熟悉他们的解析器生成器的内部工作，以了解对可以出现各种语法结构。例如，LL(1) 解析器不允许左递归并需要左因子分解，而 LALR(1) 解析器需要对解析算法有一定的了解，以消除移位/减少和减少/减少冲突。

第二个更大的问题是语法可能有歧义。例如，上面的语法生成字符串 2 + 3 * 4，但有两种方式。以一种方式，我们基本上得到了分组 2 + (3 * 4)，这就是我们想要的。另一个给了我们 (2 + 3) * 4，这不是什么意思。这意味着语法作者要么需要确保语法是明确的，要么需要引入辅助语法的优先级声明来告诉解析器如何解决冲突。这可能有点麻烦。

Packrat 解析器使用称为解析表达式文法(PEG) 的上下文无关文法的替代方案。解析表达式语法在某些方面类似于 CFG - 它们通过说明如何从（可能是递归的）较小部分组装这些字符串来描述字符串的集合。在其他方面，它们就像正则表达式：它们涉及由描述较大结构的一小部分操作组合在一起的更简单的语句。

例如，这里有一个简单的 PEG，用于上面给出的相同类型的算术表达式：

E -> F + E / F
F -> T * F / T
T -> D* / (E)
D -> 0 / 1 / 2 / 3 / 4 / 5 / 6 / 7 / 8 / 9

要了解这说明了什么，让我们看看第一行。与 CFG 一样，此行表示在两个选项之间进行选择：您可以替换E为F + E或F。但是，与常规 CFG 不同的是，这些选择有特定的顺序。具体而言，该PEG可以读作“第一，尝试更换E与F + E如果这样的作品，太棒了！如果还是不行，请尝试更换。E用F。而如果这样的作品，伟大的！否则，我们尝试了一切，这没”不工作，所以放弃。”

从这个意义上说，PEG 直接将解析的方式编码到语法结构本身中。CFG 更抽象地表示“一个 E 可以被以下任何一个替换”，而 PEG 则明确表示“要解析一个 E，首先尝试这个，然后这个，然后这个，等等”。因此，对于 PEG 可以解析的任何给定字符串，PEG 可以完全以一种方式解析它，因为一旦找到第一个解析，它就会停止尝试选项。

PEG 与 CFG 一样，可能需要一些时间才能掌握。例如，抽象中的 CFG——以及许多 CFG 解析技术——在左递归方面没有问题。例如，这个 CFG 可以用 LR(1) 解析器解析：

E -> E + F | F
F -> F * T | T
T -> (E) | N
N -> ND | D
D -> 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9

但是，packrat 解析器无法解析以下 PEG（尽管后来对 PEG 解析的改进可以纠正此问题）：

E -> E + F / F
F -> F * T / T
T -> (E) / D*
D -> 0 / 1 / 2 / 3 / 4 / 5 / 6 / 7 / 8 / 9

让我们看看第一行。第一行说“要解析 E，首先尝试读取 E，然后是 +，然后是 F。如果失败，请尝试读取 F。” 那么它将如何尝试第一个选项呢？第一步是尝试解析一个 E，这将首先尝试解析一个 E，现在我们陷入了一个无限循环。哎呀。这称为左递归，在使用 LL 系列解析器时也会出现在 CFG 中。

设计 PEG 时出现的另一个问题是需要正确选择有序的选项。如果您来自上下文无关语法领域，这里的选择是无序的，那么很容易不小心弄乱 PEG。例如，考虑这个 PEG：

E -> F / F + E
F -> T / T * F
T -> D* / (E)
D -> 0 / 1 / 2 / 3 / 4 / 5 / 6 / 7 / 8 / 9

现在，如果您尝试解析字符串 2 * 3 + 4 会发生什么？好：

• 我们尝试解析一个 E，它首先尝试解析一个 F。
• 我们尝试解析一个 F，它首先尝试解析一个 T。
• 我们尝试解析 T，它首先尝试读取一系列数字。这成功地读取了 2。
• 我们已经成功读取了 F。
• 所以我们已经成功读取了一个 E，所以我们应该在这里完成，但是有剩余的标记并且解析失败。

这里的问题是我们首先尝试了解析F之前F + E，同样首先尝试解析T之前解析T * F。结果，我们基本上比我们可以检查的少，因为我们尝试在较长的表达式之前读取较短的表达式。

您是否发现 CFG 具有模糊性和优先级声明，比 PEG 更容易或更难，具有参与选择排序，这主要是个人偏好的问题。但是很多人报告发现 PEG 比 CFG 更容易使用，因为它们更机械地映射到解析器应该做什么。与其说“这是我想要的字符串的抽象描述”，不如说“这是我希望您尝试的顺序”，这更接近于解析的工作方式。

Packrat 解析算法

与构建 LR 或 LL 解析表的算法相比，packrat 解析使用的算法在概念上非常简单。在高层次上，packrat 解析器从开始符号开始，然后依次尝试有序的选择，一次一个，直到找到一个有效的选择。当它完成这些选择时，它可能会发现它需要匹配另一个非终结符，在这种情况下，它会递归地尝试在字符串的其余部分匹配该非终结符。如果特定选择失败，解析器会回溯，然后尝试下一个产品。

匹配任何一个单独的产品并不难。如果您看到一个终端，它要么与下一个可用终端匹配，要么不匹配。如果是这样，太好了！匹配它并继续前进。如果不是，则报告错误。如果您看到一个非终结符，则（递归地）匹配该非终结符，如果它成功，则在非终结符完成匹配之后的点继续搜索的其余部分。

这意味着，更一般地，packrat 解析器通过尝试解决以下形式的问题来工作：

给定字符串中的某个位置和一个非终结符，确定从该位置开始的非终结符匹配的字符串有多少（或报告它根本不匹配。）

在这里，请注意“非终结符匹配多少字符串”的含义没有歧义。与传统的 CFG 不同，在传统的 CFG 中，非终结符可能在给定位置以多种不同的长度匹配，PEG 中使用的有序选择确保如果从给定点开始有匹配，那么从该点开始正好有一个匹配。

如果您研究过动态规划，您可能会意识到这些子问题可能相互重叠。事实上，在具有k非终端和长度为 的字符串的PEG 中，n只有 ?(kn) 个可能的不同子问题：一个用于起始位置和非终端的每个组合。这意味着，原则上，您可以使用动态编程来预先计算所有可能的位置/非终结符解析匹配的表，并拥有一个非常快速的解析器。Packrat 解析本质上是这样做的，但使用记忆化而不是动态编程。这意味着它不一定会尝试填充所有表条目，只会尝试填充在解析语法过程中实际遇到的条目。

由于每个表条目可以在恒定时间内填充（对于每个非终结符，只有有限多个产生式可以尝试固定 PEG），解析器最终以线性时间运行，与 LR 解析器的速度相匹配。

这种方法的缺点是使用的内存量。具体来说，记忆表可能会在输入字符串的每个位置记录多个条目，需要与 PEG 的大小和输入字符串的长度成比例的内存使用。将此与 LL 或 LR 解析形成对比，后者只需要与解析堆栈大小成比例的内存，通常比完整字符串的长度小得多。

话虽如此，但由于不需要了解 Packrat 解析器如何工作的内部工作原理，因此在更差的内存性能方面的权衡被抵消了。您可以阅读 PEG 并从那里获取内容。

希望这可以帮助！

Answer 3

Pyparsing是一个纯Python解析库，支持packrat解析，所以你可以看看它是如何实现的。Pyparsing 使用记忆技术来保存输入文本中特定位置的特定语法表达式的先前解析尝试。如果语法涉及在该位置重试相同的表达式，它会跳过昂贵的解析逻辑，只从记忆缓存返回结果或异常。

pyparsing wiki 的FAQ 页面上有更多信息，其中还包括返回 Bryan Ford 关于 Packrat 解析的原始论文的链接。