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