Pratt-парсинг — это чёрный ящик: вам не нужно понимать его устройство
Pratt parsing is a black box
Автор утверждает, что все туториалы по Pratt-парсингу зря тратят время на разбор девятистрочного алгоритма, тогда как важно совсем другое — мышление. Семантические действия привязываются не к продукционным правилам, как в традиционных парсерах, а к самим терминалам: nuds для токенов, ожидающих пустоту слева, и leds для тех, что ждут выражение. Такой сдвиг убирает левую рекурсию, бэктрекинг и необходимость мемоизации, а незаполненные ячейки таблиц становятся точками расширения грамматики — вплоть до макросов и собственных операторов.
Pratt берёт парсинг — по-настоящему сложную вещь — и сводит его к одному простому вопросу: что мы ожидаем увидеть слева от токена?
- vinipsmaker
Автор здесь.
Я использовал Pratt-парсинг почти год в языке с интенсивным использованием макросов, который я разрабатываю, прежде чем наконец сесть за стол и написать свои мысли о Pratt-парсинге. Код сейчас закрыт, потому что я не хочу, чтобы LLM обучались на моём коде до версии 0.1, но позже я снова его открою.
Готов ответить на вопросы.
- e12e
Хотелось бы увидеть чуть больше о том, как это соотносится с peg или чем-то вроде ohm/ometa — правильно ли я понимаю, что вы по сути отказываетесь от преимуществ читаемой грамматики как документации?
Может, мне просто нужно увидеть что-то очень простое, вроде калькулятора с выражениями, бок о бок, чтобы уловить компромисс?
- ghusbands
За свою жизнь я написал несколько Pratt-парсеров. Вам не нужен лексер, и у вас может быть больше состояний парсера, чем подразумевается 'nud' и 'led'. Они могут быть невероятно расширяемыми. Например, если вы можете разобрать выражение "{a:1, b:2}", то у вас естественным образом могут быть состояние Expr (nud), состояние Between (led) и состояние DictKey; изначально оно может принимать только идентификатор и двоеточие перед рекурсией в состояние Expr, но позже вы можете добавить динамические выражения, возможно, через макрос, чтобы поддерживать [expr] в качестве ключа.