我了解并使用Bison/Yacc，在解析领域中，Packrat Parsing非常受关注。它是什么？学习它是否值得？
3个回答
37
在高层次上：
- Packrat解析器使用parsing expression grammars（PEGs）而非传统的context-free grammars（CFGs）。 - 通过使用PEG而非CFG，设置和维护Packrat解析器通常比传统的LR解析器更容易。 - 由于它们使用memoization，因此Packrat解析器在运行时通常使用更多的内存，而不是像LALR（1）和LR（1）这样的“经典”解析器。 - 像经典的LR解析器一样，Packrat解析器以线性时间运行。
从这个意义上说，你可以将Packrat解析器视为与LR系列解析器之间简单性/内存权衡的一种选择。相对于LR系列解析器，Packrat解析器需要更少理论上的理解解析器的内部工作原理，但在运行时使用更多资源。如果你处于内存丰富的环境中，只想快速构建一个简单的解析器，则Packrat解析可能是一个不错的选择。如果你在内存受限的系统上或想要获得最大的性能，则值得投资于LR系列解析器。
本答案的其余部分会稍微详细地介绍Packrat解析器和PEGs。
关于CFGs和PEGs：
许多传统解析器（以及许多现代解析器）使用context-free grammars。上下文无关语法由一系列规则组成，如下所示：
例如，第一行表示非终结符E可以被替换为
如果你从字符串E开始并按照上述语法规则操作，就可以使用+、*、括号和单个数字生成任何数学表达式。
无上下文文法是一种紧凑的表示字符串集合的方式。它们有着丰富而深入的理论。然而，它们有两个主要缺点。第一个缺点是，单独看一个CFG只定义了一组字符串，但不告诉你如何检查特定的字符串是否由语法生成。这意味着，特定CFG是否适合于一个好的解析器取决于解析器的具体工作方式，也就是说，语法作者可能需要熟悉他们的解析器生成器的内部工作原理，以了解对语法结构会产生什么限制。例如，LL(1)解析器不允许左递归，并要求左因子分解，而LALR(1)解析器则需要一些理解解析算法来消除移位/规约和规约/规约冲突。
第二个更大的问题是，语法可以是有歧义的。例如，上面的语法生成字符串2 + 3 * 4，但有两种方式。一种方式基本上得到了分组2 + (3 * 4)，这是预期的结果。另一种方式给我们(2 + 3) * 4，这不是预期的结果。这意味着语法作者要么需要确保语法是无歧义的，要么需要引入辅助于语法的优先级声明，告诉解析器如何解决冲突。这可能会有点麻烦。
Packrat解析器使用了一种称为解析表达式文法(PEGs)的无上下文文法替代方法。解析表达式文法在某些方面类似于CFG - 它们通过描述如何从（可能是递归的）较小部分组装这些字符串来描述字符串集合。在其他方面，它们像正则表达式：它们涉及由少量操作组合在一起的简单语句，用于描述更大的结构。
例如，这里是一个简单的PEG，用于上述相同类型的算术表达式：
为了理解这句话，让我们看一下第一行。和CFG一样，这一行表示两个选项之间的选择：你可以用F + E替换E，也可以用F替换E。然而，与常规CFG不同的是，这些选择有一个特定的顺序。具体来说，这个PEG可以被解读为“首先，尝试用F + E替换E。如果成功了，太好了！如果不行，尝试用F替换E。如果成功了，太好了！否则，我们尝试了所有的方法都没有成功，所以放弃。”
在这个意义上，PEG直接将解析如何进行编码到语法结构本身中。而CFG更抽象地表示“E可以被替换为以下任何一个”，PEG明确表示“要解析E，首先尝试这个，然后尝试这个，再尝试这个等等”。因此，对于PEG可以解析的任何给定字符串，PEG只能以一种方式解析它，因为一旦找到第一次解析，就停止尝试选项。
PEG和CFG一样需要一些时间来掌握。例如，抽象的CFG和许多CFG解析技术对左递归没有问题。例如，这个CFG可以用LR(1)解析器解析：
让我们先看看第一行。第一行说“要解析E，首先尝试读取E，然后是+，然后是F。如果失败，请尝试读取F。”那么它会如何尝试第一个选项呢？第一步是尝试解析E，这将通过首先尝试解析E来实现，现在我们陷入了无限循环中。糟糕。这称为左递归，并且在使用LL族解析器处理CFG时也会出现。
设计PEG时出现的另一个问题是需要正确获取有序选择。如果您来自上下文无关语法的世界，在那里选择是无序的，很容易意外地搞乱PEG。例如，考虑以下PEG：
现在，如果您尝试解析字符串2 * 3 + 4会发生什么？好吧：我们尝试解析E，它首先尝试解析F。
我们尝试解析F，它首先尝试解析T。
我们尝试解析T，它首先尝试读取一系列数字。这成功地读取了2。
我们已经成功读取了F。
因此，我们已经成功读取了E，所以我们应该完成了，但是有剩余的标记，解析失败。
问题在于，我们在尝试解析F + E之前首先尝试解析F，同样地，在尝试解析T * F之前首先尝试解析T。结果，我们基本上咬下了比我们可以检查的更少的东西，因为我们尝试在长表达式之前读取短表达式。
与构建LR或LL解析表的算法相比，packrat parsing算法在概念上非常简单。在高层次上，packrat解析器从起始符号开始，然后按顺序逐个尝试有序的选择，直到找到一个可行的选择。在处理这些选择时，可能需要匹配另一个非终止符，在这种情况下，它会在其余字符串上递归地尝试匹配该非终止符。如果特定选择失败，则解析器将回溯，然后尝试下一个产生式。
匹配任何一个单独的产生式并不那么困难。如果您看到一个终止符号，它要么匹配下一个可用的终止符号，要么不匹配。如果是，很好！匹配它并继续。如果没有，则报告错误。如果您看到一个非终止符号，那么（递归地）匹配该非终止符号，如果成功，则在非终止符号完成匹配的点之后继续搜索。
这意味着，更普遍地说，packrat解析器通过尝试解决以下问题来工作：
给定字符串中的某个位置和一个非终止符号，确定该非终止符号从该位置开始匹配字符串的多少部分（或者报告根本不匹配）。
在这里，请注意，“非终止符号匹配字符串的多少部分”的含义没有歧义。与传统CFG不同，其中一个非终止符可能在给定位置匹配多种不同的长度，PEGs中使用的有序选择确保如果在给定点有一些匹配，那么就恰好有一个匹配从该点开始。
- Packrat解析器使用parsing expression grammars（PEGs）而非传统的context-free grammars（CFGs）。 - 通过使用PEG而非CFG，设置和维护Packrat解析器通常比传统的LR解析器更容易。 - 由于它们使用memoization，因此Packrat解析器在运行时通常使用更多的内存，而不是像LALR（1）和LR（1）这样的“经典”解析器。 - 像经典的LR解析器一样，Packrat解析器以线性时间运行。
从这个意义上说，你可以将Packrat解析器视为与LR系列解析器之间简单性/内存权衡的一种选择。相对于LR系列解析器，Packrat解析器需要更少理论上的理解解析器的内部工作原理，但在运行时使用更多资源。如果你处于内存丰富的环境中，只想快速构建一个简单的解析器，则Packrat解析可能是一个不错的选择。如果你在内存受限的系统上或想要获得最大的性能，则值得投资于LR系列解析器。
本答案的其余部分会稍微详细地介绍Packrat解析器和PEGs。
关于CFGs和PEGs：
许多传统解析器（以及许多现代解析器）使用context-free grammars。上下文无关语法由一系列规则组成，如下所示：
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解析器使用了一种称为解析表达式文法(PEGs)的无上下文文法替代方法。解析表达式文法在某些方面类似于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一样，这一行表示两个选项之间的选择：你可以用F + E替换E，也可以用F替换E。然而，与常规CFG不同的是，这些选择有一个特定的顺序。具体来说，这个PEG可以被解读为“首先，尝试用F + E替换E。如果成功了，太好了！如果不行，尝试用F替换E。如果成功了，太好了！否则，我们尝试了所有的方法都没有成功，所以放弃。”
在这个意义上，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
然而，下面的PEG无法被packrat解析器解析（尽管后来对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会发生什么？好吧：
与构建LR或LL解析表的算法相比，packrat parsing算法在概念上非常简单。在高层次上，packrat解析器从起始符号开始，然后按顺序逐个尝试有序的选择，直到找到一个可行的选择。在处理这些选择时，可能需要匹配另一个非终止符，在这种情况下，它会在其余字符串上递归地尝试匹配该非终止符。如果特定选择失败，则解析器将回溯，然后尝试下一个产生式。
匹配任何一个单独的产生式并不那么困难。如果您看到一个终止符号，它要么匹配下一个可用的终止符号，要么不匹配。如果是，很好！匹配它并继续。如果没有，则报告错误。如果您看到一个非终止符号，那么（递归地）匹配该非终止符号，如果成功，则在非终止符号完成匹配的点之后继续搜索。
这意味着，更普遍地说，packrat解析器通过尝试解决以下问题来工作：
给定字符串中的某个位置和一个非终止符号，确定该非终止符号从该位置开始匹配字符串的多少部分（或者报告根本不匹配）。
在这里，请注意，“非终止符号匹配字符串的多少部分”的含义没有歧义。与传统CFG不同，其中一个非终止符可能在给定位置匹配多种不同的长度，PEGs中使用的有序选择确保如果在给定点有一些匹配，那么就恰好有一个匹配从该点开始。
如果您学过动态规划, 您可能会意识到这些子问题可能会相互重叠。实际上，在具有k个非终端符号和长度为n的字符串的PEG中，仅有Θ(kn)个可能的不同子问题：每个组合都有一个起始位置和非终结符。这意味着，原则上，您可以使用动态规划预计算所有可能的位置/非终结符解析匹配表，并拥有一个非常快速的解析器。Packrat解析器实质上是这样做的，但使用的是记忆化而不是动态规划。这意味着它不一定会尝试填充所有的表格条目，而只是在解析语法时遇到的条目。
由于每个表格条目都可以在常数时间内完成填充（对于每个非终结符，对于固定的PEG，只有有限多个产生式可尝试），因此解析器最终以线性时间运行，与LR解析器的速度匹配。
这种方法的缺点是所使用的内存量。具体来说，记忆表格可能会记录输入字符串中每个位置的多个条目，需要使用与PEG大小和输入字符串长度成比例的内存。相比之下，LL或LR解析只需要与解析堆栈的大小成比例的内存，而堆栈大小通常远小于完整字符串的长度。
话虽如此，在这种更差的内存性能中所进行的权衡是不需要学习Packrat解析器的内部工作原理。您只需阅读关于PEG的资料并从中获取信息即可。
希望这有所帮助！
- templatetypedef
2
我认为
T -> D* / (E) 应该是 T -> D+ / (E)，你不能有空的数字。 - Andrew Savinykh好的，已修复！ - templatetypedef
2
Pyparsing是一个纯Python解析库，支持packrat解析，因此您可以看到它是如何实现的。Pyparsing使用记忆化技术来保存先前针对特定语法表达式在输入文本中特定位置的解析尝试。如果语法涉及在该位置重试相同的表达式，则跳过昂贵的解析逻辑并仅从记忆化缓存返回结果或异常。
在pyparsing wiki的FAQ页面上有更多信息，其中还包括链接回Bryan Ford关于packrat解析的原始论文。
- PaulMcG
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接
lazy vals（Scala解析器组合器），那么是否已经实现了packrat parsing？换句话说，如果我正在使用lazy val来缓存已解析的标记，那么我是否已经在使用packrat parsing？ - Kevin Meredith