← На главную

Pratt-парсинг полезно рассматривать как чёрный ящик

03.11.2026 20:07 · hackernews

Vinícius dos Santos Oliveira считает, что учебники по Pratt-парсингу слишком много внимания уделяют небольшому основному алгоритму и почти не объясняют свойства, важные на практике. Сам цикл занимает около девяти строк и с 1973 года не изменился, поэтому автор предлагает сначала воспринимать его как чёрный ящик, подобно quicksort или файловой системе.

Ключевой вопрос при разборе очередного токена: ожидается ли что-либо слева от него. Обработчик nud применяется, когда слева ничего не нужно, а led — когда уже есть левая часть выражения. В отличие от грамматик с продукционными правилами, семантические действия здесь привязаны непосредственно к терминальным токенам. Приоритеты операторов задаёт отдельная таблица binding power. Например, открывающая скобка вызова функции становится led, поскольку перед ней должно находиться выражение; похожим образом обрабатывается индексирование массива.

По словам автора, такое устройство даёт несколько практических преимуществ. Левая рекурсия, проблемная для LL(k), не возникает, потому что связанный токен уже извлечён перед вызовом обработчика. Движку не нужно перебирать альтернативы и выполнять откат: он смотрит на один токен, сравнивает числа и продолжает итерацию или рекурсию. Каждое семантическое действие выполняется один раз, поэтому в нём допустимы побочные эффекты без восстановления состояния после неудачного сопоставления. Автор использует это для резервирования имён в лексических областях, но предостерегает от чрезмерного усложнения кода.

Свободные места в таблицах становятся точками расширения грамматики: обработчики можно добавлять с учётом уже прочитанного текста, реализуя макросы или пользовательские операторы. Обработчик также способен заглядывать дальше одного токена и при необходимости вызывать другой парсер.

Ограничения тоже важны. Pratt требует отдельного лексера, не разбирает инструкции без сочетания с другими методами и не подходит для инкрементального разбора в стиле GLR. Автоматического обнаружения всех неоднозначностей при объединении грамматик нет. Поэтому статья не отменяет работу проектировщика языка, а предлагает другой способ организации парсера: сначала понять контракты nud, led и binding power, а уже потом при желании разбирать внутренний цикл.

Читать оригинал →