Вопрос #1576257

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