Грамматика
$S\to SS\mid a\mid b$ амбигуозна.
Пример строки с двумя разными деревьями разбора: возьмём $w=aba$.
Два различных вывода (скобочная группировка отражает структуру двоичного конкатенирования):
1) $((ab)a)$:
$S\Rightarrow SS\Rightarrow SSS\Rightarrow aSS\Rightarrow abS\Rightarrow aba$.
2) $(a(ba))$:
$S\Rightarrow SS\Rightarrow aS\Rightarrow aSS\Rightarrow abS\Rightarrow aba$.
Эти два дерева дают один и тот же выводный ряд символов $aba$, но имеют разную структуру — отсюда неоднозначность.
Следствия для парсинга:
- Поскольку грамматика неоднозначна, она не может быть распознаваема как детерминированная LR(1)-грамматика (всякая LR(k)-грамматика однозначна), следовательно исходная грамматика не является LR(1).
- Она также не является LL(1) (LL(1) требует единственного выбора продукции по первому символу при предсказании; неоднозначность и пересекающиеся FIRST-наборы препятствуют этому).
Как модификации влияют:
- Чтобы получить однозначную и LL(1)-совместимую грамматику для множества всех непустых строк над $\{a,b\}$, можно факторизовать по первому символу, например
$$S\to aA\mid bA,A\to aA\mid bA\mid \epsilon .$$ Здесь FIRST-альтернатив для $S$ раздельны ($\{a\}$ и $\{b\}$), грамматика однозначна и является LL(1) (а значит и LR(1)).
- Если сделать левую рекурсию, например
$$S\to Sa\mid Sb\mid a\mid b,$$ то грамматика может быть однозначной, но из‑за левой рекурсии она не LL(1) без преобразований; LR(1)-парсер с такими правилами справится (LR(1) нормально обрабатывает левую рекурсию).
- В общем: устранение двоичного правила конкатенации $S\to SS$ в пользу правых/левых линейных или факторизованных правил делает грамматику однозначной; факторизация даёт LL(1), а леворекурсивная форма — удобна для LR(1).