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

Версия 15:56, 29 августа 2015

LR(0)-разборщик это частный случай LR(k)-разборщикa, для которого сейчас будет рассмотрено построение автомата и управляющей таблицы.

Содержание

1 Алгоритм
2 Иллюстрация алгоритма
3 Формальное описание
- 3.1 Базовые операции
- 3.2 Алгоритм построения конечного автомата
4 Пример LR(0)-разбора
5 См. также
6 Источники информации

Алгоритм

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

Ситауции

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

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

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

Автомат для множества ситуаций

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

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

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

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

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

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

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

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

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

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

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

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

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

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

1. для каждого ребра мы поместим в позицию [math][I,X][/math] таблицы

[math]s\ J[/math] (сокр. от shift) , если [math]X[/math] — терминал,
[math]J[/math], если [math]X[/math] — нетерминал.

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

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

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

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

	[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]

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

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

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

Для построения множества состояний определим базовые операции [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]\$[/math] операция [math]goto(I , \$)[/math] не определена , мы выполняем действие [math]accept[/math].

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

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

Строка	Стек	[math]s = top()[/math]	[math]a = w[ip][/math]	[math]action[s,a][/math]	Комментарий
[math](n_1+n_2)+n_3\$[/math]	[math]0[/math]	[math]0[/math]	[math]([/math]	[math]shift\ 4[/math]	Перенос [math]"("[/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]+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_2)+n_3\$[/math]	[math]0\ (4\ T2[/math]	[math]2[/math]	[math]+[/math]	[math]reduce\ 2[/math]	Свертка: [math]E \to T[/math]
[math]+n_2)+n_3\$[/math]	[math]0\ (4\ E6[/math]	[math]6[/math]	[math]+[/math]	[math]shift\ 5[/math]	Перенос [math]"+"[/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])+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_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])+n_3\$[/math]	[math]0\ (4\ E6[/math]	[math]6 [/math]	[math])[/math]	[math]shift\ 8[/math]	Перенос [math]")"[/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]+n_3\$[/math]	[math]0\ T2[/math]	[math]2[/math]	[math]+[/math]	[math]reduce\ 2[/math]	Свертка: [math]E \to T[/math]
[math]+n_3\$[/math]	[math]0\ E1[/math]	[math]1[/math]	[math]+[/math]	[math]shift\ 5[/math]	Перенос [math]"+"[/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]\$[/math]	[math]0\ E1\ +5\ n_33[/math]	[math]3[/math]	[math]\$[/math]	[math]reduce\ 3[/math]	Свертка: [math]T \to \bf n[/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]\$[/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)-анализ

