1) Доказательство неоднозначности (конкретный пример).
Возьмём строку $aaa$. Для грамматики
$S\to SS\mid a\mid b$ есть, например, две различные левого-порядка продуктивности (и соответствующие разные деревья):
Вариант A:
$$S\Rightarrow SS\Rightarrow SSS\Rightarrow aSS\Rightarrow aaS\Rightarrow aaa.$$
Вариант B:
$$S\Rightarrow SS\Rightarrow aS\Rightarrow aSS\Rightarrow aaS\Rightarrow aaa.$$
Эти два вывода дают разные структуры разбора (разные бинарные скобочные разбиения):
$$((aa)a)\text{и}(a(aa)),$$ то есть одна и та же строка порождается двумя различными синтаксическими деревьями. Следовательно грамматика неоднозначна.
2) Недвусмысленная грамматика того же языка (все непустые строки над $\{a,b\}$).
Возьмём грамматику
$$S\to a\mid b\mid aS\mid bS.$$ Она порождает ровно все непустые строки над $\{a,b\}$: каждое применение продукции добавляет в начало (первый символ строки), а базовые продукции дают последний символ.
3) Доказательство эквивалентности и недвусмысленности.
- Покажем, что грамматика порождает любое $w\in \{a,b{\}}^{+}$. Пусть $w=x_1{x}_2\dots x_n$ ($x_i\in \{a,b\}$, $n\ge 1$). Тогда последовательность продукций
$$S\Rightarrow x_{1}S\Rightarrow x_1{x}_{2}S\Rightarrow \cdots \Rightarrow x_1\dots x_{n-1}S\Rightarrow x_1\dots x_n$$ (в последнем шаге продукция $S\to x_n$) даёт $w$.
- Обратно, любая продукция данной грамматики либо даёт строку длины $1$ ($a$ или $b$), либо снимает первый символ и рекурсивно порождает остаток. Значит язык равен $\{a,b{\}}^{+}$.
- Недвусмысленность: по индукции по длине строки. Для $|w|=1$ есть ровно одна продукция ($S\to a$ или $S\to b$). Пусть для всех строк длины $<n$ разбор уникален. Для $|w|=n\ge 2$ первый символ $x_1$ однозначно определяет, какая продукция использована в корне ($S\to x_1$ если $n=1$, иначе $S\to x_{1}S$). После этого остаётся разбирать хвост $x_2\dots x_n$ длины $n-1$, и по предположению индукции его разбор уникален. Следовательно разбор для $w$ единственен. Значит грамматика недвусмысленна.
4) Алгоритм синтаксического разбора (и доказательство корректности).
Алгоритм (итеративный, линейный):
- Вход: строка $w$.
- Если $|w|=0$ — отклонить (грамматика даёт только непустые строки).
- Для i от $1$ до $|w|-1$:
- проверять, что $w_i\in \{a,b\}$; записать производство $S\to w_{i}S$.
- Проверить $w_{|w|}\in \{a,b\}$; записать производство $S\to w_{|w|}$.
- Построенные последовательность продукций даёт вывод для $w$.
Сложность: один проход по символам, то есть $O(|w|)$.
Доказательство корректности:
- Корректность (soundness): каждая записанная продукция допустима в грамматике, и их последовательное применение даёт ровно $w$ (см. конструкцию в пункте 3).
- Полнота: если $w$ порождается грамматикой, то первый символ $x_1$ обязано появиться из продукции вида $S\to x_{1}S$ (если $|w|>1$) или $S\to x_1$ (если $|w|=1$); поэтому алгоритм, который строго следует первому символу и рекурсивно разбирает хвост, восстановит этот единственный разбор. По индукции на длину алгоритм найдёт и единственный возможный разбор.
Таким образом предложенная грамматика задаёт тот же язык, она недвусмысленна, и приведённый линейный алгоритм корректно и эффективно строит её единственный синтаксический разбор.