Синтаксический анализ: грамматики, рекурсивный спуск, приоритеты операторов

В прошлой статье мы превратили текст в поток токенов. Это уже победа: let x = 2 + 3 * 4; перестал быть последовательностью байтов и стал последовательностью осмысленных единиц — KW(let) IDENT(x) OP(=) INT(2) OP(+) INT(3) OP(*) INT(4) PUNCT(;).

Но поток остался плоским, а программа плоской не бывает. 2 + 3 * 4 — это не «два, плюс, три, звёздочка, четыре», это «сумма двойки и произведения тройки на четвёрку». Разница принципиальна: первая интерпретация даёт 20, вторая — 14. Информация о том, какая из них правильная, не содержится в потоке токенов. Она содержится в грамматике языка, и работа парсера — восстановить её и материализовать в виде дерева.

Эта статья — про то, как именно. Мы разберём формализм (контекстно-свободные грамматики), его границы (неоднозначность, левая рекурсия, LL(1)), два практических метода (рекурсивный спуск и Pratt-разбор) и напишем парсер языка Mini, который к концу статьи разбирает рекурсивный fib целиком — с функциями, условиями, вызовами и внятными сообщениями об ошибках.

Почему плоского потока токенов недостаточно

Формально: язык токенов, которые может породить лексер, — регулярный. Язык корректных программ — нет. Классическое доказательство: язык правильно вложенных скобок ((( ... ))) не распознаётся конечным автоматом, потому что автомат имеет конечную память, а глубина вложенности не ограничена. Лемма о накачке для регулярных языков превращает это в строгую теорему; подробный разбор — в статье «Автоматы и формальные языки».

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

Второй источник структуры — приоритет операторов. 2 + 3 * 4 разбирается однозначно не потому, что так написано в исходнике, а потому, что так решил автор языка. Приоритет — это соглашение, которое надо где-то закодировать: либо в форме грамматики, либо в таблице сил связывания. Оба способа разберём.

Контекстно-свободные грамматики: минимальный необходимый формализм

Контекстно-свободная грамматика (КС-грамматика) — четвёрка: множество терминалов (это наши токены), множество нетерминалов (имена синтаксических категорий), множество правил вида «нетерминал → последовательность символов» и стартовый нетерминал.

«Контекстно-свободная» значит: правило для нетерминала применимо всегда, независимо от того, что стоит вокруг. Именно это делает разбор алгоритмически приятным — и именно поэтому почти всё интересное в языках программирования оказывается за пределами КС-грамматик («переменная должна быть объявлена», «типы должны совпадать») и уезжает в семантический анализ.

BNF, EBNF и как читать спецификацию языка

Форма Бэкуса — Наура (BNF) появилась в отчёте об Алголе-60 и с тех пор стала стандартным способом записи синтаксиса. EBNF добавляет к ней сахар из регулярных выражений: * (ноль или больше), + (один или больше), ? (необязательно), | (альтернатива), скобки для группировки.

Вот грамматика выражений Mini — тот самый фрагмент, который мы сейчас реализуем:

expr       = equality ;
equality   = comparison ( ( "==" | "!=" ) comparison )* ;
comparison = term ( ( "<" | ">" | "<=" | ">=" ) term )* ;
term       = factor ( ( "+" | "-" ) factor )* ;
factor     = unary ( ( "*" | "/" | "%" ) unary )* ;
unary      = ( "-" | "!" ) unary | call ;
call       = primary ( "(" arguments? ")" )* ;
arguments  = expr ( "," expr )* ;
primary    = INT | IDENT | "true" | "false" | "(" expr ")" ;

Читается сверху вниз как «выражение — это равенство; равенство — это сравнение, за которым может идти сколько угодно повторов == сравнение» и так далее. Обратите внимание: порядок уровней и есть таблица приоритетов, записанная задом наперёд — чем ниже правило в списке, тем крепче связывает оператор.

Спецификации реальных языков написаны ровно так же, и их полезно уметь читать: спецификация Go — компактная EBNF на одну страницу, грамматика Python — уже в PEG-нотации, справочник Rust — с отдельной таблицей приоритетов. Если вы сомневаетесь, как язык разберёт выражение, — ответ всегда там.

Вывод, дерево разбора и неоднозначность

Вывод — последовательность подстановок от стартового нетерминала к строке терминалов. Дерево, которое эти подстановки рисуют, называется деревом разбора (parse tree, CST — concrete syntax tree). В нём есть узел на каждое применённое правило, включая все служебные цепочки term → factor → unary → call → primary → INT.

