Интуиция за Pratt parsing: как работают приоритеты операторов

Перевод статьи Intuiting Pratt parsing. Автор: Louis.

Вы знаете, что a + b * c + d вычисляется как a + (b * c) + d. Но как объяснить это машине? Как закодировать правила приоритета операторов так точно, чтобы парсер сам правильно строил дерево разбора?

Pratt parsing — элегантный алгоритм, придуманный Воном Праттом в 1973 году. Он лежит в основе парсеров многих современных языков, но его описания часто сводятся к магическим таблицам приоритетов без объяснения, почему это работает. Эта статья строит интуицию с нуля.

Абстрактное синтаксическое дерево

Наиболее распространённое решение для разбора выражений — абстрактное синтаксическое дерево (AST, Abstract Syntax Tree). В AST каждый оператор стоит над своими операндами. Вычисление идёт снизу вверх: сначала обрабатываются дочерние узлы, затем операция над ними.

Для выражения a + b * c + d правильное AST выглядит так:

			    +
   / \
  +   d
 / \
a   *
   / \
  b   c
		

Узел * находится глубже, чем +, — это и отражает более высокий приоритет умножения. При вычислении сначала перемножаются b * c, результат складывается с a, затем прибавляется d.

Как приоритет влияет на форму дерева

Здесь кроется главная интуиция Pratt parsing. Приоритет операторов напрямую определяет, в какую сторону «наклоняется» дерево:

• Убывающий приоритет (например, * + ==) — дерево наклонено влево: операторы с большим приоритетом оказываются глубже.
• Возрастающий приоритет (например, == + *) — дерево наклонено вправо.
• Равный приоритет — по соглашению левая ассоциативность, дерево наклоняется влево.

Рассмотрим промежуточное состояние разбора. Пусть мы уже построили дерево I для выражения (a > b + c * d) — это правонаклонное дерево: > наверху, * в самом низу.

Теперь встречаем следующий оператор. Куда вставить новый узел? Зависит от приоритета:

• [I] * e — приоритет * не меньше приоритета * в дереве, вставляем в самый глубокий узел.
• [I] + e — приоритет + ниже *, но выше >, поднимаемся по хребту выше узла *.
• [I] == e — приоритет == ниже всего дерева, всё дерево I становится левым потомком.

Ключевое наблюдение: когда встречается оператор с меньшим приоритетом, мы поднимаемся по правому хребту дерева, собирая узлы с более высоким приоритетом. Это и есть Pratt parsing — алгоритм, который реализует именно этот подъём по хребту.

От интуиции к коду

Начнём с простого случая — правонаклонного дерева. Каждый оператор правоассоциативен, приоритет не учитывается:

			def parse():
    left = leaf()
    if peek() is not None:
        op = advance()
        right = parse()
        return Node(op, left, right)
    return left
		

Здесь leaf() читает следующий терминал (число или переменную), peek() смотрит на текущий токен без продвижения, advance() читает и сдвигает позицию.

Добавляем приоритет. Рекурсивный вызов передаёт приоритет текущего оператора как порог — это ограничивает, какие операторы следующий уровень может «захватить»:

			def parse(prev_prec=0):
    left = leaf()
    if prec(peek()) > prev_prec:
        op = advance()
        right = parse(prec(op))
        return Node(op, left, right)
    return left
		

Это уже работает для правоассоциативных операторов. Но у нас if — разобрали один оператор и вышли. Для левоассоциативных нужен цикл:

Полный Pratt parser

			def parse(prev_prec=0):
    left = leaf()
    while prec(peek()) > prev_prec:
        op = advance()
        right = parse(prec(op))
        left = Node(op, left, right)
    return left
		

Замена if на while — это и есть процедура подъёма по хребту дерева. Цикл продолжается, пока следующий оператор имеет достаточно высокий приоритет, чтобы «захватить» левую часть. Как только приоритет падает — выходим, и текущее поддерево передаётся вверх по стеку вызовов.

Правая ассоциативность через binding power

До сих пор у нас одно число приоритета на оператор. Но для управления ассоциативностью нужно различать, насколько «сильно» оператор притягивает операнды слева и справа. Вводятся два понятия:

• LBP (left binding power) — сила притяжения левого операнда.
• RBP (right binding power) — сила притяжения правого операнда.

Правила ассоциативности через binding power:

• Левоассоциативные операторы (+, *): LBP == RBP. Правый рекурсивный вызов получает тот же приоритет — следующий оператор с таким же приоритетом не захватывается, строится левое дерево.
• Правоассоциативные операторы (**, =): RBP = LBP − 1. Правый рекурсивный вызов получает чуть меньший приоритет — следующий оператор с таким же приоритетом захватывается, строится правое дерево.

			def parse(prev_prec=0):
    left = leaf()
    while lbp(peek()) > prev_prec:
        op = advance()
        right = parse(rbp(op))
        left = Node(op, left, right)
    return left
		

Это финальная версия Pratt parser. Всего 8 строк кода — и корректный разбор всех операторов с любым приоритетом и ассоциативностью.

Итог

Pratt parsing — не хитрый трюк, а следствие простой геометрической интуиции. Деревья разбора наклоняются влево или вправо в зависимости от приоритета операторов. Когда встречается оператор с меньшим приоритетом, алгоритм поднимается по правому хребту текущего дерева — ровно настолько, насколько нужно.

Ключевые детали реализации:

• while вместо if — реализует подъём по хребту для левоассоциативных операторов.
• Передача приоритета в рекурсию — ограничивает, какие операторы «захватываются» на следующем уровне.
• LBP / RBP — контролируют ассоциативность через разницу в единицу.

Понимание этой геометрии делает Pratt parsing прозрачным: каждая строка кода отражает конкретное геометрическое действие с деревом, а не магию таблиц приоритетов.