11

我定义了以下最小的 Peg.js 语法：

start  =  "A1" / "A123"

您可以在沙盒中尝试。

我本来希望匹配“A1”和“A123”（根据我对回溯如何工作的概念）。但事实并非如此：语法识别“A1”但不识别“A123”。

注意：我不是在寻找相关问题“如何将简单的语法转换为适用于 PEG.js 的东西”中的“颠倒你的术语的顺序”的建议（预期为“a”，但找到了“a”）。相反，我希望了解我所看到的行为，以及为什么 Peg.js 的回溯不适用于这种情况。有关为什么颠倒我的术语顺序没有帮助的解释，请参阅下面更现实的示例。

举一个更现实的例子，考虑单位解析。语法应该识别带有可选前缀的公制单位（如“m”、“mol”），如“mm”、“mmol”，以及非公制单位，如“yr”、“week”或“mo”。

以下 Peg.js 语法无法识别“mol”，因为它在使用“mo”时会出错，并且不会回溯。（更改术语的顺序无济于事；或者更确切地说，会导致“mo”以牺牲“mol”或“mmol”为代价而被识别。）

start  =  nonmetric / metric / prefix metric
metric = "mol" / "l" / "m" / "g"
nonmetric = "yr" / "mo" / "week" / "day" / "hour"
prefix = "m" / "k" / "c"

我可以在 Antlr 中成功地做类似的事情：

grammar units;
start  :  nonmetric | metric | prefix metric;
metric : 'mol' | 'l' | 'm' | 'g';
nonmetric : 'yr' | 'mo' | 'week' | 'day' | 'hour';
prefix : 'm' | 'k' | 'c';
4

2 回答 2

15

问题在于回溯的概念。PEG 解析器不像其他递归下降解析器或Prolog那样回溯。相反，当面临选择时，PEG 解析器将尝试所有选项，直到成功。一旦成功，无论如何调用规则，它都会提交。

来自维基百科的文章：

然而，与上下文无关文法和正则表达式不同的是，这些运算符总是表现得很贪婪，尽可能多地消耗输入并且从不回溯。

您在复杂情况下所要求的与此问题中所要求的相同。到目前为止的答案是肯定的：您必须调整 PEG 语法中的规则，以确保总是首先匹配最长的选项，即使结果是有点难看的语法。

调整 PEG 语法的一种方法是使用前瞻（这是前瞻在 PEG 中具有特色的主要原因之一）：

start  =  nonmetric / metric / prefix metric
metric = "mol" / "l" / !"mo" "m" / "g"
nonmetric = "yr" / !"mol" "mo" / "week" / "day" / "hour"
prefix = !("mol"/"mo") "m" / "k" / "c"
于 2014-07-17T17:09:02.983 回答
3

这是设计使然。您可以指定将用于匹配的正确顺序或规则。

原始白皮书中的引述：

当然，这些工具不会使语言语法设计变得容易。不必确定 CFG 中的两个可能的替代方案是否不明确，PEG 为语言设计者提供了类似的挑战，即确定是否可以在不影响语言的情况下重新排序 '/' 表达式中的两个替代方案。这个问题通常是显而易见的，但有时不是，而且通常无法确定。然而，与发现 CFG 中的歧义一样，我们希望找到自动算法来在常见情况下保守地识别顺序敏感度或不敏感度。

在这个简单的例子中，PEG.js 可能会更聪明一些，并且可以识别您指定的规则是不明确的。可能值得问作者。

于 2014-08-06T05:10:24.483 回答