node.js – 回溯如何在peg.js中工作(带示例)?

我已经定义了以下最小的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”,并且不会回溯. (改变术语的顺序没有帮助;或者更确切地说,将导致“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';
问题在于回溯的概念. 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"
本站公众号
   欢迎关注本站公众号,获取更多程序园信息
开发小院