Рассмотрите следующую контекстно‑свободную грамматику, порождающую выражения: E -> E + E | E * E | ( E ) | id. Поясните, почему грамматика неоднозначна, приведите конкретный пример строки с двумя дериватами и предложите модифицированную грамматику, устраняющую неоднозначность с учётом приоритета умножения над сложением

20 Окт в 10:33
6 +6
0
Ответы
1

Исходная грамматика:
(E \to E + E \mid E * E \mid (E) \mid id).

Почему неоднозначна — потому что одна и та же строка может порождаться разными деревьями (разными отношениями приоритета/ассоциативности между операторами). Конкретный пример строки и две разные деривации:

Возьмём строку (id + id * id).

Деривация 1 (сложение в вершине дерева):
[
\begin{aligned}
& E \Rightarrow E + E \
& \Rightarrow id + E \
& \Rightarrow id + E E \
& \Rightarrow id + id E \
& \Rightarrow id + id * id
\end{aligned}
]

Деривация 2 (умножение в вершине дерева):
[
\begin{aligned}
& E \Rightarrow E E \
& \Rightarrow E + E E \
& \Rightarrow id + E E \
& \Rightarrow id + id E \
& \Rightarrow id + id * id
\end{aligned}
]

Обе дают одну и ту же конечную строку, но соответствуют разным синтаксическим деревьям (с разным приоритетом операторов) — значит грамматика неоднозначна.

Модифицированная (неоднозначность устраняющая, с приоритетом умножения над сложением, обычно с лево‑ассоциативностью):
[
\begin{aligned}
E &\to E + T \mid T \
T &\to T F \mid F \
F &\to (E) \mid id
\end{aligned}
]
Здесь (T) (термы) дает более высокий приоритет оператору (), а (E) объединяет термы через (+); эта грамматика устраняет рассматриваемую неоднозначность и задаёт левую ассоциативность.

20 Окт в 10:57
Не можешь разобраться в этой теме?
Обратись за помощью к экспертам
Гарантированные бесплатные доработки в течение 1 года
Быстрое выполнение от 2 часов
Проверка работы на плагиат
Поможем написать учебную работу
Прямой эфир