在高层次上:
- 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会发生什么?好吧:
我们尝试解析E,它首先尝试解析F。
我们尝试解析F,它首先尝试解析T。
我们尝试解析T,它首先尝试读取一系列数字。这成功地读取了2。
我们已经成功读取了F。
因此,我们已经成功读取了E,所以我们应该完成了,但是有剩余的标记,解析失败。
问题在于,我们在尝试解析F + E之前首先尝试解析F,同样地,在尝试解析T * F之前首先尝试解析T。结果,我们基本上咬下了比我们可以检查的更少的东西,因为我们尝试在长表达式之前读取短表达式。
与构建LR或LL解析表的算法相比,packrat parsing算法在概念上非常简单。在高层次上,packrat解析器从起始符号开始,然后按顺序逐个尝试有序的选择,直到找到一个可行的选择。在处理这些选择时,可能需要匹配另一个非终止符,在这种情况下,它会在其余字符串上递归地尝试匹配该非终止符。如果特定选择失败,则解析器将回溯,然后尝试下一个产生式。
匹配任何一个单独的产生式并不那么困难。如果您看到一个终止符号,它要么匹配下一个可用的终止符号,要么不匹配。如果是,很好!匹配它并继续。如果没有,则报告错误。如果您看到一个非终止符号,那么(递归地)匹配该非终止符号,如果成功,则在非终止符号完成匹配的点之后继续搜索。
这意味着,更普遍地说,packrat解析器通过尝试解决以下问题来工作:
给定字符串中的某个位置和一个非终止符号,确定该非终止符号从该位置开始匹配字符串的多少部分(或者报告根本不匹配)。
在这里,请注意,“非终止符号匹配字符串的多少部分”的含义没有歧义。与传统CFG不同,其中一个非终止符可能在给定位置匹配多种不同的长度,PEGs中使用的有序选择确保如果在给定点有一些匹配,那么就恰好有一个匹配从该点开始。
如果您学过动态规划, 您可能会意识到这些子问题可能会相互重叠。实际上,在具有k
个非终端符号和长度为n
的字符串的PEG中,仅有Θ(kn)个可能的不同子问题:每个组合都有一个起始位置和非终结符。这意味着,原则上,您可以使用动态规划预计算所有可能的位置/非终结符解析匹配表,并拥有一个非常快速的解析器。Packrat解析器实质上是这样做的,但使用的是记忆化而不是动态规划。这意味着它不一定会尝试填充所有的表格条目,而只是在解析语法时遇到的条目。
由于每个表格条目都可以在常数时间内完成填充(对于每个非终结符,对于固定的PEG,只有有限多个产生式可尝试),因此解析器最终以线性时间运行,与LR解析器的速度匹配。
这种方法的缺点是所使用的内存量。具体来说,记忆表格可能会记录输入字符串中每个位置的多个条目,需要使用与PEG大小和输入字符串长度成比例的内存。相比之下,LL或LR解析只需要与解析堆栈的大小成比例的内存,而堆栈大小通常远小于完整字符串的长度。
话虽如此,在这种更差的内存性能中所进行的权衡是不需要学习Packrat解析器的内部工作原理。您只需阅读关于PEG的资料并从中获取信息即可。
希望这有所帮助!
lazy vals
(Scala解析器组合器),那么是否已经实现了packrat parsing
?换句话说,如果我正在使用lazy val
来缓存已解析的标记,那么我是否已经在使用packrat parsing
? - Kevin Meredith