LR(0)-разбор — различия между версиями

Версия 12:27, 3 сентября 2015

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

Содержание

1 Построение автомата и управляющей таблицы
- 1.1 Автомат
  - 1.1.1 Базовые операции
  - 1.1.2 Построение автомата
- 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] добавляет ситуации к множеству ситуаций, у которых точка стоит слева от нетерминала. Добавляются те ситуации, которые получаются из правил, в левой части которого находится этот нетерминал.

Операция [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]

LR(0)-разбора конкретной строки

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

Строка	Стек	[math]curState[/math]	[math]curToken[/math]	[math]T[curState,curToken][/math]	Комментарий
[math](n_1+n_2)+n_3\$[/math]	[math]0[/math]	[math]0[/math]	[math]([/math]	[math]shift\ 4[/math]	Перенос [math]"("[/math]. Переход в [math]4[/math] состояние.
[math]n_1+n_2)+n_3\$[/math]	[math]0\ (4[/math]	[math]4[/math]	[math]n_1[/math]	[math]shift\ 3[/math]	Перенос [math]"n_1"[/math]. Переход в [math]3[/math] состояние.
[math]+n_2)+n_3\$[/math]	[math]0\ (4\ n_{1}3[/math]	[math]3[/math]	[math]+[/math]	[math]reduce\ 3[/math]	Свертка: [math]T \to \bf n[/math]. Удаление из стека [math]n_{1}3[/math]. Переход в [math]4[/math] состояние. Добавление в стек [math]T2[/math]. Переход в [math]2[/math] состояние.
[math]+n_2)+n_3\$[/math]	[math]0\ (4\ T2[/math]	[math]2[/math]	[math]+[/math]	[math]reduce\ 2[/math]	Свертка: [math]E \to T[/math]. Удаление из стека [math]T2[/math]. Переход в [math]4[/math] состояние. Добавление в стек [math]E6[/math]. Переход в [math]6[/math] состояние.
[math]+n_2)+n_3\$[/math]	[math]0\ (4\ E6[/math]	[math]6[/math]	[math]+[/math]	[math]shift\ 5[/math]	Перенос [math]"+"[/math]. Переход в [math]5[/math] состояние.
[math]n_2)+n_3\$[/math]	[math]0\ (4\ E6\ +5[/math]	[math]5[/math]	[math]n_2[/math]	[math]shift\ 3[/math]	Перенос [math]"n_2"[/math]. Переход в [math]3[/math] состояние.
[math])+n_3\$[/math]	[math]0\ (4\ E6\ +5\ n_23[/math]	[math]3[/math]	[math])[/math]	[math]reduce\ 3 [/math]	Свертка: [math]T \to \bf n[/math]. Удаление из стека [math]n_{2}3[/math]. Переход в [math]5[/math] состояние. Добавление в стек [math]T7[/math]. Переход в [math]7[/math] состояние.
[math])+n_3\$[/math]	[math]0\ (4\ E6\ +5\ T7[/math]	[math]7[/math]	[math])[/math]	[math]reduce\ 1 [/math]	Свертка: [math]E \to E + T[/math]. Удаление из стека [math]E6\ +5\ T7[/math]. Переход в [math]4[/math] состояние. Добавление в стек [math]E6[/math]. Переход в [math]6[/math] состояние.
[math])+n_3\$[/math]	[math]0\ (4\ E6[/math]	[math]6 [/math]	[math])[/math]	[math]shift\ 8[/math]	Перенос [math]")"[/math]. Переход в [math]8[/math] состояние.
[math]+n_3\$[/math]	[math]0\ (4\ E6\ )8[/math]	[math]8 [/math]	[math]+[/math]	[math]reduce\ 4[/math]	Свертка: [math]T \to (E)[/math]. Удаление из стека [math](4\ E6\ )8[/math]. Переход в [math]0[/math] состояние. Добавление в стек [math]T2[/math]. Переход в [math]2[/math] состояние.
[math]+n_3\$[/math]	[math]0\ T2[/math]	[math]2[/math]	[math]+[/math]	[math]reduce\ 2[/math]	Свертка: [math]E \to T[/math]. Удаление из стека [math]T2[/math]. Переход в [math]0[/math] состояние. Добавление в стек [math]E1[/math]. Переход в [math]1[/math] состояние.
[math]+n_3\$[/math]	[math]0\ E1[/math]	[math]1[/math]	[math]+[/math]	[math]shift\ 5[/math]	Перенос [math]"+"[/math]. Переход в [math]5[/math] состояние.
[math]n_3\$[/math]	[math]0\ E1\ +5[/math]	[math]5[/math]	[math]n_3[/math]	[math]shift\ 3[/math]	Перенос [math]"n_3"[/math]. Переход в [math]3[/math] состояние.
[math]\$[/math]	[math]0\ E1\ +5\ n_33[/math]	[math]3[/math]	[math]\$[/math]	[math]reduce\ 3[/math]	Свертка: [math]T \to \bf n[/math]. Удаление из стека [math]n_33[/math]. Переход в [math]5[/math] состояние. Добавление в стек [math]T7[/math]. Переход в [math]7[/math] состояние.
[math]\$[/math]	[math]0\ E1\ +5\ T7[/math]	[math]7[/math]	[math]\$[/math]	[math]reduce\ 1[/math]	Свертка: [math]E \to E + T[/math]. Удаление из стека [math]E1\ +5\ T7[/math]. Переход в [math]0[/math] состояние. Добавление в стек [math]E1[/math]. Переход в [math]1[/math] состояние.
[math]\$[/math]	[math]0\ E1[/math]	[math]1[/math]	[math]\$[/math]	[math]reduce\ 0[/math]	Так как свертка по нулевому правилу — осуществляем допуск.

