Как предотвратить жадность с PetitParser? - PullRequest
Новая
       41

Как предотвратить жадность с PetitParser?

5 голосов
/ 25 февраля 2012

Я пытаюсь реализовать BNF для 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).Это заставляет меня думать, что необязательный флаг устранения неоднозначности не работает должным образом, и что анализатор не пытается увидеть, анализирует ли он, не анализируя «е» как disambiguation, даже если это возможно.Это приводит к невозможности синтаксического анализа targetSquare, поэтому я не понимаю, почему PetitParser сдается.

1 Ответ

4 голосов
/ 25 февраля 2012

Грамматики синтаксического анализа выражений (технология синтаксического анализа, которую использует 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'.
...