Вопрос #1580048
Дана контекстно-свободная грамматика G: S -> SS | 'a' S 'b' | ε. Поясните, является ли эта грамматика неоднозначной, приведите конкретную строку с двумя различными левыми выводами, и опишите метод (или покажите преобразование), который может помочь разрешить неоднозначность для задач парсинга
Грамматика:
\( S \to SS \mid a\,S\,b \mid \varepsilon \).
Строка \(ab\) имеет два различных левых вывода:
1) Первый левый вывод:
\[
S \Rightarrow a\,S\,b \Rightarrow a\,\varepsilon\,b \Rightarrow ab.
\]
2) Второй левый вывод:
\[
S \Rightarrow SS \Rightarrow a\,S\,b\,S \Rightarrow a\,\varepsilon\,b\,S \Rightarrow ab\,S \Rightarrow ab\,\varepsilon \Rightarrow ab.
\]
Отсюда грамматика неоднозначна.
Способ разрешить неоднозначность (стандартное преобразование для языка правильно вложенных пар): заменить правило разбиения на конкатенацию на правило, которое однозначно выделяет первую пару и затем продолжение. Например неявно эквивалентная, но однозначная грамматика
\[
S \to a\,S\,b\,S \mid \varepsilon
\]
каждую непустую строку расписывает как «первая открыт. пара \(a\) — соответствующая ей \(b\) и затем остаток», что даёт уникальное разложение и убирает описанную неоднозначность. Для задач парсинга это даёт каноническую структуру (подходит для детерминированного разбора, например LL-подходов). Альтернатива для практики парсинга — использовать GLR/Chart-парсер, которые специально обрабатывают неоднозначные грамматики, но проще и эффективнее — переписать грамматику в однозначную форму, как показано.