Изменения

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

Пусть <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] </tex> назовем '''LR(0)-ситуацией''' (англ. ''LR(0)-item'').

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

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

ЗаметимМожно заметить, что хранить в каждом состоянии только по одной ситуации не имеет смысла, поэтому пусть в каждое стостояние будет представлять множество ситуаций. Для этого определим базовые операции <tex>closure (I)</tex> и <tex>goto (I, X)</tex>, где <tex>I</tex> – множество ситуаций, <tex>X</tex> – символ грамматики (терминал или нетерминал). Операция <tex>closure</tex> добавляет ситуации к множеству ситуаций, у которых точка стоит слева от нетерминала. Добавляются те ситуации, которые получаются из правил, в левой части которого находится этот нетерминалалгоритм LR-разбора похож на [[Алгоритм Эрли|алгоритм Эрли]].

{| border="0" |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>Xclosure</tex>добавляет ситуации к множеству ситуаций, у которых точка стоит слева от нетерминала. Это означает переход Добавляются те ситуации, которые получаются из одного состояния правил, в другое под воздействием символа <tex>X</tex>левой части которых находится этот нетерминал.

{| border="0" |align="left" colspan="4"|* Операция <font size=2tex> [] '''goto''' (I, X) J={} <font color=green> // {} обозначает пустое множество </fonttex> '''for''' каждой ситуации [A "переносит" точку после символа <tex>\toX</tex> w.Xv] Это означает переход из I J += [A одного состояния в другое под воздействием символа <tex> \to X</tex>wX.v] '''return''' closure (J)</font>|}

==== Построение автомата ==== Теперь обсудим алгоритм построения конечного автомата. Обозначим <tex>T</tex> множество состояний, <tex>E</tex> – {{---}} множество переходов.# Изначальное состояние содержит одно правило: <tex>E_0 \to E</tex>.# Для текущего состояния делаем операцию <tex>closure</tex>.# По всем возможный символам для каждой ситуации добавляем переходы, используя операцию <tex>goto</tex>.# Если множество <tex>T</tex> или <tex>E</tex> во втором или третьем пункте изменилось, возвращаемся ко второму шагу.

{| border="0" |align="left" colspan="4"|<font sizeУправляющая таблица =2> E, T '''build'''() 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>|}

Поскольку для символа Обращение к таблице происходит следующим образом <tex>\$mathtt{T[state, token]}</tex> операция , где *<tex>goto(I , \$)mathtt{state}</tex> не определена {{---}} состояние автомата, мы выполняем действие *<tex>accept\mathtt{token}</tex>. В итоге получился автомат.{{---}} входной символ;

=== Построение В соответствии со [[LR(k)-грамматики#Управляющая программа анализатора |структурой]] управляющей таблицы ===После того, как автомат построен, перейдем к построению управляющей таблицы. будем действовать следующим образом:

Обращение к таблице происходит слудующим образом <ol> <li>Для каждого ребра <tex>I \xrightarrow{\mathtttext{X}} J </tex> (из состояния <tex>I</tex> в состояние <tex>J</tex> по <tex>X</tex>) мы поместим в позицию <tex>T[stateI, tokenX]}</tex>, где *<tex>\mathtt{state}s(J)</tex> (сокр. от ''shift'') , если <tex>X</tex> {{---}} состояние автомататерминал, *<tex>\mathtt{token}J</tex>, если <tex>X</tex> {{---}} входной символ; В таблице информация имеет следующий вид:нетерминал.</li> '''struct''' Cell enum: Shift Reduce Accept <font color="green"li>Для состояния <tex>I</tex>, содержащего ситуацию <tex>[A\to w \cdot]</tex> в позицию <tex>T[I, Y]</ допуск tex> для каждого терминала <tex>Y</fonttex> Error * Поместим <font color="green"tex>// ошибкаr(n)</fonttex> (сокр. от ''reduce'struct''' Shift state: '''int''' ), где <font color="green"tex>n</tex> {{---}} это номер правила в изначальной грамматике.</ переход в стостояние stateli>* Запись <tex>r(0)</fonttex>означает допуск. '''struct''' Reduce rule: '''int''' <font color="green"li>Пустая ячейка означает ошибочную ситуацию.<// свертка по правилу ruleli></fontol>

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

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

В начале работы стек пуст, и указатель входной цепочки находится перед ее первым символом. Этому <tex>0</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> Получаем следующий [[Недетерминированные конечные автоматыФайл:eps-dfa.png|НКА600px]]:

[[Файл:epsНа картинке в двойной рамке обозначены терминальные состояния {{-dfa--}} это такие состояния, из которых можно производить свертку по правилу грамматики, а из остальных возможен только перенос. Этот термин не используется в алгоритме, а нужен только для лучшего визуального восприятия.png|600px]]

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

=== Управляющая таблица Заполнение управляющей таблицы === Теперь можно построить управляющую таблицу. Поступим следующим образом: 1. для каждого ребра <tex>I \xrightarrow{\text{X}} J </tex> мы поместим в позицию <tex>[I,X]</tex> таблицы * <tex>s\ J</tex> (сокр. от ''shift'') , если <tex>X</tex> {{---}} терминал,*<tex>J</tex>, если <tex>X</tex> {{---}} нетерминал. 2. для состояния, содержащего ситуацию <tex>[A\to w \cdot]</tex>, поместим <tex>r(n)</tex> (сокр. от ''reduce'') в позицию <tex>[I, Y]</tex> для каждого терминала <tex>Y</tex>, где <tex>n</tex> {{---}} это номер правила в изначальной грамматике. 3. пустая ячейка означает ошибочную ситуацию.

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

|style="background-color:#FFF;padding:2px 20px"| <tex>s3s(3)</tex>

|style="background-color:#FFF;padding:2px 20px"| <tex>s4s(4)</tex>

|style="background-color:#FFF;padding:2px 20px"| <tex>s5s(5)</tex>

|style="background-color:#FFF;padding:2px 20px"| <tex>s3s(3)</tex>

|style="background-color:#FFF;padding:2px 20px"| <tex>s4s(4)</tex>

|style="background-color:#FFF;padding:2px 20px"| <tex>s3s(3)</tex>

|style="background-color:#FFF;padding:2px 20px"| <tex>s4s(4)</tex>

|style="background-color:#FFF;padding:2px 20px"| <tex>s5s(5)</tex>

|style="background-color:#FFF;padding:2px 20px"| <tex>s8s(8)</tex>

== Формальное описание ===== Базовые операции ===Теперь опишем алгоритм формально. Для построения множества состояний определим базовые операции <tex>closure (I)</tex> и <tex>goto (I, X)</tex>, где <tex>I</tex> – множество ситуаций, <tex>X</tex> – символ грамматики (терминал или нетерминал). Операция <tex>closure</tex> добавляет ситуации к множеству ситуаций, у которых точка стоит слева от нетерминала. Добавляются те ситуации, которые получаются из правил, в левой части которого находится этот нетерминал. {| border="0" |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>. {| border="0" |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> – множество переходов. {| border="0" |align="left" colspan="4"|<font size=2> E, T '''build'''() 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>|} Поскольку для символа <tex>\$</tex> операция <tex>goto(I , \$)</tex> не определена , мы выполняем действие <tex>accept</tex>. == Пример LR(0)-разбора конкретной строки===

!style="background-color:#EEE"| <tex>s = top()curState</tex>!style="background-color:#EEE"| <tex>a = w[ip]curToken</tex>!style="background-color:#EEE"| <tex>actionT[scurState,acurToken]</tex>

|style="background-color:#FFF;padding:2px 20px"| Перенос <tex>"("</tex>. Переход в <tex>4</tex> состояние.

|style="background-color:#FFF;padding:2px 20px"| Перенос <tex>"n_1"</tex>. Переход в <tex>3</tex> состояние.

|style="background-color:#FFF;padding:2px 20px"| Свертка: <tex>T \to \bf n</tex>. Удаление из стека <tex>n_{1}3</tex>. Переход в <tex>4</tex> состояние. Добавление в стек <tex>T2</tex>. Переход в <tex>2</tex> состояние.

|style="background-color:#FFF;padding:2px 20px"| Свертка: <tex>E \to T</tex>. Удаление из стека <tex>T2</tex>. Переход в <tex>4</tex> состояние. Добавление в стек <tex>E6</tex>. Переход в <tex>6</tex> состояние.

|style="background-color:#FFF;padding:2px 20px"| Перенос <tex>"+"</tex>. Переход в <tex>5</tex> состояние.

|style="background-color:#FFF;padding:2px 20px"| Перенос <tex>"n_2"</tex>. Переход в <tex>3</tex> состояние.

|style="background-color:#FFF;padding:2px 20px"| Свертка: <tex>T \to \bf n</tex>. Удаление из стека <tex>n_{2}3</tex>. Переход в <tex>5</tex> состояние. Добавление в стек <tex>T7</tex>. Переход в <tex>7</tex> состояние.

|style="background-color:#FFF;padding:2px 20px"| Свертка: <tex>E \to E + T</tex>. Удаление из стека <tex>E6\ +5\ T7</tex>. Переход в <tex>4</tex> состояние. Добавление в стек <tex>E6</tex>. Переход в <tex>6</tex> состояние.

|style="background-color:#FFF;padding:2px 20px"| Перенос <tex>")"</tex>. Переход в <tex>8</tex> состояние.

|style="background-color:#FFF;padding:2px 20px"| Свертка: <tex>T \to (E)</tex>. Удаление из стека <tex>(4\ E6\ )8</tex>. Переход в <tex>0</tex> состояние. Добавление в стек <tex>T2</tex>. Переход в <tex>2</tex> состояние.

|style="background-color:#FFF;padding:2px 20px"| Свертка: <tex>E \to T</tex>. Удаление из стека <tex>T2</tex>. Переход в <tex>0</tex> состояние. Добавление в стек <tex>E1</tex>. Переход в <tex>1</tex> состояние.

|style="background-color:#FFF;padding:2px 20px"| Перенос <tex>"+"</tex>. Переход в <tex>5</tex> состояние.

|style="background-color:#FFF;padding:2px 20px"| Перенос <tex>"n_3"</tex>. Переход в <tex>3</tex> состояние.

|style="background-color:#FFF;padding:2px 20px"| Свертка: <tex>T \to \bf n</tex>. Удаление из стека <tex>n_33</tex>. Переход в <tex>5</tex> состояние. Добавление в стек <tex>T7</tex>. Переход в <tex>7</tex> состояние.

|style="background-color:#FFF;padding:2px 20px"| Свертка: <tex>E \to E + T</tex>. Удаление из стека <tex>E1\ +5\ T7</tex>. Переход в <tex>0</tex> состояние. Добавление в стек <tex>E1</tex>. Переход в <tex>1</tex> состояние.

|style="background-color:#FFF;padding:2px 20px"| ДопускТак как свертка по нулевому правилу {{---}} осуществляем допуск.

* Альфред Ахо, Рави Сети, Джеффри Ульман. Компиляторы. Принципы, технологии, инструменты. Издательство Вильямс, 2003. Стр. 301 - 326.* [http://ict.edu.ru/ft/005128//ch7.pdf Терехов Ан.А., Вояковская Н., Булычев Д., Москаль А. - Разработка компиляторов на платформе .NET {{--- }} Восходящие анализаторы]* [http://window.edu.ru/resource/974/69974/files/lang_trans.pdf Б.К.Мартыненко. Языки и трансляции. Стр. 198 - 223]