Кратко — возможные подходы, пример преобразования и ограничения.
1) Правила приоритетов и ассоциативности
- Задают семантику разбора без изменения грамматики: указывают, какой оператор имеет больший приоритет и какая ассоциативность (левая/правая/нет).
- В парсерах LR/GLR/других часто используются директивы вида (yacc/bison): %left '+', %left '*', где порядок деклараций задаёт приоритет; директивы решают преимущественно shift/reduce-конфликты.
- Ограничение: применимы только к конфликтам, порождённым операторами; не устраняют общую неизбежную неоднозначность языка (reduce/reduce-конфликты не всегда решаются).
2) Рефакторинг грамматики по уровням приоритетов (устранение неоднозначности синтаксически)
- Идея: выделить уровни выражений для каждого приоритета, задать ассоциативность через рекурсию.
- Пример исходной неоднозначной грамматики:
$$S\to S+S\mid S\ast S\mid (S)\mid id$$ - Преобразим правила, задав $\ast$ выше по приоритету чем $+$ и обе операции левоассоциативны:
$$\begin{array}{rl}E& \to E+T\mid T\\ T& \to T\ast F\mid F\\ F& \to (E)\mid id\end{array}$$ Эта грамматика однозначна относительно приоритетов и левой ассоциативности.
3) Преобразование для LL(1) (убрать левую рекурсию и выполнить left-factoring)
- Устранение левой рекурсии для верхней грамматики:
$$\begin{array}{rl}E& \to T{E}^{\prime }\\ E^{\prime }& \to +T{E}^{\prime }\mid \epsilon \\ T& \to F{T}^{\prime }\\ T^{\prime }& \to \ast F{T}^{\prime }\mid \epsilon \\ F& \to (E)\mid id\end{array}$$ - Результат: грамматика подходит для LL(1) (при корректных FIRST/FOLLOW), даёт ту же структуру разбора (левая ассоц.).
4) Преобразование для LR(1)
- LR(1) обычно не требует удаления левой рекурсии; достаточно оставить естественную грамматику и при необходимости добавить директивы приоритетов/ассоц.
- Пример (yacc-подобно):
%left '+'
%left '*'
%%
expr: expr '+' expr
| expr '*' expr
| '(' expr ')'
| id
- Если после генерации таблиц остаются конфликты, применяют приоритеты или рефакторинг.
5) Особые случаи (правоассоциативные операторы, унарные операторы)
- Правоассоциативный оператор (например, возведение в степень) задают правой рекурсией:
$$P\to A\mid A\hat{}P$$ или эквивалентно при LL(1) с соответствующей обработкой.
- Унарные операторы часто требуют отдельной нетерминальной ступени (F ::= '+' F | '-' F | atom) чтобы разрешить амбигьюити.
6) Ограничения и замечания
- Некоторые языки фундаментально неоднозначны: существуют контекстно‑свободные языки, для которых нет неоднозначной грамматики (пример):
$$L=\{a^i{b}^j{c}^k\mid i=j\text{или}j=k\}$$ — этот язык является неразрешимо неоднозначным (there exist inherently ambiguous CFLs).
- Преобразование в LL(1) не всегда возможно без значительного усложнения грамматики; некоторые конструкции потребуют увеличения числа нетерминалов или потерю «натуральности» дерева разбора.
- Директивы приоритета/ассоциативности решают в основном shift/reduce-конфликты; reduce/reduce‑конфликты требуют рефакторинга или более мощного парсера.
- LR(1) (или LALR(1)) покрывает гораздо больше грамматик, чем LL(1), но генерация таблиц может привести к конфликтам, требующим вмешательства.
- Для сохранения всех синтаксических разборов (если нужно работать с неоднозначностью) используют GLR или Earley, которые строят лесы зависимостей; это нужно, если неоднозначность семантически значима.
Вывод: стандартный путь — либо явно задать приоритеты/ассоциативность (если это только операторы), либо синтаксически рефакторить грамматику по уровням приоритетов и при необходимости убирать левую рекурсию / делать left-factoring для LL(1). Для сложных/встроенно неоднозначных языков применяют LR-парсеры с директивами или GLR/Earley.