Ниже — сжатое, но полноценное руководство по устранению неоднозначности на примере арифметической грамматики, с объяснением последствий для LR- и LL-парсеров и альтернативными приёмами.

1) Проблема (пример неоднозначной грамматики)
Исходная (неоднозначная) грамматика:
E -> E + E
E -> E * E
E -> ( E )
E -> id

Для строки id + id * id эта грамматика даёт два разбора:

E -> E + E (правый E -> E E) — соответствуют дереву a + (b c)E -> E E (левый E -> E + E) — соответствуют дереву (a + b) c

То есть не определены приоритеты операций и их ассоциативность.

2) Способы устранения неоднозначности

Изменить грамматику, выделив уровни приоритета (разделить нетерминалы).Задать приоритеты и ассоциативность в генераторе парсеров (например, %left/%right/%nonassoc в yacc/bison), не меняя сильно правил.Использовать алгоритмы парсинга с поддержкой приоритетов (Pratt, precedence-climbing) или семантические правила («встроить» предпочтение в действия).

3) Пример «после исправления» — выделение приоритетов и левой ассоциативности
Стандартный исправленный вариант (лево-рекурсивный, * выше +, обе — левая ассоциативность):

E -> E + T
E -> T
T -> T * F
T -> F
F -> ( E )
F -> id

Эта грамматика однозначна для обычных арифметических выражений: * имеет более высокий приоритет, + — ниже; обе операции лево-ассоциативны (потому что используются леворекурсивные правила).

4) Версия, пригодная для LL(1) (исключаем левую рекурсию и делаем факторизацию)
Для рекурсивного нисходящего парсера удобнее:

E -> T E'
E' -> + T E' | ε
T -> F T'
T' -> * F T' | ε
F -> ( E ) | id

Эта форма однозначна и обычно пригодна для LL(1) (при удовлетворении FIRST/FOLLOW условий).

5) Как это влияет на LR-парсер (bottom-up, например yacc/bison)

На исходной неоднозначной грамматике LR-таблица обычно содержит shift/reduce (и/или reduce/reduce) конфликты. Генератор выдаст предупреждение о конфликтах.При использовании приоритетов/ассоциативности (в yacc: %left '+', %left '*', порядок деклараций задаёт относительный приоритет) конфликт shift/reduce разрешается автоматически: если следующий токен имеет больший приоритет — выполняется shift (тем самым даётся более высокий приоритет операции); если приоритеты равны — поведение определяется ассоциативностью (%left -> reduce, %right -> shift).При изменении грамматики на разделённые нетерминалы (E, T, F) LR-таблица станет без конфликтов (обычно), потому что грамматика уже однозначна — парсер формирует однозначное дерево.

Замечание: LR-парсеры отлично работают с леворекурсией, так что лево-рекурсивная форма (E -> E + T) не проблемна.

6) Как это влияет на LL-парсер (top-down, рекурсивный спуск)

Исходная лево-рекурсивная грамматика (E -> E + E | ...) недопустима для LL(1) — приводит к бесконечной рекурсии при рекурсивном спуске. Требуется убрать левую рекурсию и, возможно, сделать left-factoring.Приведённая выше LL-версия (E -> T E' ...) — типичный приём для получения LL(1). Такой парсер реализует ту же семантику (приоритеты и левую ассоциативность) явно в правилах.В отличие от yacc-подхода, в чистом LL-парсере обычно надо менять грамматику; «аннотаций приоритета» как в yacc обычно нет (хотя некоторые генераторы позволяют задавать правила приоритета вручную).

7) Примеры деклараций приоритета в yacc/bison (альтернатива переписыванию грамматики)
Пример в bison-подобном синтаксисе:
%token ID
%left '+'
%left ''
%%
expr: expr '+' expr
| expr '' expr
| '(' expr ')'
| ID
;
%%
Порядок %left задаёт приоритет: более поздняя декларация — более высокий приоритет (т.е. '*' выше, если declared after '+'). Также можно использовать %right для правой ассоциативности (например для '^').

8) Иные замечания

Ассоциативность: левая рекурсия даёт левую ассоциативность; правая рекурсия — правую (E -> T | E '+' T -> right recursion would be E -> T E'' with E'' -> '+' T E'', etc. — практический способ для рекурсивного спуска правой ассоциативности).Если нужно строгое дерево разбора (AST) вместо полного parse tree, часто проще сохранять правила построения AST (семантические действия) так, чтобы всегда строился желаемый AST даже при исходной неоднозначной грамматике; но это менее желательно, чем убирать неоднозначность грамматики.Альтернативы: precedence-climbing / Pratt-парсер упрощают реализацию анализатора выражений и легко выражают разную приоритетность и ассоциативность без сложной грамматики.

Короткое резюме

Убрать неоднозначность удобнее всего, выделив уровни (E, T, F) и/или указав приоритеты и ассоциативность.LR-парсеры нормально работают с левой рекурсией; неоднозначность проявится в конфликтах, которые можно разрешить приоритетами.LL-парсеры требуют удаления левой рекурсии и, возможно, left-factoring; грамматика меняется явным образом.

Если хотите, могу:

показать конкретный разбирающий пример (таблицы LR(0)/LR(1) с конфликтами); илидать код для yacc/bison + примеры входов и сообщения о конфликтах; илипреобразовать произвольную неоднозначную арифметическую грамматику в LL(1) шаг за шагом.