Вопрос #1577809
Дана контекстно‑свободная грамматика G, порождающая выражения с операциями + и *; приведите пример строки, для которой грамматика двусмысленна, докажите двусмысленность разбором двумя разными деревьями и предложите модифицированную неамбигуозную грамматику или парсер (LR/LL), корректно учитывающий приоритеты и ассоциативность
\[
G:\; E \to E + E \mid E * E \mid (E) \mid id
\]
Пример неоднозначной строки:
\[
id + id * id
\]
Две разные разбора (деревца/выводы).
1) Разбор, соответствующий семантике «+ ниже по приоритету, * — выше» (правильный):
\[
E \Rightarrow E + E \Rightarrow id + E \Rightarrow id + E * E \Rightarrow id + id * id
\]
Дерево (в скобочной форме):
\[
E[\,E + E[\,E * E[\,id,\,id\]\,]\,] \quad\text{то есть}\quad id + (id * id)
\]
2) Альтернативный разбор (другая группировка):
\[
E \Rightarrow E * E \Rightarrow E + E * E \Rightarrow id + id * id
\]
Дерево:
\[
E[\,E * E[\,E + E[\,id,\,id\],\,id\,]\,] \quad\text{то есть}\quad (id + id) * id
\]
Поскольку один и тот же выводимый терминал дает два различных деревa/группировки, грамматика двусмысленна.
Неамбигуозная грамматика, задающая приоритеты и левую ассоциативность:
(вариант с явным уровнем выражений)
\[
\begin{aligned}
E &\to E + T \mid T\\
T &\to T * F \mid F\\
F &\to (E) \mid id
\end{aligned}
\]
Эта грамматика однозначно задаёт приоритет \(*\) выше \(+\) и левую ассоциативность (левая рекурсия).
Если нужен LL(1)-совместимый (без левой рекурсии) вариант:
\[
\begin{aligned}
E &\to T\;E'\\
E' &\to +\;T\;E' \mid \varepsilon\\
T &\to F\;T'\\
T' &\to *\;F\;T' \mid \varepsilon\\
F &\to (E) \mid id
\end{aligned}
\]
Этот вариант парсится LL(1). Аналогично исходная левая-рекурсивная форма подходит для LR-парсеров (LR(0)/S LR(1)/LALR(1)/LR(1)) и будет однозначной.