Грамматика:
$$S\to SS\mid aSb\mid \epsilon$$
1) Язык, порождённый грамматикой.
$$L(G)=\{w\in \{a,b{\}}^{\ast }\mid {\#}_a(w)={\#}_b(w)\text{и для каждой позиции}u\text{(префикс}w){\#}_a(u)\ge {\#}_b(u)\},$$ то есть язык корректно сбалансованных скобок одного типа (аналог Dyck-1, ставим \(a='('\), \(b=')'\)).
Краткое объяснение: правило $aSb$ даёт вложенные пары $a\dots b$, правило $SS$ — конкатенацию корректных фрагментов, $\epsilon$ — пустую строку. Все и только корректно сбалансированные строки получаются.
2) Неоднозначность грамматики.
Грамматика неоднозначна. Контрпример: $w=ababab$ (эквивалентно "()()()"). Две разные левосторонние вывoдные последовательности (показываю схематично):
Первый вариант (дерево вида $((SS)S)$):
$$S\Rightarrow SS\Rightarrow SSS\Rightarrow (aSb)SS\Rightarrow (a\epsilon b)SS\Rightarrow abSS\Rightarrow ab(aSb)S\Rightarrow ab(a\epsilon b)S\Rightarrow ababS\Rightarrow abab(aSb)\Rightarrow ababab.$$
Второй вариант (дерево вида $(S(SS))$):
$$S\Rightarrow SS\Rightarrow SSS\Rightarrow S(aSb)S\Rightarrow S(a\epsilon b)S\Rightarrow SabS\Rightarrow (aSb)abS\Rightarrow (a\epsilon b)abS\Rightarrow ababS\Rightarrow abab(aSb)\Rightarrow ababab.$$
Получены разные деревья вывода для одного слова ⇒ грамматика неоднозначна.
3) Регулярность и детерминируемость.
- Язык не является регулярным. Простая аргументация: для любого $p$ (pumping length) строка $a^p{b}^p$ принадлежит $L(G)$, но по лемме о накачке регулярных языков нельзя накачать часть только из блока $a$ так, чтобы равенство чисел $a$ и $b$ сохранялось — противоречие.
- Язык является детерминируемым в смысле детерминированного КСЯ (DPDA) и является LR(1) (и даже LL(1)). Это стандартный детерминированный язык скобочной последовательности одного типа.
DPDA (одно состояние $q$, маркер дна $Z_0$, символ стека $A$):
$$\begin{array}{rl}& \delta (q,a,Z_0)=(q,A{Z}_0),\delta (q,a,A)=(q,AA),\\ & \delta (q,b,A)=(q,\epsilon ),\\ & \text{при конце входа: если стек}{Z}_0\text{— принять, иначе отклонить.}\end{array}$$ На $a$ — детерминированно пушим $A$; на $b$ — если верх стека $A$, попаем; иначе — ошибка. Это детерминированный автомат-стек, принимающий $L(G)$.
4) Предложение по преобразованию грамматики для парсинга в компиляторе.
Заменить неоднозначную грамматику на эквивалентную однозначную (и пригодную для LL/LR-парсинга), например:
$$S\to aSbS\mid \epsilon .$$ Эта грамматика однозначна и описывает тот же язык: любая непустая сбалансированная строка представляется как первая пара $a\dots b$ с вложенным внутри $S$ и затем следует (конкатенируется) ещё один $S$. Она подходит для рекурсивного спуска (LL(1)) и для LR(1)-парсеров. Для практической реализации:
- использовать рекурсивный спуск по правилу: если lookahead = $a$, потребовать $a$, вызвать S, ожидать $b$, затем рекурсивно вызвать S; если lookahead = $b$ или EOF — возвращать $\epsilon$;
- либо строить LR(1)-таблицу по этой грамматике (она не содержит конфликтов).
Вывод: грамматика порождает язык корректно сбалансованных $a,b$-строк (Dyck-1), сама неоднозначна, язык не регулярный но является детерминируемым КСЯ (DPDA, LR(1)). Для парсинга замените грамматику на, например, $S\to aSbS\mid \epsilon$.