Использование приоритета и ассоциативности для разрешения неоднозначности при LR-анализе

Приоритет и ассоциативность

Рассмотрим грамматику выражений \[E \to E + E | E * E | (E) | val.\]

Она является неоднозначной.

Она очевидно является неоднозначной, поскольку не определяет ни ассоциативность, ни приоритет операторов $+$ и $*$. Ранее мы рассматривали однозначную грамматику, порождающую тот же язык, которая включала приоритет и ассоциативность операторов непосредственно в определение. С другой стороны, определение той грамматики достаточно объёмное по сравнению с неоднозначным. Возникает вопрос: нельзя ли разрешить конфликты, возникающие в силу неоднозначности грамматики, используя информацию о приоритете и ассоциативности операторов? Попробуем построить SLR-анализатор для этой неоднозначной грамматики.

Введём правило расширенной грамматики \[S\to E\]

и построим LR(0)-автомат.

Начальное состояние: \[\begin{array}{rll} I_0 = \{S \to .E\}^+ = \{ & S \to .E \\ & E \to .E + E \\ & E \to .E * E \\ & E \to .(E) \\ & E \to .val \\ \} \end{array}\]

Функция переходов

\[\begin{align} \mathrm{GOTO}(I_{0}, E) = & I_{1} \\ = & \{\\ & \begin{array}{l} S \to E . \\ E \to E . + E \\ E \to E . * E \\ \hline \end{array}\\ & \} \\ \end{align}\]

