Предложу компактную EBNF-версию грамматики для выражений с приоритетами и скобками, обоснование, и кратко — как лексер и парсер взаимодействуют и какие ошибки возможны при неоднозначностях.
Грамматика (EBNF, числа и формулы в KaTeX):
$Expr::=AddExpr$
$AddExpr::=MulExpr\{{(}^{\prime }{+}^{\prime }{\mid }^{\prime }{-}^{\prime })MulExpr\}$ — (низкий приоритет, левосторонняя ассоциативность)
$MulExpr::=PowExpr\{{(}^{\prime }{\ast }^{\prime }{\mid }^{\prime }{/}^{\prime })PowExpr\}$ — (средний приоритет, левосторонняя ассоциативность)
\(PowExpr ::= UnaryExpr [ '^' \; PowExpr ]\) — (высокий приоритет, правосторонняя ассоциативность)
$UnaryExpr::={(}^{\prime }{+}^{\prime }{\mid }^{\prime }{-}^{\prime })UnaryExpr\mid Primary$ — (унарные операции выше умножения/сложения)
$Primary::=NUMBER\mid IDENTIFIER{\mid }^{\prime }{(}^{\prime }Expr{}^{\prime }{)}^{\prime }$
Терминалы: $NUMBER$, $IDENTIFIER$, '+', '-', '*', '/', '^', '(', ')'.
(В варианте для LR-парсеров можно записать явную левую рекурсию: $AddExpr::=AddExpr{(}^{\prime }{+}^{\prime }{|}^{\prime }{-}^{\prime })MulExpr\mid MulExpr$, и аналогично для $MulExpr$.)
Обоснование:
- Уровни нетерминалов (AddExpr, MulExpr, PowExpr) задают приоритеты: операции в нижних уровнях не «поглощают» более приоритетные, т.е. $\ast$ и $/$ сильнее $+$ и $-$.
- Правосторонняя рекурсия для возведения в степень ($PowExpr$) обеспечивает правильную правую ассоциативность: \(a^b^c\) парсится как $a^{(b^c)}$.
- Унарные операции обработаны отдельно, чтобы `" - 2 * 3"` понималось как $(-(2))\ast 3$ или $-(2\ast 3)$ в зависимости от желаемой семантики; предложенная грамматика делает унарный минус выше умножения (т.е. $-x^2$ парсится как $-(x^2)$) — при необходимости можно изменить порядок.
Взаимодействие лексера и парсера:
- Лексер разбивает вход на токены: $NUMBER$ (например, последовательность цифр и точка), $IDENTIFIER$ (буквы/цифры/подчеркивания), символы-операторы и скобки; пропускает пробелы и комментарии; сообщает парсеру поток токенов с позициями (номер строки/столбца) и значениями (лексемы).
- Парсер читает токены и строит дерево разбора (AST) согласно грамматике. Лексер должен давать «чистые» токены: например, знак минус обычно возвращается как отдельный токен '-', а не включается в $NUMBER$ (чтобы у парсера был выбор распознать унарный минус или бинарный).
- Для корректной диагностики ошибок лексер передаёт позиции токенов; парсер может запросить следующий токен (lookahead) или несколько для принятия решений (LL(k)).
Типичные ошибки и неоднозначности:
- Лексические ошибки: неизвестный символ, некорректный литерал числа (например, несколько точек), неопознанная последовательность — генерация ошибки лексера.
- Синтаксические ошибки: неожиданный токен, неполное выражение, незакрытая скобка — парсер сообщает позицию и ожидаемые токены.
- Неоднозначная грамматика приводит к конфликтам у генераторов парсеров:
- Shift/reduce — когда парсер не знает, сделать ли сдвиг (прочитать ещё токен) или редьюс (свернуть правило). Часто возникает при сочетаниях префиксных/постфиксных операторов или при конструкции "dangling else".
- Reduce/reduce — когда два разных сокращения возможны в одной точке; это «худшая» неоднозначность.
- Примеры неоднозначностей:
- Если не указать, что '^' правосторонний, строка \(a^b^c\) может иметь два дерева: $(a^b{)}^c$ или $a^{(b^c)}$.
- Общая неоднозначная грамматика: $S::=SS{\mid }^{\prime }{a}^{\prime }$ даёт несколько деревьев для строки ${}^{\prime }aa{a}^{\prime }$.
- Решения:
- Переписать грамматику по уровням (как выше) для явного задание приоритетов и ассоциативности.
- Для генераторов Yacc/Bison — использовать директивы precedence/associativity (например, %left, %right).
- Для LL-парсеров — устранить левую рекурсию и использовать EBNF-формы или парсер Pratt/precedence-climbing.
- Для ошибок — реализовать восстановление после ошибки (panic mode, синтаксическое предсказание) и выдачу информативных сообщений с позициями.
Краткая рекомендация: для простого выраженческого языка — использовать уровневую грамматику (как приведено), лексер отдаёт токены без знака в числах, а парсер строит AST; для генераторов парсеров использовать либо EBNF для LL-парсеров, либо левую рекурсию для LR, и явно задавать ассоциативность/приоритет для операторов, чтобы избежать конфликтов.