Кратко: причина неоднозначности — одна и та же входная строка допускает несколько деревьев разбора; способы устранения делятся на три группы: перепроектирование грамматики (устранение неоднозначных правил), установка приоритетов/ассоциативности в парсере, и лексическое разделение токенов. Ниже — что делать, примеры и последствия для генерации кода.
1) Типичные источники неоднозначности
- Операторы без явных приоритетов/ассоциативности (например $+$ и $\ast$ или право/лево ассоциативность).
- Правило "dangling else":
$S\to \text{if}E\text{then}S\mid \text{if}E\text{then}S\text{else}S\mid \text{other}$.
- Общие префиксы и отсутствие факторинга (нужен left‑factoring).
- Контекстно-зависимые токены (унарный и бинарный минус) — лексическая неоднозначность.
- Reduce/reduce и shift/reduce конфликты в LALR/GLR/YACC.
2) Перепроектирование грамматики (предпочтуется, когда возможно)
- Ввести уровни для приоритетов (разложить выражения по уровням):
$E\to E+T\mid T$
$T\to T\ast F\mid F$
$F\to (E)\mid \text{id}$
Это устраняет неоднозначность для арифметики и задаёт левую ассоциативность.
- Устранить "dangling else" через явное разделение матчед/не‑матчед конструкций:
$S\to M\mid U$
$M\to \text{if}E\text{then}M\text{else}M\mid \text{other}$
$U\to \text{if}E\text{then}S$
- Применить left‑factoring: вместо $A\to \alpha {\beta }_1\mid \alpha {\beta }_2$ писать $A\to \alpha A^{\prime }$, $A^{\prime }\to {\beta }_1\mid {\beta }_2$.
- Для LL‑парсеров — удалить левую рекурсию.
Последствие для codegen: перепроектированная грамматика даёт однозначное AST и простую детерминированную генерацию кода; но структура дерева может измениться (добавятся промежуточные нетерминалы), что потребует адаптации трансляторов и правил оптимизаций.
3) Приоритеты и ассоциативность в генераторах парсеров
- Использовать директивы (например в Yacc/Bison):
%left '+', %left '*' или %right '^'.
Это решает shift/reduce конфликты без переписывания грамматики.
- Для неявных конфликтов — определить приоритеты лексем/правил или дать предпочтение shift/reduce.
Последствие для codegen: AST создаётся согласно приоритетам парсера; легко внедрить, но поведение может отличаться от "интуитивной" грамматики — документировать приоритеты обязательно.
4) Лексическое разделение
- Разделять токены, которые выглядят одинаково в разных контекстах: например давать унарному минусу отдельный токен $\text{NEG}$ или вычислять его в парсере (помещать в правило для унарных операторов).
- Ввести контекстно-зависимую лексему через режимы лексера (start conditions), чтобы отличать, например, идентификатор от ключевого слова в разных местах.
Последствие для codegen: упрощает синтаксический анализ и даёт более чистые AST‑узлы для семантики; требует дополнительных усилий при лексере и может осложнить подсветку/инкрементальную обработку.
5) Альтернативы: GLR/parse forest + семантика
- Если грамматика принципиально неоднозначна и вы хотите сохранить выразительность, используйте GLR/parse forest и затем применяйте семантические фильтры/динамическое разрешение конфликтов (например выбирать исходя из типов или контекста).
Последствие для codegen: сначала получаете лес разбора; нужно отдельное правило выбора единственного AST — усложняет компилятор и ухудшает предсказуемость/производительность.
6) Практические шаги для устранения неоднозначности (рекомендуемая последовательность)
- Найти конфликты: включить отчёты парсера (Yacc/Bison warnings), запустить фуззинг примеров.
- Попробовать простое переписывание (factoring, уровни) — если возможно, это лучший вариант.
- Если переписывание громоздко, использовать приоритеты/ассоциативность в парсере.
- Разделять токены в лексере для контекстных различий.
- Если грамматика не поддаётся, применять GLR и семантические фильтры.
- Наконец, стандартизовать форму AST (canonicalization) перед генерацией кода, чтобы codegen получал однозначную структуру.
7) Влияние на генерацию кода — сводка
- Неоднозначность без явного разрешения может приводить к разным, несогласованным версиям сгенерированного кода.
- Правила приоритетов/рефакторинг дают детерминированный AST — проще оптимизировать и тестировать.
- GLR + семантика даёт гибкость, но усложняет фазу трансформаций и оптимизаций.
- Лексическое разделение улучшает точность синтаксического дерева и упрощает codegen, но меняет контракт между лексером и парсером.
Заключение (коротко): при возможности перепроектируйте грамматику (факторинг + уровни), иначе используйте приоритеты/ассоциативность и лексические режимы; для сохранения всей выразительности применяйте GLR + семантику, но обязательно канонизируйте AST перед генерацией кода.