LR(0)-разбор

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

Содержание

1 Построение автомата и управляющей таблицы
- 1.1 Автомат
- 1.2 Управляющая таблица
2 Пример
3 См. также
4 Источники информации

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

Как было сказано в статье про LR(k)-разборщик, управляющая программа одинакова для всех LR-анализаторов, а таблица и автомат изменяются от одного анализатора к другому. Надо заметить, что алгоритм LR-разбора похож на Алгоритм Эрли.

Автомат

Каждое состояние автомата будет состоять из 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]:

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

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

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

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

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

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

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

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

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

Обращение к таблице происходит следующим образом [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]s3[/math]		[math]s4[/math]
[math]1[/math]				[math]s5[/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]s3[/math]		[math]s4[/math]
[math]5[/math]		[math]7[/math]	[math]s3[/math]		[math]s4[/math]
[math]6[/math]				[math]s5[/math]		[math]s8[/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]