1) Показательство неоднозначности

Грамматика
S -> S S | 'a' | 'b'
порождает все непустые строки над алфавитом {a,b} $любойразбиениемнаотдельныесимволы$. Но она неоднозначна: одна и та же строка может иметь разные деревья вывода $разнуюбинарнуюассоциациюконкатенации$.

Пример: строка "aba".

Два различных синтаксических дерева $вскобочнойформе$:

Разбиение как $a$$ba$:
S
├─ 'a'
└─ S
├─ 'b'
└─ 'a'

Левосторонняя $однаиз$ последовательностей вывода:
S => S S => 'a' S => 'a' S S => 'a' 'b' 'a'.

Разбиение как $ab$$a$:
S
├─ S
│ ├─ 'a'
│ └─ 'b'
└─ 'a'

Другой вывод:
S => S S => S S S => 'a' 'b' S => 'a' 'b' 'a'.

Оба дерева дают одну и ту же терминальную строку "aba", но деревья разные — значит грамматика неоднозначна. Более общо: для любой строки длины n≥3 возможны разные бинарные разбиения (число возможных разбиений — каталановы числа >1 при n≥3).

2) Эквивалентная неамбициозная КС-грамматика

Язык — все непустые строки над {a,b}, то есть $a|b$+. Можно дать праволинейную $регулярную$ грамматику, однозначно задающую этот язык:

S -> 'a' S | 'b' S | 'a' | 'b'

Эта грамматика однозначна: каждое вхождение символа в строке соответствует одному конкретному применению правила, то есть разбивка на символы фиксирована $праворекурсивныйвыводслеванаправо$, следовательно уникальное дерево вывода для каждой строки. Она порождает именно все непустые строки и только их, поэтому эквивалентна исходной.

3) Pushdown-автомат, распознающий тот же язык

Поскольку язык регулярный, можно построить детерминированный PDA, фактически не использующий стек, но принимающий по конечному состоянию и требующий хотя бы одного символа.

Формальное описание $одноизвозможных$:

M = $Q,\Sigma ,\Gamma ,\delta ,q0,Z0,F$,
Q = {q0, q1}, Σ = {a,b}, Γ = {Z0},
q0 — начальное, Z0 — начальный символ стека, F = {q1}.

Переходы $\delta$:

δ$q0,a,Z0$ = {$q1,Z0$}δ$q0,b,Z0$ = {$q1,Z0$}δ$q1,a,Z0$ = {$q1,Z0$}δ$q1,b,Z0$ = {$q1,Z0$}

Интерпретация: при чтении первого символа переходим из q0 в принимающее q1, далее на каждом символе остаёмся в q1; стек не меняется. Прием по конечному состоянию гарантирует, что пустая строка не принимается, а любая непустая — принимается. $МожнодатьэквивалентныйPDAсприёмомпопустомустеку,еслипредпочитатьтакойвариант.$

4) Влияние неоднозначности на парсинг и семантический анализ

Парсинг:

Неоднозначная грамматика даёт несколько деревьев разбора для одной и той же входной строки. Для генерации одного $детерминированного$ разбора требуются правила разрешения неоднозначностей $приоритеты/ассоциативность$ либо перестройка грамматики в неамбициозную форму.Использование стандартных детерминированных парсеров $LL(k),LR(k)$ на неоднозначной грамматике обычно невозможно либо вызывает конфликты $shift/reduce,reduce/reduce$. Генераторы парсеров либо отвергнут грамматику, либо потребуют ручной настройки разрешений.Общее количество разных деревьев может быть экспоненциальным, поэтому алгоритмы, которые перечисляют все деревья $например,обобщённыепарсерыGLL/GLR,CYK/Earleyсмодификациями$, могут иметь большие накладные расходы по памяти и времени.

Семантический анализ:

Семантика обычно привязывается к конкретной структуре дерева $AST$. При существовании нескольких деревьев возникает неоднозначность значения выражения/программы: какие семантические действия выполнять?Нельзя корректно выполнять семантические действия до разрешения неоднозначности — иначе результат будет зависеть от выбранного разбора или реализующей стратегии парсера.Практически: в компиляторах неоднозначности разрешают в грамматике $задаваяприоритеты/ассоциативность$ или выбирают однозначную грамматику, чтобы получить уникальное AST для последующей семантики $типизация,проверка,генерациякода$.

Вывод: в данном случае язык не является «внутренне неоднозначным» — существуют эквивалентные неамбициозные грамматики $например,праворекурсивнаявыше$. Поэтому практическое решение — переписать грамматику в однозначную форму или задать унаследованные правила разрешения, чтобы парсинг и семантический анализ были детерминированными и эффективными.