Pratt Parser: элегантный парсинг выражений

Vaughan Pratt опубликовал этот алгоритм в 1973 году. Его почти забыли. В 2007 году Дуглас Крокфорд переоткрыл его и написал статью 'Top Down Operator Precedence'. В 2012 году TypeScript выбрал Pratt для парсинга выражений. В 2015 - Rust. В 2019 - Go 1.13. Хороший алгоритм не умирает.

• TypeScript compiler: Pratt parsing для 18 уровней приоритетов JavaScript выражений
• Rustc: expression parsing через Pratt в parser/expr.rs - ~600 строк вместо тысяч grammar rules
• V8 (JavaScript engine): аналог Pratt в парсере для быстрой обработки выражений
• Prettier (code formatter): Pratt-like подход для понимания приоритетов при форматировании

Приоритеты операторов: почему это сложно

`1 + 2 * 3` должно дать 7, а не 9. Все знают это с первого класса. Но попробуйте написать парсер который это корректно обрабатывает - и вы поймёте, почему в 1973 Vaughan Pratt придумал целый алгоритм для этой «заметной» задачи.

**Классическая проблема**: рекурсивный спуск для выражений требует отдельного уровня рекурсии на каждый приоритет оператора. 5 приоритетов = 5 функций (expr, term, factor, unary, primary). Добавить новый приоритет - рефакторинг всей грамматики. TypeScript поддерживает 18 уровней приоритетов. 18 функций?

**Левая и правая ассоциативность** - отдельная проблема. `a + b + c` = `(a+b)+c` (левая). `a = b = c` = `a=(b=c)` (правая). В классическом парсере это решается через рекурсию: левая ассоциативность - итерация, правая - рекурсивный вызов. В Pratt - через разные значения left и right binding power.

Алгоритм Pratt: binding power и nud/led

Идея Pratt проста и гениальна: каждый токен имеет **binding power** - "силу притяжения" к соседним токенам. `*` притягивает сильнее чем `+`. Алгоритм: пока следующий оператор имеет большую binding power - продолжаем строить правый операнд.

Pratt Parser в реальных компиляторах

TypeScript compiler, Rust compiler (rustc), Go parser - все используют Pratt parsing для выражений. Причина: алгоритм легко расширяется новыми операторами без изменения существующего кода. Добавить оператор `??` (nullish coalescing) в TypeScript - добавить строку в таблицу binding power.

Расширения: постфиксы, тернарный оператор, mixfix

Красота Pratt parsing - в обработке любой синтаксической формы через nud/led без изменения core алгоритма. Индексирование `a[i]`, вызов `f(x)`, тернарный `a ? b : c`, optional chaining `a?.b` - всё это led-обработчики с нужными binding power.

Ключевые идеи

• Pratt Parser: каждый токен имеет binding power - 'силу притяжения' к соседям
• nud (null denotation): обработка токена без левого контекста (prefix, literals)
• led (left denotation): обработка с левым операндом (infix, postfix)
• Правоассоциативность: передать bp-1 вместо bp при рекурсии
• Расширяемость: новый оператор = новая строка в таблице, без изменения core алгоритма

Связанные темы

Pratt Parser строит AST и является основой expression parsing в современных компиляторах.

• Рекурсивный спуск — Pratt parsing - эволюция recursive descent для expression parsing
• AST — Pratt Parser строит AST-узлы - следующий этап компиляции

Вопросы для размышления

• Как реализовать string template literals (`${expr}`) в Pratt Parser? Какой тип токена и обработчик нужны?
• В чём разница между Pratt Parser и Shunting Yard алгоритмом Дейкстры? Когда выбрать каждый?
• Как добавить поддержку pipe оператора `|>` (stage 2 proposal) в существующий Pratt Parser для JavaScript?

Связанные уроки

• comp-11-recursive-descent — Рекурсивный спуск - база для понимания Pratt parsing
• comp-10-cfg — Грамматики выражений - контекст для приоритетов операторов
• comp-16-ast — Pratt parser строит AST - следующий урок
• comp-12-lr-parsing — LR parsing - альтернативный подход для той же задачи
• alg-21-dp