parsing - 如何使用 PetitParser 防止贪婪？

Question

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

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”解析为消歧的情况下进行解析，即使它可以是。但它导致无法解析强制 targetSquare，所以我不明白为什么 PetitParser 放弃。

Answer 1

Parsing Expression Grammars (PetitParser 使用的解析器技术)是贪婪的。这意味着一旦成功消耗了某些东西，他们就不会再回头。在您的情况下，规则“消歧”已成功使用，因此即使解析器稍后卡住，解析器也不会重试跳过它。

BNF 和 PEG 语法看起来很相似，但它们的语义却截然不同。因此，您不能将 BNF 语法规则逐条翻译为 PetitParser。您必须仔细安排选择(PEG 中的顺序很重要)。在您的特定示例中，您可以将 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'.