Контекстно-свободные грамматики и приоритет

Грамматика умеет кодировать приоритет операторов — нужно лишь правильно расставить уровни нетерминалов.

Контекстно-свободная грамматика (КСГ) — грамматика, в которой левая часть каждой продукции — ровно один нетерминал, раскрываемый независимо от контекста.

Почти все языки программирования описываются именно КСГ. «Контекстно-свободная» означает, что нетерминал раскрывается одинаково, где бы он ни встретился — это резко упрощает разбор. Но как заставить грамматику понимать, что 2 + 3 * 4 равно 14, а не 20?

Проблема приоритета

Возьмём наивную грамматику выражений.

<expr> ::= <expr> "+" <expr>
         | <expr> "*" <expr>
         | <number>

Она неоднозначна: строку 2 + 3 * 4 можно разобрать двумя способами — сгруппировать сначала + или сначала *. Грамматика не говорит, какой верный, и результат становится непредсказуемым.

Уровни нетерминалов = приоритет

Решение: ввести отдельный нетерминал для каждого уровня приоритета. Чем ниже оператор в иерархии правил, тем сильнее он связывает.

<expr>   ::= <term> { "+" <term> }
<term>   ::= <factor> { "*" <factor> }
<factor> ::= <number> | "(" <expr> ")"

Теперь сложение работает с <term>, а умножение — внутри <term>, с <factor>. Это значит, что умножение «собирается» раньше и оказывается глубже в дереве. Скобки в <factor> позволяют поднять любое подвыражение на верхний уровень.

Как работает под капотом

Разберём 2 + 3 * 4 по новой грамматике. Дерево покажет приоритет наглядно.

        expr (+)
        /     \
     term      term (*)
      |        /     \
      2       3       4

Левый term — это просто 2. Правый term — это 3 * 4. Сложение видит уже готовое произведение 12 и прибавляет 2. Порядок вычисления зашит в форму дерева, а форма — в уровни грамматики.

Проверим арифметику Python, который использует те же приоритеты.

print(2 + 3 * 4)        # умножение раньше
print((2 + 3) * 4)      # скобки меняют порядок

Вывод:

14
20

Левая ассоциативность

Запись { "+" <term> } (повторение в EBNF-стиле) задаёт левую ассоциативность: 10 - 3 - 2 разбирается как (10 - 3) - 2 = 5, а не 10 - (3 - 2) = 9. Для вычитания и деления это критично.

print(10 - 3 - 2)   # (10 - 3) - 2
print(16 / 4 / 2)   # (16 / 4) / 2

Вывод:

5
2.0

Частые ошибки

Главная — использовать неоднозначную грамматику без уровней приоритета. Парсер тогда либо даёт случайный результат, либо отказывается строиться (для автогенераторов это конфликт).

Вторая — перепутать порядок уровней: поставить умножение выше сложения. Тогда сложение начнёт связывать сильнее, и 2 + 3 * 4 даст 20. Запомните: самый «сильный» оператор — в самом глубоком (нижнем) правиле.

Итог

КСГ раскрывает нетерминалы независимо от контекста — это упрощает разбор.
Неоднозначная грамматика не задаёт приоритет и даёт непредсказуемый результат.
Уровни нетерминалов (expr → term → factor) кодируют приоритет операторов.
Самый сильно связывающий оператор живёт в самом глубоком правиле; повторение задаёт левую ассоциативность.