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