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