Вопрос #1577128
Дана контекстно‑свободная грамматика S → S + S | S * S | (S) | a — покажите, что эта грамматика является неоднозначной, приведите примеры неоднозначных деревьев вывода, затем постройте не неоднозначную грамматику или определите правила приоритета/ассоциативности, которые позволяют однозначно парсить выражения
\[
S \to S + S \mid S * S \mid (S) \mid a
\]
неоднозначна. Пример строки с двумя различными деревьями: \(a+a+a\).
Две различные левые вывода/дерева (один соответствует \((a+a)+a\), другой — \(a+(a+a)\)):
1) Первый вывод (лево‑ассоциативная ветвь):
\[
S \Rightarrow S + S \Rightarrow S + S + S \Rightarrow a + S + S \Rightarrow a + a + S \Rightarrow a + a + a
\]
(соответствует разбиению \((a+a)+a\)).
2) Второй вывод (право‑ассоциативная ветвь):
\[
S \Rightarrow S + S \Rightarrow a + S \Rightarrow a + S + S \Rightarrow a + a + S \Rightarrow a + a + a
\]
(соответствует разбиению \(a+(a+a)\)).
Аналогично неоднозначность видна для строки \(a+a*a\): возможны деревья \((a+a)*a\) и \(a+(a*a)\).
Чтобы устранить неоднозначность, вводят уровни (приоритеты) и ассоциативность. Стандартная не неоднозначная грамматика с приоритетом \(*\) выше \(+\) и левой ассоциативностью:
\[
\begin{aligned}
E &\to E + T \mid T\\
T &\to T * F \mid F\\
F &\to (E) \mid a
\end{aligned}
\]
Здесь \(E\) — выражения с \(+\), \(T\) — термы с \(*\), \(F\) — множители. В этой грамматике:
- операция \(*\) имеет более высокий приоритет (потому что производится на уровне \(T\)),
- обе операции левоассоциативны (благодаря левой рекурсии).
Пример однозначного разбора:
\[
a+a*a \quad\text{разбирается как}\quad E\Rightarrow E+T\Rightarrow T+T\Rightarrow F+T\Rightarrow a+(T*F)\Rightarrow a+(a*a)
\]
то есть однозначно \(a+(a*a)\).
Краткое обоснование однозначности: синтаксическая структура разделена по уровням (E, T, F), и каждое нетерминальное правило определяет единственный способ разбиения по оператору соответствующего приоритета; поэтому для фиксированной строки порядок узлов определяется однозначно.