如何用PetitParser防止贪婪？

Question

我正在尝试在Pharo/PetitParser中实现BNF for EPD。

digit18 := $1 asParser / $2 asParser / $3 asParser / $4 asParser / $5 asParser / $6 asParser / $7 asParser / $8 asParser.
piecePromotion := $N asParser / $B asParser / $R asParser / $Q asParser.
promotion := ($= asParser) , piecePromotion.
fileLetter := ($a asParser / $b asParser / $c asParser / $d asParser / $e asParser / $f asParser / $g asParser / $h asParser).
targetSquare := fileLetter , digit18.
disambiguation := fileLetter / digit18.
pieceCode := ($N asParser / $B asParser / $R asParser / $Q asParser / $K asParser) optional.
castles := $O asParser, $- asParser, $O asParser, (($- asParser, $O asParser) optional) .
sanMove := (pieceCode, disambiguation optional, targetSquare, promotion optional, ($+ asParser / $# asParser) optional) "/ castles". "commented out because I'd be getting another error with this enabled"

然后，我尝试像这样解析：

element := PPUnresolvedParser new.

element def: ( sanMove ).
mse := element end.
mse parse: 'Re4'.

但是我得到了这个错误：

$h expected at 2 // btw these indexes seem to start at 0

如果我尝试将Ree4作为输入，它将成功解析为#($R $e #($e $4) nil nil)。这使我认为消除歧义的可选标志不能正常工作，解析器不会尝试在不将"e“解析为disambiguation的情况下进行解析，即使它可以解析。但这会导致无法解析强制targetSquare，所以我不明白为什么PetitParser会放弃。

Answer 1

Parsing Expression Grammars ( PetitParser正在使用的解析器技术)是贪婪的。这意味着，一旦成功地使用了某些东西，它们就永远不会回溯。在您的例子中，“消歧”规则被成功使用，因此解析器永远不会重试跳过它，即使解析器后来被卡住了。

BNF和PEG语法看起来很相似，但它们具有非常不同的语义。因此，您不能仅将BNF语法规则逐条转换为PetitParser。你必须仔细地安排选择(顺序很重要)。在您的特定示例中，您可以将sanMove更改为：

sanMove := pieceCode, ((targetSquare, promotion optional, ($+ asParser / $# asParser) optional) / (disambiguation optional, targetSquare, promotion optional, ($+ asParser / $# asParser) optional)).

有了这个规则，你的两个测试都会被解析：

sanMove end parse: 'Ree4'.
sanMove end parse: 'Re4'.