\[\begin{align} \mathrm{GOTO}(I_{0}, () = & I_{2} \\ = & \{\\ & \begin{array}{l} E \to (.E) \\ \hline E \to .E + E \\ E \to .E * E \\ E \to .(E) \\ E \to .val \\ \end{array}\\ & \} \\ \end{align}\]

\[\begin{align} \mathrm{GOTO}(I_{0}, val) = & I_{3} \\ = & \{\\ & \begin{array}{l} E \to val. \\ \hline \end{array}\\ & \} \\ \hline \end{align}\]

\[\begin{align} \mathrm{GOTO}(I_{1}, +) = & I_{4} \\ = & \{\\ & \begin{array}{l} E \to E + . E \\ \hline E \to .E + E \\ E \to .E * E \\ E \to .(E) \\ E \to .val \\ \end{array}\\ & \} \\ \end{align}\]

\[\begin{align} \mathrm{GOTO}(I_{1}, *) = & I_{5} \\ = & \{\\ & \begin{array}{l} E \to E * . E \\ \hline E \to .E + E \\ E \to .E * E \\ E \to .(E) \\ E \to .val \\ \end{array}\\ & \} \\ \hline \end{align}\]

\[\begin{align} \mathrm{GOTO}(I_{2}, E) = & I_{6} \\ = & \{\\ & \begin{array}{l} E \to (E.) \\ E \to E .+ E \\ E \to E .* E \\ \hline \end{array}\\ & \} \\ \mathrm{GOTO}(I_{2}, () = & I_{2} \\ \mathrm{GOTO}(I_{2}, val) = & I_{3} \\ \hline \end{align}\]

\[\begin{align} \mathrm{GOTO}(I_{4}, E) = & I_{7} \\ = & \{\\ & \begin{array}{l} E \to E + E . \\ E \to E . + E \\ E \to E . * E \\ \hline \end{array}\\ & \} \\ \mathrm{GOTO}(I_{4}, () = & I_{2} \\ \mathrm{GOTO}(I_{4}, val) = & I_{3} \\ \hline \end{align}\]

\[\begin{align} \mathrm{GOTO}(I_{5}, E) = & I_{8} \\ = & \{\\ & \begin{array}{l} E \to E * E . \\ E \to E . + E \\ E \to E . * E \\ \hline \end{array}\\ & \} \\ \mathrm{GOTO}(I_{5}, () = & I_{2} \\ \mathrm{GOTO}(I_{5}, val) = & I_{3} \\ \hline \mathrm{GOTO}(I_{6}, +) = & I_{4} \\ \mathrm{GOTO}(I_{6}, *) = & I_{5} \\ \end{align}\]

\[\begin{align} \mathrm{GOTO}(I_{6}, )) = & I_{9} \\ = & \{\\ & \begin{array}{l} E \to (E). \\ \hline \end{array}\\ & \} \\ \hline \mathrm{GOTO}(I_{7}, +) = & I_{4} \\ \mathrm{GOTO}(I_{7}, *) = & I_{5} \\ \hline \mathrm{GOTO}(I_{8}, +) = & I_{4} \\ \mathrm{GOTO}(I_{8}, *) = & I_{5} \\ \end{align}\]

Диаграмма переходов

`FOLLOW`

\[\begin{align} \mathrm{FOLLOW}(S) & = \{$\} \\ \mathrm{FOLLOW}(E) & = \{*, +, ), $\} \\ \end{align}\]

`ACTION`

Пронумеруем продукции следующим образом: \[\begin{align} E & \to E + E & (1)\\ E & \to E * E & (2)\\ E & \to (E) & (3)\\ E & \to val & (4)\\ \end{align}\]

Построим таблицу ACTION:

ACTION	0	1	2	3	4	5	6	7	8	9
val	s3		s3		s3	s3
+		s4		r4			s4	s4/r1	s4/r2	r3
*		s5		r4			s5	s5/r1	s5/r2	r3
(	s2		s2		s2	s2
)				r4			s9	r1	r2	r3
$		acc		r4				r1	r2	r3

Мы видим, что ожидаемо возникают конфликты перенос/свёртка для символов $+$ и $*$.

В состояние 7 анализатор попадает, разобрав строку $E+E$. Конфликт для символа $+$ связан с отсутствием в грамматике информации об ассоциативности оператора $+$. Если оператор левоассоциативен, то приоритетной должна быть свёртка (поскольку выражение $E+E+E$ должно быть интерпретировано как $(E+E)+E$, и мы должны свернуть первый прочитанный $E+E$ как если бы он был в скобках). Если правоассоциативен – то перенос (соображения аналогичные).

Конфликт в состоянии 7 для символа $*$ связан с отсутствием информации об относительном приоритете операторов $+$ и $*$. Если $+$ имеет меньший приоритет, то выбор должен быть сделан в пользу переноса (действительно, выражение $E+E*E$ должно быть разобрано как $E+(E*E)$, и тогда, прочитав в нём $E+E$ мы должны прочитать $*$, чтобы можно было произвести свёртку $E*E$). Если $*$ имеет меньший приоритет, то выбор – в пользу свёртки. Если приоритет одинаковый, то выбор определяется ассоциативностью.

Аналогично можно рассуждать о конфликтах в состоянии 8, в которое анализатор приходит, прочитав строку $E*E$.

Таблица GOTO (только значащие строки):

GOTO	E
0	1
2	6
4	7
5	8

Ассоциативность и приоритет продукций

Показательным будет пример для грамматики с унарным оператором $-$: \[\begin{align} E & \to E - E | - E | val \end{align}\]

Начальное состояние \[\begin{align} I_0 = \{S\to .E\}^+ = \{ & S\to E\\ & E\to .E - E\\ & E\to . - E\\ & E\to . val\\ \} \end{align}\]

Оператор $-$ имеет разный приоритет (и ассоциативность) в разных продукциях.

Функция `GOTO`:

\[\begin{align} \mathrm{GOTO}(I_{0}, E) = & I_{1} \\ = & \{\\ & \begin{array}{l} S \to E . \\ E\to E. - E\\ \hline \end{array}\\ & \} \\ \end{align}\]

\[\begin{align} \mathrm{GOTO}(I_{0}, -) = & I_{2} \\ = & \{\\ & \begin{array}{l} E\to - . E\\ \hline E\to .E - E\\ E\to . - E\\ E\to . val\\ \end{array}\\ & \} \\ \end{align}\]

\[\begin{align} \mathrm{GOTO}(I_{0}, val) = & I_{3} \\ = & \{\\ & \begin{array}{l} E\to val .\\ \hline \end{array}\\ & \} \\ \hline \end{align}\]

\[\begin{align} \mathrm{GOTO}(I_{1}, -) = & I_{4} \\ = & \{\\ & \begin{array}{l} E\to E - .E\\ \hline E\to .E - E\\ E\to . - E\\ E\to . val\\ \end{array}\\ & \} \\ \hline \end{align}\]

\[\begin{align} \mathrm{GOTO}(I_{2}, E) = & I_{5} \\ = & \{\\ & \begin{array}{l} E\to - E .\\ E\to E . - E\\ \hline \end{array}\\ & \} \\ \mathrm{GOTO}(I_{2}, -) = & I_{2} \\ \mathrm{GOTO}(I_{2}, val) = & I_{3} \\ \hline \end{align}\]

\[\begin{align} \mathrm{GOTO}(I_{4}, E) = & I_{6} \\ = & \{\\ & \begin{array}{l} E\to E - E .\\ E\to E . - E\\ \hline \end{array}\\ & \} \\ \mathrm{GOTO}(I_{4}, -) = & I_{2} \\ \mathrm{GOTO}(I_{4}, val) = & I_{3} \\ \hline \mathrm{GOTO}(I_{5}, -) = & I_{4} \\ \hline \mathrm{GOTO}(I_{6}, -) = & I_{4} \\ \end{align}\]

Таблица `ACTION`

\[\begin{align} E & \to E - E & (1) \\ E & \to - E & (2) \\ E & \to val & (3) \\ \end{align}\]

\[\mathrm{FOLLOW}(E) = \{-, \$\}\]

ACTION	-	val	$	GOTO	E
0	s2	s3		0	1
1	s4		acc	1
2	s2	s3		2	5
3	r3		r3	3
4	s2	s3		4	6
5	s4/r2		r2	5
6	s4/r1		r1	6

Пример разбора

Разбор строки val--val-val:

Стек	Символы	Строка	Действие
0		`val--val-val`	s3
0 3	`val`	`--val-val`	r3
0 1	`E`	`--val-val`	s4
0 1 4	`E-`	`-val-val`	s2
0 1 4 2	`E--`	`val-val`	s3
0 1 4 2 3	`E--val`	`-val`	r3

Стек	Символы	Строка	Действие
0 1 4 2 5	`E--E`	`-val`	r2
0 1 4 6	`E-E`	`-val`	r1
0 1	`E`	`-val`	s4
0 1 4	`E-`	`val`	s3
0 1 4 3	`E-val`	`$`	r3
0 1 4 6	`E-E`	`$`	r1
0 1	`E`	`$`	acc