LR(0)-разбор


НЕТ ВОЙНЕ
24 февраля 2022 года российское руководство во главе с Владимиром Путиным развязало агрессивную войну против Украины. В глазах всего мира это военное преступление совершено от лица всей страны, всех россиян. Будучи гражданами Российской Федерации, мы против своей воли оказались ответственными за нарушение международного права, военное вторжение и массовую гибель людей. Чудовищность совершенного преступления не оставляет возможности промолчать или ограничиться пассивным несогласием. Мы убеждены в абсолютной ценности человеческой жизни, в незыблемости прав и свобод личности. Режим Путина — угроза этим ценностям. Наша задача — обьединить все силы для сопротивления ей. Эту войну начали не россияне, а обезумевший диктатор. И наш гражданский долг — сделать всё, чтобы её остановить. Антивоенный комитет России
Распространяйте правду о текущих событиях, оберегайте от пропаганды своих друзей и близких. Изменение общественного восприятия войны - ключ к её завершению.
meduza.io, Популярная политика, Новая газета, zona.media, Майкл Наки.

LR(0)-разборщик — это частный случай LR(k)-разборщикa. Заметим, что в данном случае [math]k=0[/math], то есть решение о своих действиях принимается только на основании содержимого стека, символы входной цепочки не учитываются.

Построение автомата и управляющей таблицы

Автомат

Каждое состояние автомата будет состоять из LR(0)-ситуации.

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

Пусть — КС-грамматика и . Композицию назовем LR(0)-ситуацией (англ. LR(0)-item).

В начале работы стек пуст, и указатель входной цепочки находится перед ее первым символом. Этому состоянию соответствует ситуация [math][E_0 \to \cdot E][/math], где [math]E_0[/math] — нетерминал, добавленный при пополнении грамматики, [math]E[/math] — стартовый нетерминал. Назовем это состояние [math]0[/math]. Входная цепочка может начинаться с любого терминального символа, с которого начинается правая часть любого правила с левой частью [math]E[/math]. Построим соответствующий переход по следующей схеме:

Теперь мы должны выяснить, что произойдет, если анализатор выполнит перенос. Предположим, что мы выполним перенос [math]c[/math] или перенос [math]B[/math]:

Таким образом, мы определяем новые состояния, в которые автомат перейдет после переноса того или иного терминала или нетерминала.

Можно заметить, что алгоритм LR-разбора похож на алгоритм Эрли.

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

Заметим, что хранить в каждом состоянии только по одной ситуации не имеет смысла, поэтому пусть каждое состояние будет представлять множество ситуаций, а переходы — терминалы и нетерминалы. Для этого определим базовые операции [math]closure (I)[/math] и [math]goto (I, X)[/math], где [math]I[/math] — множество ситуаций, [math]X[/math] — символ грамматики (терминал или нетерминал).

Операция [math]closure[/math] добавляет ситуации к множеству ситуаций, у которых точка стоит слева от нетерминала. Добавляются те ситуации, которые получаются из правил, в левой части которых находится этот нетерминал.

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

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

Теперь обсудим алгоритм построения конечного автомата. Обозначим [math]T[/math] множество состояний, [math]E[/math] — множество переходов.

Изначальное состояние содержит одно правило: [math]E_0 \to E[/math].
Для текущего состояния делаем операцию [math]closure[/math].
По всем возможный символам для каждой ситуации добавляем переходы, используя операцию [math]goto[/math].
Если множество [math]T[/math] или [math]E[/math] во втором или третьем пункте изменилось, возвращаемся ко второму шагу.

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

После построения автомата можно перейти к построению управляющей таблицы.

Обращение к таблице происходит следующим образом [math]\mathtt{T[state, token]}[/math], где

[math]\mathtt{state}[/math] — состояние автомата,
[math]\mathtt{token}[/math] — входной символ;

В соответствии со структурой управляющей таблицы будем действовать следующим образом:

Для каждого ребра [math]I \xrightarrow{\text{X}} J [/math] (из состояния [math]I[/math] в состояние [math]J[/math] по [math]X[/math]) мы поместим в позицию [math]T[I,X][/math]
- [math]s(J)[/math] (сокр. от shift) , если [math]X[/math] — терминал,
- [math]J[/math], если [math]X[/math] — нетерминал.
Для состояния [math]I[/math], содержащего ситуацию [math][A\to w \cdot][/math] в позицию [math]T[I, Y][/math] для каждого терминала [math]Y[/math]
- Поместим [math]r(n)[/math] (сокр. от reduce), где [math]n[/math] — это номер правила в изначальной грамматике.
Запись [math]r(0)[/math] означает допуск.
Пустая ячейка означает ошибочную ситуацию.

Пример

Для иллюстрации алгоритма LR(0)-разборщика мы будем использовать грамматику:

Обратим внимание, что данная грамматика является леворекурсивной, поэтому нисходящий разборщик не сможет осуществить разбор слова из этой грамматики.

Пополнение грамматики

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

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

[math]0[/math] состоянию будет соответствует ситуация [math][E_0 \to \cdot E][/math]. Добавляем остальные состояния и получаем следующий НКА:

На картинке в двойной рамке обозначены терминальные состояния — это такие состояния, из которых можно производить свертку по правилу грамматики, а из остальных возможен только перенос. Этот термин не используется в алгоритме, а нужен только для лучшего визуального восприятия.

Теперь в одно состояние перемещаем все ситуации, в которые идут [math]\varepsilon[/math]-переходы. Получаем ДКА:

Заполнение управляющей таблицы

Пронумеруем правила для выполнения свертки:

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

	[math]E[/math]	[math]T[/math]	[math]n[/math]	[math]+[/math]	[math]([/math]	[math])[/math]	[math]\$[/math]
[math]0[/math]	[math]1[/math]	[math]2[/math]	[math]s(3)[/math]		[math]s(4)[/math]
[math]1[/math]				[math]s(5)[/math]			[math]r(0)[/math]
[math]2[/math]				[math]r(2)[/math]		[math]r(2)[/math]	[math]r(2)[/math]
[math]3[/math]				[math]r(3)[/math]		[math]r(3)[/math]	[math]r(3)[/math]
[math]4[/math]	[math]6[/math]	[math]2[/math]	[math]s(3)[/math]		[math]s(4)[/math]
[math]5[/math]		[math]7[/math]	[math]s(3)[/math]		[math]s(4)[/math]
[math]6[/math]				[math]s(5)[/math]		[math]s(8)[/math]
[math]7[/math]				[math]r(1)[/math]		[math]r(1)[/math]	[math]r(1)[/math]
[math]8[/math]				[math]r(4)[/math]		[math]r(4)[/math]	[math]r(4)[/math]