Грамматика с явными уровнями приоритета и ассоциативности (неоднозначность устранена структурой правил):
Нетерминалы: $\text{Expr},\text{Term},\text{Unary},\text{Power},\text{Primary}$.
Терминалы: $+-,\ast ,/,{}^{,}(,),\text{number},\text{id}$.
Грамматика (неоднозначная форма с управлением приоритетами и ассоциативностью):
$$\begin{array}{rl}\text{Expr}& \to \text{Expr}+\text{Term}\mid \text{Expr}-\text{Term}\mid \text{Term}\\ \text{Term}& \to \text{Term}\ast \text{Power}\mid \text{Term}/\text{Power}\mid \text{Power}\\ \text{Power}& \to {\text{Primary}}^{\text{Power}}\mid \text{Primary}\\ \text{Primary}& \to (\text{Expr})\mid \text{number}\mid \text{id}\mid +\text{Primary}\mid -\text{Primary}\end{array}$$
Объяснение выбора:
- Сложение/вычитание реализованы лево-рекурсивно в $\text{Expr}$ → это обеспечивает левую ассоциативность для $+$ и $-$ (например, $1-2-3$ парсится как $(1-2)-3$).
- Умножение/деление аналогично в $\text{Term}$ — более высокий приоритет, также левая ассоциативность.
- Возведение в степень через правую рекурсию в $\text{Power}$ (${\text{Primary}}^{\text{Power}}$) даёт правую ассоциативность для \(^\) (например, $2^{3^4}$ означает $2^{(3^4)}$).
- Унарные $+$ и $-$ включены в $\text{Primary}$ или можно вынести в отдельный уровень, в зависимости от желаемого отношения с \(^\): в приведённой грамматике \(^\) имеет более высокий приоритет чем унарный (то есть $-2^2$ парсится как $-(2^2)$). (Если нужно, чтобы унарный был сильнее \(^\), поменять порядок уровней.)
Анализ неоднозначности и способы её устранения:
- Неоднозначность возникает, если использовать шаблонную продукцию вида $\text{E}\to \text{E op E}\mid (\text{E})\mid \text{number}$: одна и та же строка имеет много деревьев (нет заданных приоритетов/ассоциативности).
- Устранить неоднозначность можно:
1. Разделить грамматику на уровни по приоритету (как выше): каждый уровень — отдельный нетерминал.
2. Задать ассоциативность через направление рекурсии: левая рекурсия → левая ассоциативность; правая рекурсия → правая ассоциативность.
3. Для генераторов/парсеров (Yacc/Bison) использовать директивы приоритета/ассоциативности (%left,\ %right,\ %nonassoc).
4. Применять алгоритмы разбора с учётом приоритетов (precedence climbing, Pratt parser) — не меняют грамматику, но разрешают конфликты при разборе.
- Особые замечания по унарному минусу и степеням: соглашение о том, что сильнее — унарный оператор или степень, должно быть явно отражено в грамматике (изменением уровня для унарного оператора), иначе выражения вроде $-2^2$ будут интерпретироваться по-разному.
Пример LL(1)-дружественной формы (без левой рекурсии, эквивалент по приоритетам):
$$\begin{array}{rl}\text{Expr}& \to \text{Term}\text{Expr’}\\ \text{Expr’}& \to +\text{Term}\text{Expr’}\mid -\text{Term}\text{Expr’}\mid \epsilon \\ \text{Term}& \to \text{Power}\text{Term’}\\ \text{Term’}& \to \ast \text{Power}\text{Term’}\mid /\text{Power}\text{Term’}\mid \epsilon \\ \text{Power}& \to \text{Unary}\text{Power’}\\ \text{Power’}& {\to }^{}\text{Power}\mid \epsilon \\ \text{Unary}& \to +\text{Unary}\mid -\text{Unary}\mid \text{Primary}\\ \text{Primary}& \to (\text{Expr})\mid \text{number}\mid \text{id}\end{array}$$
Эта форма однозначна и пригодна для реализации в рекурсивном нисходящем парсере или в LL(1)-анализаторе.
Кратко: используйте уровни нетерминалов для приоритета и направление рекурсии для ассоциативности; при помощи этого грамматика становится однозначной.