Парсеры Пратта

[vak]

Статья проштудировать на будущее.

http://journal.stuffwithstuff.com/2011/03/19/pratt-parsers-expression-parsing-made-easy/

Comments

[x86128]

Доброго времени суток.

Будущее зреет лет 10 как правило :).
Пользуясь случаем подкину дровишек:

1) https://gist.github.com/yelouafi/556e5159e869952335e01f6b473c4ec1 - на пальцах
2) https://github.com/true-grue/raddsl - вариант на Python
3) https://crates.io/crates/pratt - реализация на Rust

[spamsink]

Интересно, насколько бы сократился Паскаль-компилятор, если переписать его парсер таким образом. Вопрос ещё и в том, как в парсере Пратта обстоит дело с диагностикой ошибок и восстановлением после них.

[vak]

Отличные ссылочки, спасибо. Когда-нибудь займусь при случае.

[x86128]

На сколько мне известно, с диагностикой там плохо. Также плохо то, что там много "откатов" при неудачном шаге и на прямую такие парсеры не используются, т.е. практическое применение достигается только если сделать что-то типа мемоизации/кеша (например лексических токенов с типами). Т.е. сложность как бы не O(n^2) (могу ошибаться).

Компилятор Паскаля сократится, конечно, но засчет утраты диагностики во время парсинга. Но после парсинга надо еще выполнить трансляцию и если это сделать, например, так как прделожено в 2) (с переписыванием термов/замены узлов дерева) то добавятся еще проблемы с дебагом правил трансляции узлов в маш.код.

Поэтому, для реализации игрушечных компиляторов для спец архитектур подойдет хорошо, а вот для больших грамматик - нет. Это подтверждается там что в GCC или Rust ручной режим парсинга/компиляции с промежуточными стадиями различных оптимизаций (без всяких там бизонов и PEG-ов). :))))))))

[spamsink]

В существующем компиляторе, строго говоря, с восстановлением после ошибок так себе. Иногда одна ошибка вызывает чуть не десяток диагностик, только первая из которых имеет смысл.

[sab123]

Погодите, а где там откаты? В примере в статье я не вижу откатов. Насколько я понял статью, там по сути делается ручной разбор для LR(1) вместо LL(1), т.е. решение о том, заканчивать разбор правила или проолжать, смещается на конец правила. Но как только оно принято, то уже не меняется.

Ну, и как всегда грамматика переписывается так, чтобы в ней у всех правил был уникальный префикс, вместо

exp : exp "+" exp
exp : exp "*" exp

пишется

exp : exp tail
tail : "+" exp
tail : "*" exp