Ниже — подробное руководство по построению рекурсивного нисходящего (top‑down) парсера для контекстно‑свободной грамматики арифметических выражений с унарными и бинарными операциями, скобками и приоритетами. Разберём этапы, типичные проблемы (в первую очередь — левая рекурсия) и способы их устранения, а также практики обработки ошибок для понятных сообщений пользователю.

1) Общая архитектура

Лексер (tokenizer): выделяет токены (NUMBER, IDENT, +, -, *, /, ^, '(', ')', EOF и т.д.) и сохраняет позицию (строка/столбец / индекс).Парсер — рекурсивный нисходящий: набор функций (parseExpression, parseTerm, parseFactor/parsePrimary) которые читают токены и строят AST (узлы: BinaryOp, UnaryOp, Number, Paren и т.п.).AST или промежуточное представление используется далее (выражение вычисления, трансформация и т.п.).

2) Пример исходной "интуитивной" грамматики (может содержать левую рекурсию)
(упрощённо)
Expr -> Expr '+' Expr
| Expr '-' Expr
| Expr '*' Expr
| Expr '/' Expr
| '-' Expr (унарный минус)
| '(' Expr ')'
| NUMBER

Эта форма неудобна для рекурсивного нисходящего парсера из‑за левой рекурсии и неоднозначности при приоритете операторов.

3) Преобразование грамматики: приоритеты и устранение левой рекурсии
Типичный подход — разбить по уровням приоритета (Expr, Term, Factor) и убрать левую рекурсию.

Неформальная корректная грамматика с приоритетами и ассоциативностью:
Expr -> Term Expr'
Expr' -> ('+' | '-') Term Expr' | ε (лево‑ассоциативные +,-)
Term -> Factor Term'
Term' -> ('' | '/') Factor Term' | ε (лево‑ассоциативные ,/)
Factor -> Unary
Unary -> ('+' | '-') Unary | Power
Power -> Primary ('^' Unary)? (право‑ассоциативный ^)
Primary -> NUMBER | '(' Expr ')'

Пояснения:

Удаление прямой левой рекурсии: правило A -> A α | β заменяется на A -> β A' ; A' -> α A' | ε.Унарные операторы включены на уровне Unary (префиксные). Это решает неоднозначность унарного и бинарного минуса: когда парсер вызывает parseUnary в контексте, где ожидается операнд, знак трактуется как унарный.Для степени (^) часто нужна правая ассоциативность: Power -> Primary ('^' Unary)? или реализуется рекурсивно: Power -> Primary '^' Power | Primary; эта форма — правая рекурсия — допустима для рекурсивного нисходящего парсера.

4) Как в коде выглядят функции парсера (псевдокод)
Привожу типовые функции (в процедурном стиле):

function parseExpression():
node = parseTerm()
while (currentToken is '+' or '-'):
op = currentToken
advance()
right = parseTerm()
node = BinaryOp(op, node, right)
return node

function parseTerm():
node = parseUnary()
while (currentToken is '*' or '/'):
op = currentToken
advance()
right = parseUnary()
node = BinaryOp(op, node, right)
return node

function parseUnary():
if (currentToken is '+' or '-'):
op = currentToken
advance()
operand = parseUnary() // для нескольких унарных подряд
return UnaryOp(op, operand)
else:
return parsePower()

function parsePower():
node = parsePrimary()
if (currentToken is '^'):
advance()
right = parseUnary() // правостепенная ассоц.: parseUnary или parsePower
return BinaryOp('^', node, right)
return node

function parsePrimary():
if (currentToken is NUMBER):
n = currentToken.value
advance()
return NumberNode(n)
if (currentToken is '('):
advance()
node = parseExpression()
expect(')') // см. обработку ошибок ниже
return node
error("Ожидался операнд или '('") // обработка ошибок

Эта структура реализует приоритеты: Power > Unary > Term(*) > Expr(+/-).

5) Альтернативы: Pratt (precedence‑climbing) / precedence-climbing

Для большого числа операторов / смешанных префикс/постфикс/инфикс удобен алгоритм Pratt (или precedence climbing). Он компактнее и гибко управляет приоритетами и ассоциативностью.Идея: есть функция parseExpression(minPrecedence) — сначала parse prefix (либо число, либо унарный оператор), затем в цикле пока текущий оператор имеет precedence >= minPrecedence: захватываем infix и рекурсивно парсим правый операнд с учётом ассоциативности.

6) Левaя рекурсия: проблемы и устранение

Прямая левая рекурсия (A -> A α | β) ломает рекурсивный нисходящий парсер (необходима бесконечная рекурсия).Устраняется преобразованием грамматики в эквивалентную без левой рекурсии (см. пример в пункте 3).Непрямая левая рекурсия (A -> B α; B -> A β) требует более общего алгоритма устранения: порядок нетерминалов и замен (см. стандартный алгоритм удаления левой рекурсии).Если грамматика слишком сложна или динамична, можно применять парсер, который поддерживает левую рекурсию (например, PEG‑парсеры с memoization и поддержкой left recursion, GLR и т.д.), либо использовать Pratt/precedence climbing там, где это применимо.

7) Левые факторы (left factoring)

Если у двух альтернатив общий префикс, рекурсивный нисходящий парсер может не знать, какую альтернативу выбрать по одному токену. Тогда применяют left‑factoring:
A -> α β1 | α β2 => A -> α A' ; A' -> β1 | β2Часто нужна при наличии одинакового начала альтернатив (например, IDENT '(' vs IDENT ...).