Компилятору такое дерево не нужно: оно раздуто и повторяет случайности грамматики, а не смысл программы. Поэтому парсер строит сразу абстрактное синтаксическое дерево (AST), где остаются только содержательные узлы. CST существует лишь как форма стека вызовов — в памяти его никто не материализует.

Устройству AST целиком посвящена следующая статья; пока достаточно знать, что парсер обязан выдавать именно его.

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

expr = expr "+" expr | expr "*" expr | INT ;

неоднозначна: 2 + 3 * 4 разбирается и как (2 + 3) * 4, и как 2 + (3 * 4). Ни одно из деревьев не «правильнее» с точки зрения грамматики — она просто не содержит нужной информации. Практических лекарств три:

1. Расслоить грамматику по уровням приоритета — то, что сделано в грамматике Mini выше. Работает всегда, читается плохо при большом числе уровней.
2. Оставить неоднозначную грамматику и разрешать конфликты внешней таблицей — путь yacc/bison (%left, %right, %nonassoc) и Pratt-парсеров.
3. Задать разрешение конфликта правилом «жадности» — путь PEG, где | упорядочен и первая подошедшая альтернатива побеждает.

Самый известный пример неоднозначности — висячий else (dangling else):

if (a) if (b) x(); else y();   // else относится к if (b) или к if (a)?

C, C++, Java, C# и JavaScript решают его правилом «else связывается с ближайшим незакрытым if». В рекурсивном спуске это правило получается бесплатно: вложенный вызов if_stmt первым видит else и забирает его себе. В bison та же грамматика даёт shift/reduce-конфликт, который приходится глушить объявлением приоритетов. Языки, спроектированные позже (Go, Rust, Swift, Mini), проблему просто устранили — фигурные скобки у тела условия обязательны. Это ранний пример темы «Проектирование языков и DSL»: часть работы парсера можно вычеркнуть решением на уровне дизайна синтаксиса.

Приоритет и ассоциативность: как их вшивают в грамматику

Расслоение по уровням работает по простому принципу: чем глубже нетерминал, тем выше приоритет оператора, потому что глубокие уровни собирают свои узлы первыми и оказываются ниже в дереве.

Ассоциативность задаётся формой правила:

• term = factor ( "+" factor )* — цикл, узлы накапливаются слева направо → левая ассоциативность: 1 - 2 - 3 даёт (1 - 2) - 3.
• power = unary ( "^" power )? — рекурсия в хвосте → правая ассоциативность: 2 ^ 3 ^ 2 даёт 2 ^ (3 ^ 2) = 512, а не 64.
• comparison = term ( "<" term )? — без цикла и без рекурсии → неассоциативно: a < b < c синтаксическая ошибка. Так сделано в Python-подобных сравнениях цепочками и, например, в Rust (a < b < c не компилируется).

