LR(0)-разбор

LR(0)-разбор означает, что разборщик для принятия решения не смотрит на символы строки, а смотрит только на состояние стека и определяет переходы по нему.

LR(0)-Разбор

Иллюстрация алгоритма

Заметим, что LR(0)-анализатор принимает решение о своих действиях только на основании содержимого магазина, не учитывая символы входной цепочки. Для иллюстрации построения таблиц LR(0)-анализатора мы будем использовать грамматику:

$E \to E + T \\ E \to T \\ T \to {\bf n} \\ T \to (E) \\ $

Для начала переходим к Пополненной грамматике:

$E_0 \to E \\ E \to E + T \\ E \to T \\ T \to {\bf n} \\ T \to (E) \\ $

Определение:

Пусть $\Gamma =\langle \Sigma, N, S, P \rangle$ — КС-грамматика и $A \to w_1 w_2 \in P$. Композицию $[A \to w_1 \cdot w_2, u]$, где $u \in \Sigma^{k}$, назовем LR(k)-ситуацией (англ. LR(k)-item)

LR(0)-ситуации не должны содержать терминальной цепочки, так как $k=0$, то есть мы можем записывать их следующим образом: $[A \to w_1 \cdot w_2]$

Построение автомата

В начале работы магазин пуст, и указатель входной цепочки находится перед ее первым символом. Этому состоянию соответствует ситуация $[E_0 \to \cdot E]$. Для терминалов или нетерминалой, мы строим переходы к другим ситуациям по следующей схеме:

${[} A \to \alpha \cdot c \beta] \xrightarrow{\text{c}} {[} A \to \alpha c \cdot \beta]$

${[} A \to \alpha \cdot B \beta] \xrightarrow{\text{B}} {[} A \to \alpha B \cdot \beta]$

${[} A \to \alpha \cdot B \beta] \xrightarrow{\varepsilon} {[} B \to \cdot \gamma]$

Получаем следующий НКА:

Избавимся от $\varepsilon$-переходов и получим ДКА:

Управляющая таблица

Теперь можно построить управляющую таблицу. Поступим следующим образом:

1. для каждого ребра $I \xrightarrow{\text{X}} J$ мы поместим в позицию $[I,X]$ таблицы

• $s\ J$ (сокр. от shift) , если $X$ — терминал,
• $J$, если $X$ — нетерминал.

2. для состояния, содержащего ситуацию $[A\to w \cdot]$, поместим $r(n)$ (сокр. от reduce) в позицию $[I, Y]$ для каждого терминала $Y$, где $n$ — это номер правила в изначальной грамматике.

3. пустая ячейка означает ошибочную ситуацию.

Вспомним грамматику и пронумеруем правила для 2 пункта:

$(0)\ E_0 \to E\\ (1)\ E \to E + T\\ (2)\ E \to T\\ (3)\ T \to {\bf n} \\ (4)\ T \to (E) \\ $

Управляющая таблица будет выглядеть так:

	$E$	$T$	$n$	$+$	$($	$)$	$\$$
$0$	$1$	$2$	$s3$		$s4$
$1$				$s5$			$r(0)$
$2$				$r(2)$		$r(2)$	$r(2)$
$3$				$r(3)$		$r(3)$	$r(3)$
$4$	$6$	$2$	$s3$		$s4$
$5$		$7$	$s3$		$s4$
$6$				$s5$		$s8$
$7$				$r(1)$		$r(1)$	$r(1)$
$8$				$r(4)$		$r(4)$	$r(4)$

Формальное описание

Базовые операции

Теперь опишем алгоритм формально.

Для построения множества состояний определим базовые операции $closure (I)$ и $goto (I, X)$, где $I$ – множество ситуаций, $X$ – символ грамматики (терминал или нетерминал). Операция $closure$ добавляет ситуации к множеству ситуаций, у которых точка стоит слева от нетерминала. Добавляются те ситуации, которые получаются из правил, в левой части которого находится этот нетерминал.