@@ Строка 1: / Строка 1: @@
-LR(0)-разбор означает, что разборщик для принятия решения не смотрит на символы строки, а смотрит только на состояние стека и определяет переходы по нему.
+LR(0)-разборщик это частный случай [[LR(k)-грамматики#LR-разборщик|LR(k)-разборщикa]], для которого сейчас будет рассмотрено построение автомата и управляющей таблицы.
-== LR(0)-Разбор ==
+== Алгоритм ==
+Заметим, что LR(0)-разборщик принимает решение о своих действиях только на основании содержимого стека, не учитывая символы входной цепочки.
-=== Иллюстрация алгоритма ===
+=== Ситауции ===
-Заметим, что LR(0)-анализатор принимает решение о своих действиях только на основании содержимого магазина, не учитывая символы входной цепочки. Для иллюстрации построения таблиц LR(0)-анализатора мы будем использовать грамматику:
+{{Определение
+|id=def_LRk_item)
+|definition=
+Пусть <tex>\Gamma =\langle \Sigma, N, S, P \rangle</tex> {{---}} КС-грамматика и <tex>A \to w_1 w_2 \in P</tex>. Композицию <tex>[A \to w_1 \cdot w_2, u] </tex>, где <tex>u \in \Sigma^{k}</tex>, назовем '''LR(k)-ситуацией''' (англ. ''LR(k)-item'')
+}}
+LR(0)-ситуации не должны содержать терминальной цепочки, так как <tex>k=0</tex>, то есть мы можем записывать их следующим образом: <tex>[A \to w_1 \cdot w_2]</tex>
+=== Автомат для множества ситуаций ===
+В начале работы стек пуст, и указатель входной цепочки находится перед ее первым символом. Этому состоянию соответствует ситуация <tex>[E_0 \to \cdot E]</tex>.
+Для терминалов или нетерминалов, мы строим переходы к другим ситуациям по следующей схеме:
+<tex>{[} A \to \alpha \cdot c \beta] \xrightarrow{\text{c}}  {[} A \to \alpha  c \cdot \beta] </tex>
+<tex>{[} A \to \alpha \cdot B \beta] \xrightarrow{\text{B}}  {[} A \to \alpha  B \cdot \beta] </tex>
+<tex>{[} A \to \alpha \cdot B \beta] \xrightarrow{\varepsilon}  {[} B \to \cdot \gamma] </tex>
+Получаем следующий [[Недетерминированные конечные автоматы|НКА]]:
+Избавимся от <tex>\varepsilon</tex>-переходов и получим [[Детерминированные конечные автоматы|ДКА]]:
+=== Построение управляющей таблицы ===
+== Иллюстрация алгоритма ==
+Для иллюстрации алгоритма LR(0)-разборщика мы будем использовать грамматику:
 <tex>
@@ Строка 12: / Строка 38: @@
 T \to (E) \\
 </tex>
+=== Пополнение грамматики===
 Для начала переходим к ''Пополненной грамматике'':
@@ Строка 22: / Строка 49: @@
 T \to (E) \\
 </tex>
-{{Определение
-|id=def_LRk_item)
-|definition=
-Пусть <tex>\Gamma =\langle \Sigma, N, S, P \rangle</tex> {{---}} КС-грамматика и <tex>A \to w_1 w_2 \in P</tex>. Композицию <tex>[A \to w_1 \cdot w_2, u] </tex>, где <tex>u \in \Sigma^{k}</tex>, назовем '''LR(k)-ситуацией''' (англ. ''LR(k)-item'')
-}}
-LR(0)-ситуации не должны содержать терминальной цепочки, так как <tex>k=0</tex>, то есть мы можем записывать их следующим образом: <tex>[A \to w_1 \cdot w_2]</tex>
-==== Построение автомата ====
+=== Построение автомата ===
-В начале работы магазин пуст, и указатель входной цепочки находится перед ее первым символом. Этому состоянию соответствует ситуация <tex>[E_0 \to \cdot E]</tex>.
+В начале работы стек пуст, и указатель входной цепочки находится перед ее первым символом. Этому состоянию соответствует ситуация <tex>[E_0 \to \cdot E]</tex>.
 Для терминалов или нетерминалой, мы строим переходы к другим ситуациям по следующей схеме:
@@ Строка 47: / Строка 68: @@
 [[Файл:LRk_dfa.png|600px]]
-==== Управляющая таблица ====
+=== Управляющая таблица ===
 Теперь можно построить управляющую таблицу.
@@ Строка 164: / Строка 185: @@
 |}
-=== Формальное описание ===
+== Формальное описание ==
-==== Базовые операции ====
+=== Базовые операции ===
 Теперь опишем алгоритм формально.
@@ Строка 197: / Строка 218: @@
 |}
-==== Алгоритм построения конечного автомата ====
+=== Алгоритм построения конечного автомата ===
 Теперь обсудим алгоритм построения анализатора. Обозначим <tex>T</tex> множество состояний, <tex>E</tex> – множество переходов.
@@ Строка 219: / Строка 240: @@
 Поскольку для символа <tex>\$</tex> операция <tex>goto(I , \$)</tex> не определена , мы выполняем действие <tex>accept</tex>.
-=== Пример LR(0)-разбора ===
+== Пример LR(0)-разбора ==
 Пример будет для строки <tex>(n_1+n_2)+n_3</tex>