Грамматика
$$S\to S+S\mid S\ast S\mid (S)\mid a$$ неоднозначна. Пример строки с двумя различными деревьями: $a+a+a$.
Две различные левые вывода/дерева (один соответствует $(a+a)+a$, другой — $a+(a+a)$):
1) Первый вывод (лево‑ассоциативная ветвь):
$$S\Rightarrow S+S\Rightarrow S+S+S\Rightarrow a+S+S\Rightarrow a+a+S\Rightarrow a+a+a$$ (соответствует разбиению $(a+a)+a$).
2) Второй вывод (право‑ассоциативная ветвь):
$$S\Rightarrow S+S\Rightarrow a+S\Rightarrow a+S+S\Rightarrow a+a+S\Rightarrow a+a+a$$ (соответствует разбиению $a+(a+a)$).
Аналогично неоднозначность видна для строки $a+a\ast a$: возможны деревья $(a+a)\ast a$ и $a+(a\ast a)$.
Чтобы устранить неоднозначность, вводят уровни (приоритеты) и ассоциативность. Стандартная не неоднозначная грамматика с приоритетом $\ast$ выше $+$ и левой ассоциативностью:
$$\begin{array}{rl}E& \to E+T\mid T\\ T& \to T\ast F\mid F\\ F& \to (E)\mid a\end{array}$$ Здесь $E$ — выражения с $+$, $T$ — термы с $\ast$, $F$ — множители. В этой грамматике:
- операция $\ast$ имеет более высокий приоритет (потому что производится на уровне $T$),
- обе операции левоассоциативны (благодаря левой рекурсии).
Пример однозначного разбора:
$$a+a\ast a\text{разбирается как}E\Rightarrow E+T\Rightarrow T+T\Rightarrow F+T\Rightarrow a+(T\ast F)\Rightarrow a+(a\ast a)$$ то есть однозначно $a+(a\ast a)$.
Краткое обоснование однозначности: синтаксическая структура разделена по уровням (E, T, F), и каждое нетерминальное правило определяет единственный способ разбиения по оператору соответствующего приоритета; поэтому для фиксированной строки порядок узлов определяется однозначно.