Пунктирная стрелка — ключевой момент: ( в primary рекурсивно вызывает expr, и именно поэтому скобки «сбрасывают» приоритет. Никакого особого кода для этого писать не надо.

Левая рекурсия — единственный настоящий запрет рекурсивного спуска

Правило

term = term "+" factor | factor ;

математически безупречно и даёт левую ассоциативность напрямую. Но парсер рекурсивного спуска на нём зависает: функция term() первым делом вызывает term(), не съев ни одного токена, — бесконечная рекурсия и RecursionError.

Это называется левой рекурсией, и она бывает косвенной (A → B x, B → A y), что обнаружить глазами гораздо труднее. Три способа справиться:

1. Переписать в EBNF-цикл (то, что мы уже сделали):

term = factor ( "+" factor )* ;

Формально это преобразование устранения левой рекурсии: A = A α | β превращается в A = β α*. Дерево строится вручную внутри цикла — накапливаем узел слева.

2. Взять восходящий парсер. LR-семейство левую рекурсию не просто переваривает, а предпочитает: левая рекурсия там дешевле правой, потому что стек не растёт.

3. Поддержать её специальным приёмом. PEG-парсер CPython (начиная с 3.9, PEP 617) умеет левую рекурсию через хитрость с мемоизацией — «выращивание семени»: правило сначала разбирается без левой рекурсии, потом результат подставляется и разбор повторяется, пока дерево растёт.

FIRST, FOLLOW и что значит LL(1)

Рекурсивный спуск на каждом шаге должен решить, какую альтернативу выбрать, глядя на один следующий токен. Грамматики, где это всегда возможно, называются LL(1): L — читаем слева направо, L — строим левый вывод, 1 — заглядываем на один токен вперёд.

Формально нужны два множества:

• FIRST(α) — множество терминалов, с которых может начинаться строка, выводимая из α. Плюс специальный ε, если α может быть пустой.
• FOLLOW(A) — множество терминалов, которые могут стоять сразу за нетерминалом A.

Грамматика LL(1), если для каждой пары альтернатив A = α | β выполняется: FIRST(α) и FIRST(β) не пересекаются, и — если α может быть пустой — FIRST(β) не пересекается с FOLLOW(A).

На практике эти множества считают редко: их выводит генератор парсеров, а при ручном написании парсера конфликт обнаруживается сам собой — вы просто не можете написать if. Но понимать их надо, потому что ошибки типа «grammar is not LL(1)» и «shift/reduce conflict» — это ровно про пересечения FIRST/FOLLOW.

Для инструкций Mini множества FIRST тривиально не пересекаются, и в этом весь смысл ключевых слов:

Ключевые слова в языках существуют в первую очередь ради этой таблицы. Языки без них (Lisp, Forth, APL) платят другим — либо единообразием синтаксиса, либо ручным управлением разбором. А там, где FIRST всё-таки пересекается, нужен либо больший lookahead, либо откат. Классика — C++: A * b; это умножение или объявление указателя? Ответ зависит от того, объявлено ли A типом, то есть от семантики. C и C++ решают это «лексическим хаком»: таблица символов сообщает лексеру, что A — typedef, и он выдаёт другой токен. Формально это ломает разделение фаз, и все об этом жалеют.

Ландшафт методов разбора

Что стоит за точками:

Практический вывод, который стоит принять сразу: почти все промышленные компиляторы пишут парсер руками методом рекурсивного спуска. GCC перешёл на рукописный парсер C++ в версии 4.1, отказавшись от bison; Clang, rustc, компилятор Go, TypeScript, V8, C# Roslyn — все рукописные. Причина не в производительности, а в качестве диагностики: генератору парсеров нечего сказать, кроме «syntax error», а рукописный код знает контекст и может выдать «ожидалась ; в конце объявления — возможно, вы забыли её на строке 12». Ради этого терпят рутину. Подробнее о цене хорошего сообщения — статья «Проектирование языков и DSL».

Рекурсивный спуск: пишем парсер выражений Mini

Метод описывается одной фразой: каждому нетерминалу грамматики соответствует функция. Функция читает токены и либо возвращает узел AST, либо сообщает об ошибке. Взаимная рекурсия функций воспроизводит вложенность грамматики; стек вызовов Python и есть магазинная память автомата.

Начнём с контракта токена — его нам поставляет лексер:

import re
from dataclasses import dataclass
from typing import Optional, List

@dataclass(frozen=True)
class Token:
    kind: str      # 'INT' | 'IDENT' | 'KW' | 'OP' | 'EOF'
    text: str
    line: int
    col: int

Чтобы статья была самодостаточной, вот его сжатая версия — одна регулярка и цикл, поддерживающий строку и колонку (полный разбор — в статье 01):

TOKEN_RE = re.compile(r"""
      (?P<WS>\s+)
    | (?P<INT>\d+)
    | (?P<IDENT>[A-Za-z_]\w*)
    | (?P<OP>==|!=|<=|>=|->|[-+*/%<>=!(),;{}:])
""", re.VERBOSE)
KEYWORDS = {"let", "fn", "if", "else", "return", "true", "false"}

def tokenize(src: str) -> List[Token]:
    toks, line, col, i = [], 1, 1, 0
    while i < len(src):
        m = TOKEN_RE.match(src, i)
        if m is None:
            raise SyntaxError(f"{line}:{col}: неизвестный символ {src[i]!r}")
        kind, text = m.lastgroup, m.group()
        if kind == "WS":                                # пробелы не порождают токен,
            nl = text.count("\n")                       # но двигают позицию
            line, col = (line + nl, len(text) - text.rfind("\n")) if nl else (line, col + len(text))
            i = m.end(); continue
        if kind == "IDENT" and text in KEYWORDS:
            kind = "KW"                                 # ключевые слова — отдельный вид токена
        toks.append(Token(kind, text, line, col))
        col += len(text); i = m.end()
    toks.append(Token("EOF", "", line, col))            # страж: убирает проверки на конец списка
    return toks

Токен EOF в конце — не мелочь, а важный приём: он позволяет всюду писать peek().text == ... без проверок выхода за границу. Ту же роль играет часовой в связном списке (структуры данных).

Узлы AST — обычные датаклассы. Каждый хранит токен, чтобы позже показать место ошибки:

@dataclass
class Num:                                              # 42
    value: int; tok: Token
@dataclass
class Bool:                                             # true / false
    value: bool; tok: Token
@dataclass
class Var:                                              # x
    name: str; tok: Token
@dataclass
class Unary:                                            # -x, !flag
    op: str; operand: object; tok: Token
@dataclass
class Binary:                                           # a + b
    op: str; left: object; right: object; tok: Token
@dataclass
class Call:                                             # f(a, b)
    callee: object; args: list; tok: Token

Узлы инструкций (Let, If, Return, Block, ExprStmt, FnDecl, ErrorStmt) устроены так же — имя, поля, токен; их состав виден по коду ниже.

Теперь ядро — навигация по потоку и диагностика:

class ParseError(Exception):
    pass

class Parser:
    def __init__(self, tokens):
        self.toks = tokens
        self.i = 0
        self.errors = []

    def peek(self, k=0):
        return self.toks[min(self.i + k, len(self.toks) - 1)]

    def advance(self):
        t = self.toks[self.i]
        if t.kind != "EOF":       # на EOF стоим на месте — так безопаснее
            self.i += 1
        return t

    def check(self, *texts):
        return self.peek().text in texts

    def match(self, *texts):      # съесть, если подошло
        return self.advance() if self.check(*texts) else None

    def expect(self, text, what): # съесть или упасть с осмысленным текстом
        if self.check(text):
            return self.advance()
        raise self.error(f"ожидалось {text!r} {what}")

    def error(self, msg, tok=None):
        t = tok or self.peek()
        got = "конец файла" if t.kind == "EOF" else repr(t.text)
        return ParseError(f"{t.line}:{t.col}: {msg}, а найдено {got}")

И собственно каскад уровней приоритета — построчный перевод грамматики в код:

    def expression(self):
        return self.equality()

    def equality(self):                        # equality = comparison ( ("=="|"!=") comparison )*
        node = self.comparison()
        while self.check("==", "!="):
            op = self.advance()
            node = Binary(op.text, node, self.comparison(), op)
        return node

    def comparison(self):                      # тело буква в букву как у equality,
        node = self.term()                     # только набор операторов и следующий уровень
        while self.check("<", ">", "<=", ">="):
            op = self.advance()
            node = Binary(op.text, node, self.term(), op)
        return node

    def term(self):                            # term = factor ( ("+"|"-") factor )*
        node = self.factor()
        while self.check("+", "-"):
            op = self.advance()
            node = Binary(op.text, node, self.factor(), op)
        return node

    def factor(self):                          # factor = unary ( ("*"|"/"|"%") unary )*
        node = self.unary()
        while self.check("*", "/", "%"):
            op = self.advance()
            node = Binary(op.text, node, self.unary(), op)
        return node

    def unary(self):                           # правая рекурсия: --x разбирается как -(-x)
        if self.check("-", "!"):
            op = self.advance()
            return Unary(op.text, self.unary(), op)
        return self.call()

    def call(self):                            # постфиксный цикл: f(1)(2) законен
        node = self.primary()
        while self.check("("):
            lp = self.advance()
            args = []
            if not self.check(")"):
                args.append(self.expression())
                while self.match(","):
                    args.append(self.expression())
            self.expect(")", "после списка аргументов")
            node = Call(node, args, lp)
        return node

    def primary(self):
        t = self.peek()
        if t.kind == "INT":
            return Num(int(self.advance().text), t)
        if t.text in ("true", "false"):
            self.advance()
            return Bool(t.text == "true", t)
        if t.kind == "IDENT":
            return Var(self.advance().text, t)
        if t.text == "(":
            self.advance()
            inner = self.expression()          # рекурсия наверх: скобки сбрасывают приоритет
            self.expect(")", "после выражения в скобках")
            return inner
        raise self.error("ожидалось начало выражения")

Обратите внимание на строчку node = Binary(op.text, node, self.factor(), op). Результат предыдущей итерации становится левым потомком нового узла — это и есть левая ассоциативность, собранная руками. Поменяйте местами — получите правую.

Проследим разбор 2 + 3 * 4 по вызовам:

factor() забрал * себе и вернул наверх уже готовое произведение — поэтому умножение оказалось глубже в дереве. Приоритет нигде не записан числом; он выражен порядком вызовов. Это ровно тот приём, с которым мы столкнулись в мини-компиляторе из обзорной статьи, только теперь на шести уровнях.

Сложность. Каждый токен читается ровно один раз и в цикл никогда не возвращается, значит время O(n) по числу токенов. Память — O(d), где d — максимальная глубина вложенности выражения (глубина стека вызовов). Отсюда, кстати, практическая проблема: файл вида ((((...1...)))) с глубиной 100 000 роняет рекурсивный парсер по переполнению стека. Настоящие компиляторы ограничивают глубину явно — Clang по умолчанию режет на 256 уровнях (-fbracket-depth), CPython — на 200 (sys.setrecursionlimit тут не спасает, у C-парсера свой лимит). Это не костыль, а защита от DoS: без лимита любой пользовательский конфиг может уронить сервис.

Приоритеты без каскада: Pratt-парсер

У каскада есть недостаток, который становится заметным на реальных языках. В C — пятнадцать уровней приоритета, в C++ — семнадцать. Это пятнадцать почти одинаковых функций, и каждый атом 1 проходит через все пятнадцать вызовов, прежде чем добраться до primary. Измерим на нашем парсере (выражение из 2000 слагаемых, счёт всех вызовов функций через sys.setprofile):

каскад из 6 уровней : 34 007 вызовов, 3.85 мс
Pratt               : 13 998 вызовов, 2.26 мс

Разница в 2.4 раза по вызовам — и это на грамматике вдвое короче настоящей. Хуже другое: добавить оператор в каскад означает вставить новый уровень и переписать соседние.

Pratt-разбор (top-down operator precedence, Вон Пратт, статья 1973 года) заменяет цепочку функций одной функцией с числовым параметром. Каждому оператору назначается сила связывания (binding power) — насколько крепко он притягивает соседние операнды. Причём сил две: левая и правая, и их асимметрия кодирует ассоциативность.

Правило простое: если левая сила ниже правой (+ = 7/8), оператор левоассоциативен; если выше (= = 2/1) — правоассоциативен. Никаких особых случаев в коде.

# (левая сила, правая сила)
INFIX = {
    "=":  (2, 1),                                     # правоассоциативно
    "==": (3, 4), "!=": (3, 4),
    "<":  (5, 6), ">":  (5, 6), "<=": (5, 6), ">=": (5, 6),
    "+":  (7, 8), "-":  (7, 8),
    "*":  (9, 10), "/": (9, 10), "%": (9, 10),
}
PREFIX_BP = 11    # унарные -x, !x — крепче любой бинарной арифметики
CALL_BP   = 13    # вызов f(x) крепче унарного минуса: -f(x) == -(f(x))

class PrattParser(Parser):
    def expression(self, min_bp=0):
        t = self.advance()
        # --- префиксная позиция: то, с чего выражение может начаться ---
        if t.kind == "INT":
            left = Num(int(t.text), t)
        elif t.text in ("true", "false"):
            left = Bool(t.text == "true", t)
        elif t.kind == "IDENT":
            left = Var(t.text, t)
        elif t.text in ("-", "!"):
            left = Unary(t.text, self.expression(PREFIX_BP), t)
        elif t.text == "(":
            left = self.expression(0)                  # внутри скобок порог сбрасывается
            self.expect(")", "после выражения в скобках")
        else:
            raise self.error("ожидалось начало выражения", t)

        # --- инфиксная/постфиксная позиция: пока связывание достаточно крепкое ---
        while True:
            op = self.peek()
            if op.text == "(" and CALL_BP >= min_bp:   # постфиксный вызов
                lp = self.advance()
                args = []
                if not self.check(")"):
                    args.append(self.expression(0))
                    while self.match(","):
                        args.append(self.expression(0))
                self.expect(")", "после списка аргументов")
                left = Call(left, args, lp)
                continue
            bp = INFIX.get(op.text)
            if bp is None:
                break                                  # не оператор — выражение кончилось
            lbp, rbp = bp
            if lbp < min_bp:
                break                                  # слева связывают крепче — отдаём операнд
            self.advance()
            left = Binary(op.text, left, self.expression(rbp), op)
        return left

Вся идея — в двух строках: if lbp < min_bp: break и self.expression(rbp). Рекурсивный вызов с правой силой означает «собери мне всё, что связано крепче, чем этот оператор справа». Разберём 1 - 2 - 3: внешний вызов с min_bp=0 берёт 1, видит - (7 ≥ 0), рекурсивно разбирает правую часть с min_bp=8; внутри видит второй - с левой силой 7 < 8 и прекращает работу, вернув 2. Внешний цикл собирает (1-2) и повторяет — получается ((1-2)-3). Для = силы (2, 1): внутренний вызов с min_bp=1 встречает = с левой силой 2 ≥ 1 и продолжает — получается правая ассоциативность. Одна таблица, ноль ветвлений.

Проверка (оба парсера должны совпадать всюду, где грамматики пересекаются):

2 + 3 * 4              -> (+ 2 (* 3 4))
2 * 3 + 4              -> (+ (* 2 3) 4)
1 - 2 - 3              -> (- (- 1 2) 3)
-a * b                 -> (* (- a) b)
!x == false            -> (== (! x) false)
f(a, b + 1) * 2        -> (* (call f a (+ b 1)) 2)
-f(x)                  -> (- (call f x))
a < b == c > d         -> (== (< a b) (> c d))

правая ассоциативность (только Pratt): x = y = 1 + 2  ->  (= x (= y (+ 1 2)))

Почему силы нумеруются нечётными/чётными парами, а не 1, 2, 3? Чтобы оставить место: между уровнями 7/8 и 9/10 всегда можно вставить новый оператор, не переписывая таблицу. Тот же приём используют в LSM-деревьях и в порядковых полях в БД. Отличное практическое введение в Pratt-разбор — статья Алекса Кладова, из которой эта схема сил и заимствована; каноническое объяснение — глава Роберта Найстрома.

Промышленная практика — гибрид: инструкции и объявления разбираются рекурсивным спуском (там правила задаются ключевыми словами и приоритетов нет), а выражения — Pratt-парсером. Так устроены rustc, Zig, Carbon, парсер выражений в SQLite. Мы делаем так же: PrattParser наследует весь код инструкций у Parser и переопределяет только expression.

Полный парсер Mini: инструкции, блоки, функции

Грамматика инструкций:

program    = declaration* ;
declaration= fnDecl | statement ;
fnDecl     = "fn" IDENT "(" params? ")" ( "->" IDENT )? block ;
params     = IDENT ":" IDENT ( "," IDENT ":" IDENT )* ;
statement  = letStmt | ifStmt | returnStmt | block | exprStmt ;
letStmt    = "let" IDENT ( ":" IDENT )? "=" expr ";" ;
ifStmt     = "if" expr block ( "else" ( ifStmt | block ) )? ;
returnStmt = "return" expr? ";" ;
block      = "{" declaration* "}" ;
exprStmt   = expr ";" ;

Код — прямой перевод, строчка в строчку:

    def program(self):
        stmts = []
        while self.peek().kind != "EOF":
            stmts.append(self.declaration())
        return stmts

    def statement(self):
        if self.check("let"):    return self.let_stmt()
        if self.check("if"):     return self.if_stmt()
        if self.check("return"): return self.return_stmt()
        if self.check("{"):      return self.block()
        expr = self.expression()
        self.expect(";", "в конце инструкции-выражения")
        return ExprStmt(expr)

    def let_stmt(self):
        kw = self.advance()
        name = self.expect_ident("после 'let'")
        type_ = self.expect_ident("после ':' в аннотации типа").text if self.match(":") else None
        self.expect("=", "в объявлении переменной")
        init = self.expression()
        self.expect(";", "в конце объявления")
        return Let(name.text, type_, init, kw)

    def if_stmt(self):
        kw = self.advance()
        cond = self.expression()
        then = self.block()                       # тело в скобках — висячего else не бывает
        otherwise = None
        if self.match("else"):
            otherwise = self.if_stmt() if self.check("if") else self.block()
        return If(cond, then, otherwise, kw)

    def return_stmt(self):
        kw = self.advance()
        value = None if self.check(";") else self.expression()
        self.expect(";", "в конце return")
        return Return(value, kw)

    def block(self):
        lb = self.expect("{", "в начале блока")
        stmts = []
        while not self.check("}") and self.peek().kind != "EOF":
            stmts.append(self.declaration())
        self.expect("}", "в конце блока")
        return Block(stmts, lb)

    def fn_decl(self):
        kw = self.advance()
        name = self.expect_ident("после 'fn'")
        self.expect("(", "после имени функции")
        params = []
        if not self.check(")"):
            params.append(self.param())
            while self.match(","):
                params.append(self.param())
        self.expect(")", "после списка параметров")
        ret = self.expect_ident("после '->'").text if self.match("->") else None
        return FnDecl(name.text, params, ret, self.block(), kw)

Запускаем на целевой программе трека:

src = """
fn fib(n: Int) -> Int {
  if n < 2 { return n; }
  return fib(n - 1) + fib(n - 2);
}
let limit: Int = 10;
let result = fib(limit);
print(result);
"""
for stmt in PrattParser(tokenize(src)).program():
    print(show(stmt))     # show — печать дерева в скобочной нотации

Вывод:

(fn fib(n:Int) -> Int (block (if (< n 2) (block (return n))) (return (+ (call fib (- n 1)) (call fib (- n 2))))))
(let limit:Int 10)
(let result (call fib limit))
(call print result)

Это работающий парсер: 200 строк, полный синтаксис Mini, дерево на выходе. Функцию show и обход дерева мы вынесем в следующую статью — там она превратится в первого посетителя (Visitor).

Ошибки: сообщения и восстановление

Компилятор, который падает на первой синтаксической ошибке, годится для учебника и не годится для работы. IDE вызывает парсер на каждое нажатие клавиши, и в этот момент код всегда синтаксически сломан: пользователь набрал let x = и ещё думает. Парсер обязан вернуть дерево с дырами, а не исключение.

Базовая техника — паническое восстановление (panic mode): поймали ошибку, записали её, пропускаем токены до ближайшей точки, где точно начинается что-то новое, и продолжаем.

    SYNC_STARTERS = {"let", "fn", "if", "return", "}"}

    def declaration(self):
        try:
            return self.fn_decl() if self.check("fn") else self.statement()
        except ParseError as e:
            self.errors.append(str(e))        # ошибку копим, а не бросаем наверх
            tok = self.peek()
            self.synchronize()
            return ErrorStmt(str(e), tok)     # узел-заглушка: дерево остаётся полным

    def synchronize(self):
        while self.peek().kind != "EOF":
            if self.toks[self.i - 1].text == ";":   # только что закончилась инструкция
                return
            if self.peek().text in self.SYNC_STARTERS:
                return
            self.advance()

Проверяем на заведомо битом входе:

broken = "let x = ;\nlet y = 2 * ;\nlet z = 3;\n"
p = PrattParser(tokenize(broken))
stmts = p.program()

ошибка: 1:9: ожидалось начало выражения, а найдено ';'
ошибка: 2:13: ожидалось начало выражения, а найдено ';'
разобрано инструкций: 3 | последняя: (let z 3)

Две ошибки найдены за один проход, третья корректная инструкция разобрана нормально. Именно такое поведение ожидает от парсера языковой сервер.

Практические правила диагностики, выстраданные компиляторными командами:

• Не сообщать о каскадных ошибках. Пока парсер в панике, новые ошибки подавляются: одна пропущенная скобка не должна порождать сорок сообщений. Rust идёт дальше и на этапе выдачи дедуплицирует диагностики по спанам.
• Говорить, чего ждали, а не что нашли. «Ожидалась ;» полезнее, чем «неожиданный let». Лучший вариант — оба плюс позиция.
• Пытаться угадать намерение. expected ';' с подсказкой «вставьте ; в конец строки 12» — это rustc --explain и «did you mean» в Clang. Реализуется просто: если ошибка возникла на первом токене новой строки, точка вставки — конец предыдущей.
• Хранить спаны в узлах, а не только позицию начала. Подсветка ^^^ требует диапазона. Мы храним токен; в продакшне хранят (start, end) в байтах от начала файла.
• Не терять токены. Для форматтера и LSP нужны и комментарии, и пробелы. Такое дерево называют lossless syntax tree; так устроены tree-sitter и rust-analyzer.

Сложность и производительность

Packrat-мемоизация — это классическое динамическое программирование: результат разбора правила A на позиции i кешируется, и повторный откат не пересчитывает его. Линейное время покупается линейной памятью — для файла в мегабайт это десятки мегабайт таблицы, поэтому CPython мемоизирует не все правила, а выборочно.

Отрезвляющий факт: парсинг почти никогда не является узким местом компилятора. В типичной сборке C++ большая часть времени уходит на препроцессор, инстанцирование шаблонов, оптимизации и линковку; в rustc — на проверку заимствований, монофоризацию и LLVM. Профили сборок Chromium и Rust показывают долю парсера в единицы процентов. Отсюда практический вывод: оптимизировать парсер стоит ровно до момента, когда он читает вход за один проход и не аллоцирует лишнего; дальше выигрыш надо искать в оптимизациях и кодогенерации.

Исключение — инструменты, которые парсят непрерывно: LSP, линтеры, подсветка синтаксиса. Там важны не абсолютные миллисекунды, а инкрементальность: перепарсить не файл, а изменившееся поддерево. Это и есть главная идея tree-sitter.

Немного истории — она объясняет, почему всё так

Дуга очевидна: сначала теория научилась описывать синтаксис, потом инструменты научились генерировать парсеры автоматически, а потом промышленность вернулась к рукописным парсерам — потому что критерием качества стало не «разобрал/не разобрал», а «объяснил человеку, что не так». Теория при этом никуда не делась: рукописный парсер пишут по грамматике, и понимание LL(1)/FIRST/FOLLOW нужно ровно для того, чтобы понимать, где рукописный код начинает врать.

Типичные ошибки

• Смешивать разбор и вычисление. Соблазн посчитать 2 + 3 прямо в парсере велик, но тогда парсер нельзя переиспользовать ни для форматтера, ни для линтера, ни для типов. Парсер возвращает дерево — и всё. Свёртка констант живёт в оптимизациях.
• Забыть про позиции. Узел без спана бесполезен для диагностики, и добавить спаны потом дороже, чем сразу: придётся трогать каждый конструктор.
• Смешивать лексер и парсер. «Пусть парсер сам разберётся с пробелами» приводит к тому, что грамматика тонет в служебных правилах. Разделение фаз — не догма, а экономия.
• Городить неоднозначную грамматику и латать её приоритетами. В bison это соблазнительно, но каждый подавленный shift/reduce-конфликт — это место, где язык ведёт себя не так, как вы думаете. Правило: конфликтов должно быть ноль.
• Строить CST и потом конвертировать в AST. Двойная работа и двойная память. Стройте AST сразу; CST нужен только инструментам, которым важен исходный текст побайтово.
• Не ограничивать глубину рекурсии. Вход ((((((... из пользовательского ввода роняет процесс. Лимит глубины — это защита, а не перестраховка.
• Разбирать язык регулярными выражениями. HTML, JSON, SQL, конфиги — всё это КС-языки. Регулярка справится с 90 % входов и сломается на оставшихся 10 % в проде.
• Считать, что «пробелы не важны». В Python, YAML, Haskell отступы значимы, и это обрабатывается на границе лексера и парсера (токены INDENT/DEDENT). Решение принимается до написания парсера, не после.

Мини-итог

• Поток токенов плоский, программа — дерево. Парсер восстанавливает вложенность, приоритет и ассоциативность, опираясь на контекстно-свободную грамматику.
• Неоднозначность — свойство грамматики, а не языка. Лечится расслоением по уровням приоритета, внешней таблицей приоритетов или упорядоченным выбором в PEG.
• Левая рекурсия — единственный жёсткий запрет рекурсивного спуска; устраняется переписыванием A = A α | β в A = β α*.
• LL(1) означает «выбор правила по одному токену вперёд». FIRST/FOLLOW — формальная проверка этого свойства; ключевые слова в языках существуют главным образом чтобы её обеспечить.
• Рекурсивный спуск — функция на нетерминал, стек вызовов вместо магазина, O(n) времени и O(глубины) памяти. Так написаны GCC, Clang, rustc, Go, TypeScript.
• Pratt-разбор заменяет каскад уровней таблицей сил связывания. Асимметрия левой и правой силы даёт ассоциативность бесплатно. Промышленный стандарт — гибрид: спуск для инструкций, Pratt для выражений.
• Восстановление после ошибок — не украшение, а требование: без него не работают ни IDE, ни адекватная диагностика.

Что почитать

• Robert Nystrom, Crafting Interpreters — «Parsing Expressions» и «Compiling Expressions». Лучший практический текст по теме, бесплатный.
• Vaughan Pratt, «Top Down Operator Precedence», POPL 1973 — оригинал.
• Alex Kladov, «Simple but Powerful Pratt Parsing» — современное объяснение сил связывания.
• Bryan Ford, «Parsing Expression Grammars», POPL 2004; и PEP 617 — как PEG приехал в CPython.
• Aho, Lam, Sethi, Ullman, Compilers: Principles, Techniques, and Tools («книга дракона»), главы 4–5 — исчерпывающе про LL, LR, FIRST/FOLLOW.
• Руководство GNU Bison — если всё-таки нужен генератор; раздел про разрешение конфликтов особенно поучителен.
• tree-sitter — инкрементальный GLR, на котором живёт подсветка в Neovim, GitHub и Zed.
• Связанные статьи портала: автоматы и формальные языки, рекурсия и «разделяй и властвуй», синтаксис лямбда-исчисления — там та же задача про ассоциативность аппликации, функциональная парадигма — про парсер-комбинаторы как альтернативный способ записать ту же грамматику.

Что дальше

У нас есть дерево — но пока это набор датаклассов, по которому нечем ходить. Следующая статья превращает его в полноценную структуру: как проектировать иерархию узлов, чем отличается обход сверху вниз от обхода снизу вверх, почему паттерн Visitor стал стандартом де-факто в компиляторах и как написать первый настоящий проход по AST — интерпретатор выражений Mini, который наконец что-то вычислит.

Абстрактное синтаксическое дерево: представление, обход, паттерн Visitor