Дан контекстно-свободный грамматический фрагмент: S -> S '+' S | 'a' | '(' S ')'. Покажите, что грамматика неоднозначна, приведите два разных дерева вывода для одной строки, предложите способ модифицировать грамматику для устранения неоднозначности и привести регуляризацию для LL(1)/LR(1) парсера
Дан контекстно-свободный грамматический фрагмент: S -> S '+' S | 'a' | '(' S ')'. Покажите, что грамматика неоднозначна, приведите два разных дерева вывода для одной строки, предложите способ модифицировать грамматику для устранения неоднозначности и привести регуляризацию для LL(1)/LR(1) парсера
Не можешь разобраться в этой теме?
Обратись за помощью к экспертам
Гарантированные бесплатные доработки в течение 1 года
Быстрое выполнение от 2 часов
Проверка работы на плагиат
Поможем написать учебную работу
S→S ′+′ S∣′a′∣′(′ S ′)′ S \to S\ '+'\ S \mid 'a' \mid '('\,S\,')'
S→S ′+′ S∣′a′∣′(′S′)′ неоднозначна.
Пример строки: a+a+a\text{a+a+a}a+a+a. Два различных дерева вывода (в скобочной нотации):
- Левое сопряжение (left-assoc):
(S (S (S ’a’) ′+′ (S ’a’)) ′+′ (S ’a’)) (S\ (S\ (S\ \text{'a'})\ '+'\ (S\ \text{'a'}))\ '+'\ (S\ \text{'a'}))
(S (S (S ’a’) ′+′ (S ’a’)) ′+′ (S ’a’)) (т.е. ((a+a)+a)((a+a)+a)((a+a)+a))
- Правое сопряжение (right-assoc):
(S (S ’a’) ′+′ (S (S ’a’) ′+′ (S ’a’))) (S\ (S\ \text{'a'})\ '+'\ (S\ (S\ \text{'a'})\ '+'\ (S\ \text{'a'})))
(S (S ’a’) ′+′ (S (S ’a’) ′+′ (S ’a’))) (т.е. a+(a+a)a+(a+a)a+(a+a))
Оба дерева соответствуют одной и той же строке — значит грамматика неоднозначна.
Способ устранения неоднозначности: зафиксировать ассоциативность оператора '+'. Например, сделать оператор левосторонне-ассоциативным.
1) Вариант, пригодный для LR(1) (лево-рекурсивный, однозначный):
S→S ′+′ M∣M,M→′a′∣′(′ S ′)′ S \to S\ '+'\ M \mid M,\qquad M \to 'a' \mid '('\,S\,')'
S→S ′+′ M∣M,M→′a′∣′(′S′)′ (здесь выражения парсятся как последовательные левые свёртки, т.е. ((a+a)+a)((a+a)+a)((a+a)+a).)
2) Вариант, пригодный для LL(1) (устранена левая рекурсия):
S→M S′,S′→′+′ M S′∣ε,M→′a′∣′(′ S ′)′ S \to M\ S',\qquad S' \to '+'\ M\ S' \mid \varepsilon,\qquad M \to 'a' \mid '('\,S\,')'
S→M S′,S′→′+′ M S′∣ε,M→′a′∣′(′S′)′ (термин ε\varepsilonε — пустая цепочка). Этот вариант однозначен и LL(1): \(\mathrm{FIRST}(M)=\{\text{'a'},'('\}\), \(\mathrm{FIRST}(S')=\{'+',\varepsilon\}\), пересечений, вызывающих конфликт, нет.
Таким образом: выбрать желаемую ассоциативность (здесь — левую) и заменить правило \(S\to S+' '+S\) на приведённые однозначные формы для LR(1) или LL(1).