8) Различение унарных и бинарных операторов

Унарный оператор должен присутствовать в грамматике на уровне, где ожидается операнд (parseUnary), тогда в контексте left operand right operand будет корректно распознаваться как бинарный, а когда парсер ожидает начало factor, встретит -, он трактует его как унарный.В реализации с лексером токен "-" один и тот же; различие по синтаксису делает парсер, который решает, какой смысл у токена в данном месте.

9) Обработка ошибок синтаксиса — принципы и стратегии
Цели: дать понятное сообщение, показать позицию ошибки, продолжить анализ при возможности (чтобы сообщить о нескольких ошибках), и не захламлять вывод лишними сообщениям.

Основные техники:
a) Сообщение об ошибке с позиции и ожидаемым множеством:

При несоответствии: “На позиции X: найден токен 'T', ожидалось одно из: {NUMBER, '(', '+'}”.Для формулировки ожидаемого множества используют FIRST/Follow множества или список токенов, которые функции parse* обычно принимают.

b) Panic‑mode recovery (синхронизация):

При ошибке пропускаем токены до ближайшего синхронизирующего токена (например, ;, newline, EOF или ')'), затем продолжаем разбор на более высоком уровне.Для выражений синхронизация может быть ')' или ';' или EOF. Это простая и надёжная стратегия, но может пропускать много текста.

c) Insertion/Deletion heuristic (фаза реконструкции — попытка восстановления):

Попытка «вставить» ожидаемый токен виртуально (например, вставить ')' если встретили EOF) и продолжить, либо удалить неожиданный токен и попробовать снова.Подходит для дружественных IDE и для генерации единого AST, но нужно аккуратно ограничивать такие исправления, чтобы не скрыть реальные ошибки.

d) Error productions:

Добавить в грамматику распространённые ошибки как отдельные альтернативы (например, Primary -> '(' Expr => сообщение “пропущена ')'”), чтобы распознавать и давать хорошие сообщения.

e) Построение специальных error‑узлов в AST:

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

f) Сбор нескольких ошибок:

Не бросать исключение на первой ошибке; фиксировать ошибку (сообщение, позиция), попытаться восстановиться и продолжить.

g) Подсказки и контекст:

Если токен не подходит, показывать не только “ожидалось …”, но и контекст: “Перед токеном 'x' ожидался операнд; возможно пропущен оператор?” или “Отсутствует ')' для операнда, начатого в позиции P”.Для частых ошибок (пропущенная скобка, лишняя запятая, лишний оператор) распознавать паттерны и формировать понятные рекомендации.

Реализация простого обработчика в парсере:

В каждой функции parseX есть helper expect(tokenType):
if current != tokenType:
reportError(pos, "Ожидался {tokenType}, найден {current}")
// попытка восстановления:
if current in synchronizationSetForFunction:
// считаем токен пропущенным — возвращаем два варианта: вставка виртуального токена или Null/error node
return // continue with error node
else:
// пропустить токен
advance()
// повторить проверку несколько раз, или until EOF
else:
advance()

Используйте синхронизационные множества на каждом уровне (например, для parsePrimary: {')', '+', '-', '*', '/', EOF}).

10) Примеры сообщений и сценарии восстановления

Пропущена закрывающая скобка:
"Ошибка на позиции 12: ожидалась ')', найден токен '+'; вставлена ')' и продолжаем парсинг."Непредвиденный оператор:
"Ошибка на позиции 8: неожиданный оператор '+'. Ожидался операнд. Возможно пропущена скобка или число перед '+'. Пропускаем '+' и продолжаем."Неожиданный EOF:
"Ошибка: неожиданный конец файла. Ожидались: NUMBER, '(' или унарный оператор."

11) Дополнительные практические советы

Храните в токенах позицию (line/col/offset) — это необходимо для полезных сообщений.Для IDE/интерактивных приложений удобна по‑символьная диагностика: выделение диапазона ошибки.Пишите тесты ошибок: типичные опечатки, вложенные незакрытые скобки, подряд операторы, пустые скобки и т.д.Для сложной грамматики рассмотрите использование парсер‑генераторов (ANTLR, Bison) либо GLR/PEG если нельзя избежать левой рекурсии или неоднозначностей. Но для арифметики рекурсивный нисходящий парсер + преобразование грамматики вполне достаточен.Для выражений с большим числом операторов Pratt‑парсер часто проще и короче.

Короткое резюме

Разбейте грамматику по приоритетам, вынеся унарные операторы в отдельный уровень; удалите левую рекурсию обычной транспозицией в формы с X' (или используйте precedence climbing/Pratt).Реализуйте функции parseExpression/parseTerm/parseUnary/... или Pratt‑метод.Для ошибок: отчёт о позиции, список ожидаемых токенов, синхронизация (panic mode) + опционально вставка/удаление токенов и error‑узлы в AST для продолжения разбора и выдачи нескольких диагностик.

Если хотите, могу:

Привести полную реализацию простого рекурсивного нисходящего парсера на выбранном языке (Python/Java/TypeScript).Показать пример реализации Pratt‑парсера для вашего набора операторов и ассоциативностей.Написать набор тестов для проверки случаев ошибок и восстановления.