[] closure (I) do for каждой ситуации [A $\to$ w.Xv] из I for каждого правила грамматики X $\to$ u I += [X $\to$ .u] // Операция += добавляет элемент к множеству while I изменилось return I

Операция $goto$ "переносит" точку после символа $X$. Это означает переход из одного состояния в другое под воздействием символа $X$.

[] goto (I, X) J={} // {} обозначает пустое множество for каждой ситуации [A $\to$ w.Xv] из I J += [A $\to$wX.v] return closure (J)

Алгоритм построения конечного автомата

Теперь обсудим алгоритм построения анализатора. Обозначим $T$ множество состояний, $E$ – множество переходов.

E, T build() E = {} T = {closure ([S' $\to$ .S])} do for каждого состояния I из T for каждой ситуации [A $\to$ w.Xv] из I J = goto(I, X) T += {J} // ко множеству состояний добавляется новое состояние E += (I $\to$ J) // ко множеству ребер добавляется ребро, идущее из состояния I в состояние J. Этот переход осуществляется по символу X while E или T изменились return E, T

Поскольку для символа $\$$ операция $goto(I , \$)$ не определена , мы выполняем действие $accept$.

Пример LR(0)-разбора

Пример будет для строки $(n_1+n_2)+n_3$

Строка	Стек	$s = top()$	$a = w[ip]$	$action[s,a]$	Комментарий
$(n_1+n_2)+n_3\$$	$0$	$0$	$($	$shift\ 4$	Перенос $"("$
$n_1+n_2)+n_3\$$	$0\ (4$	$4$	$n_1$	$shift\ 3$	Перенос $"n_1"$
$+n_2)+n_3\$$	$0\ (4\ n_{1}3$	$3$	$+$	$reduce\ 3$	Свертка: $T \to \bf n$
$+n_2)+n_3\$$	$0\ (4\ T2$	$2$	$+$	$reduce\ 2$	Свертка: $E \to T$
$+n_2)+n_3\$$	$0\ (4\ E6$	$6$	$+$	$shift\ 5$	Перенос $"+"$
$n_2)+n_3\$$	$0\ (4\ E6\ +5$	$5$	$n_2$	$shift\ 3$	Перенос $"n_2"$
$)+n_3\$$	$0\ (4\ E6\ +5\ n_23$	$3$	$)$	$reduce\ 3$	Свертка: $T \to \bf n$
$)+n_3\$$	$0\ (4\ E6\ +5\ T7$	$7$	$)$	$reduce\ 1$	Свертка: $E \to E + T$
$)+n_3\$$	$0\ (4\ E6$	$6$	$)$	$shift\ 8$	Перенос $")"$
$+n_3\$$	$0\ (4\ E6\ )8$	$8$	$+$	$reduce\ 4$	Свертка: $T \to (E)$
$+n_3\$$	$0\ T2$	$2$	$+$	$reduce\ 2$	Свертка: $E \to T$
$+n_3\$$	$0\ E1$	$1$	$+$	$shift\ 5$	Перенос $"+"$
$n_3\$$	$0\ E1\ +5$	$5$	$n_3$	$shift\ 3$	Перенос $"n_3"$
$\$$	$0\ E1\ +5\ n_33$	$3$	$\$$	$reduce\ 3$	Свертка: $T \to \bf n$
$\$$	$0\ E1\ +5\ T7$	$7$	$\$$	$reduce\ 1$	Свертка: $E \to E + T$
$\$$	$0\ E1$	$1$	$\$$	$reduce\ 0$	Допуск

См. также

• Предиктивный синтаксический анализ

Источники информации

• Альфред Ахо, Рави Сети, Джеффри Ульман. Компиляторы. Принципы, технологии, инструменты. Издательство Вильямс, 2003. Стр. 301 - 326.
• Терехов Ан.А., Вояковская Н., Булычев Д., Москаль А. - Разработка компиляторов на платформе .NET - Восходящие анализаторы
• Б.К.Мартыненко. Языки и трансляции. Стр. 198 - 223