Приведу примеры двух различных разборов, объяснение, и неамбиграфный вариант грамматики с приёмами и ограничениями.
1) Исходная неоднозначная грамматика:
$E\to E+E\mid E\ast E\mid (E)\mid id$.
2) Два различных дерева разбора для строки $id+id\ast id$:
- Разбор A (плюс на верхнем уровне, умножение внутри правого поддерева), даёт семантику $id+(id\ast id)$:
$$E\Rightarrow E+E\Rightarrow id+E\Rightarrow id+(E\Rightarrow E\ast E\Rightarrow id\ast id)$$
- Разбор B (умножение на верхнем уровне, плюс внутри левого поддерева), даёт семантику $(id+id)\ast id$:
$$E\Rightarrow E\ast E\Rightarrow (E\Rightarrow E+E\Rightarrow id+id)\ast id$$
Оба разбора порождают одну и ту же строку, но разные абстрактные синтаксические деревья (AST) и, следовательно, разные вычисления.
3) Почему неоднозначность неприемлема для парсеров:
- Парсеру нужно однозначно выбрать правило и структуру AST для дальнейших этапов (семантика, генерация кода). Неоднозначность даёт несколько возможных AST → неоднозначные семантические действия.
- Синтаксические анализаторы (LR, LL) при неоднозначной грамматике обнаруживают конфликты (shift/reduce, reduce/reduce) и не могут однозначно строить разбор без дополнительных правил (приоритеты/ассоциативность).
- Практически: двусмысленность усложняет статическую проверку, оптимизации и приводит к непредсказуемому поведению.
4) Преобразование в эквивалентную (неоднозначность устранена) LL(1)-подобную грамматику. Требуемые решения: ввести уровни приоритета и ассоциативность, убрать левую рекурсию (для LL):
- Сначала выразим приоритеты (умножение выше сложения) и левую ассоциативность:
$$\begin{array}{rl}E& \to E+T\mid T\\ T& \to T\ast F\mid F\\ F& \to (E)\mid id\end{array}$$
- Для получения LL(1) убрать левую рекурсию (приём удаления левой рекурсии):
$$\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}$$
Этот вариант однозначен, реализует приоритет $\ast >+$ и левую ассоциативность для обоих операторов, и является пригодным для LL(1) парсинга (при корректном расчёте FIRST/FOLLOW и отсутствии конфликтов).
5) Приёмы и ограничения преобразования:
- Приёмы: удаление левой рекурсии (для LL), левое факторирование (если есть общие префиксы), введение нетерминалов для уровней приоритета/ассоц.
- Ограничения:
- Преобразование фиксирует приоритеты и ассоциативность; если исходная неоднозначная грамматика намеренно допускала разные интерпретации, эта информация теряется (обычно это желаемо).
- Не все неоднозначные грамматики имеют тривиально эквивалентную однозначную форму без изменения языка или семантики; иногда нужна внешняя политика разрешения (директивы приоритетов в генераторах парсеров, семантические правила).
- Удаление левой рекурсии меняет форму деревьев (но сохраняет вычислительную семантику при правильно выбранных правилах ассоциации).
- LL(1) требовательна к отсутствию конфликтов FIRST/FIRST и FIRST/FOLLOW; для более сложных языковых конструкций может потребоваться переход на LR(1) или использование приоритетов в генераторе (yacc/bison) вместо полного переписывания грамматики.
Кратко: для $id+id\ast id$ неоднозначность даёт два разбора ( $id+(id\ast id)$ и $(id+id)\ast id$ ); для практических парсеров грамматику преобразуют, вводя уровни приоритета и удаляя левую рекурсию, как показано выше, при этом обязательно явно задают требуемую ассоциативность и учесть ограничения преобразования.