См. также

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

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

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

@@ Строка 24: / Строка 24: @@
 Таким образом, мы определяем новые состояния, в которое автомат перейдет после переноса того или иного терминала или нетерминала.
-Заметим, что хранить в каждом состоянии только по одной ситуации не имеет смысла, поэтому пусть в каждое стостояние будет представлять множество ситуаций, а переходы {{---}} термилалы и нетермилалы. Для этого определим базовые операции <tex>closure (I)</tex> и <tex>goto (I, X)</tex>, где <tex>I</tex> – множество ситуаций, <tex>X</tex> – символ грамматики (терминал или нетерминал). Операция <tex>closure</tex> добавляет ситуации к множеству ситуаций, у которых точка стоит слева от нетерминала. Добавляются те ситуации, которые получаются из правил, в левой части которого находится этот нетерминал.
+==== Базовые операции ====
-{| border="0"
+Заметим, что хранить в каждом состоянии только по одной ситуации не имеет смысла, поэтому пусть в каждое стостояние будет представлять множество ситуаций, а переходы {{---}} термилалы и нетермилалы. Для этого определим базовые операции <tex>closure (I)</tex> и <tex>goto (I, X)</tex>, где <tex>I</tex> {{---}} множество ситуаций, <tex>X</tex> {{---}} символ грамматики (терминал или нетерминал).
-|align="left" colspan="4"|
-<font size=2>
-  [] '''closure''' (I)
-      '''do'''
-          '''for''' каждой ситуации [A <tex>\to</tex> w.Xv] из I
-              '''for'''  каждого правила грамматики X <tex>\to</tex> u
-                   I += [X <tex>\to</tex> .u] <font color=green> // Операция += добавляет элемент к множеству </font>
-      '''while''' I изменилось
-      '''return''' I
-</font>
-|}
-Операция <tex>goto</tex> "переносит" точку после символа <tex>X</tex>. Это означает переход из одного состояния в другое под воздействием символа <tex>X</tex>.
+* Операция <tex>closure</tex> добавляет ситуации к множеству ситуаций, у которых точка стоит слева от нетерминала. Добавляются те ситуации, которые получаются из правил, в левой части которого находится этот нетерминал.
-{| border="0"
+* Операция <tex>goto</tex> "переносит" точку после символа <tex>X</tex>. Это означает переход из одного состояния в другое под воздействием символа <tex>X</tex>.
-|align="left" colspan="4"|
-<font size=2>
-  [] '''goto''' (I, X)
-      J={}  <font color=green> // {} обозначает пустое множество </font>
-      '''for''' каждой ситуации [A <tex>\to</tex> w.Xv] из I
-          J += [A <tex> \to </tex>wX.v]
-      '''return''' closure (J)
-</font>
-|}
-Теперь обсудим алгоритм построения конечного автомата. Обозначим <tex>T</tex> множество состояний, <tex>E</tex> – множество переходов.
+==== Построение автомата ====
+Теперь обсудим алгоритм построения конечного автомата. Обозначим <tex>T</tex> множество состояний, <tex>E</tex> {{---}} множество переходов.
-{| border="0"
+# Изначальное состояние содержит одно правило: <tex>E_0 \to E</tex>,
-|align="left" colspan="4"|
+# Для текущего состояния делаем операцию <tex>closure</tex>,
-<font size=2>
+# По всем возможный символам для каждой ситуации добавляем переходы, используя операцию <tex>goto</tex>,
-  E, T '''build'''()
+# Если множество <tex>T</tex> или <tex>E</tex> во втором или третьем пункте изменилось, возвращаемся ко второму шагу.
-    E = {}
-    T = {closure ([S' <tex>\to</tex> .S])}
-    '''do'''
-        '''for''' каждого состояния I из T
-            '''for''' каждой ситуации [A <tex>\to</tex> w.Xv] из I
-                J = goto(I, X)
-                T += {J}     <font color=green>  // ко множеству состояний добавляется новое состояние </font>
-                E += (I <tex>\to</tex> J) <font color=green> // ко множеству ребер добавляется ребро, идущее из состояния I в состояние J. Этот переход осуществляется по символу X </font>
-    '''while''' E или T изменились
-    '''return''' E, T
-</font>
-|}
 === Управляющая таблица ===

LR(0)-разбор — различия между версиями

Версия 12:27, 3 сентября 2015

Содержание

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

Автомат

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

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

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

Пример

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

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

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

LR(0)-разбора конкретной строки

См. также

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

Навигация

Персональные инструменты

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

Варианты

Просмотры

Ещё

Поиск

Навигация

Инструменты