node.js - 回溯在 peg.js 中是如何工作的(有例子)？

Question

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

start  =  "A1" / "A123"

你可以试试in the sandbox .

我希望匹配“A1”和“A123”(根据我对回溯工作原理的理解)。但事实并非如此:语法识别“A1”但不识别“A123”。

注意:我不是在寻找相关问题 How to transform a simple grammar into something which works in PEG.js (expected "a" but "a" found) 中的“颠倒条款顺序”的建议。 .相反，我想了解我所看到的行为，以及为什么 Peg.js 的回溯不适用于这种情况。有关为什么颠倒我的术语顺序没有帮助的解释，请参阅下面更实际的示例。

---

有关更实际的示例，请考虑单位解析。语法应该识别带有可选前缀的公制单位(如“m”、“mol”)，如“mm”、“mmol”，以及非公制单位，如“yr”、“week”或“mo”。

以下 Peg.js 语法无法识别“mol”，因为它在使用“mo”时被绊倒，并且不会回溯。 (更改术语的顺序没有帮助；或者更确切地说，将导致以牺牲“mol”或“mmol”为代价来识别“mo”。)

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';

Answer 1

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

来自Wikipedia article :

Unlike in context-free grammars and regular expressions, however, these operators always behave greedily, consuming as much input as possible and never backtracking.

您在复杂情况下的要求与 this question 中的要求相同.到目前为止，答案是是的:您必须调整 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"