Изменения
Исправление очепятки
LR(0)-разборщик {{---}} это частный случай [[LR(k)-грамматики#LR-разборщик|LR(k)-разборщикa]], заметим. Заметим, что в данном случае <tex>k=0</tex>, то есть решение о своих действиях принимается только на основании содержимого стека, не учитывая символы входной цепочкине учитываются.
== Построение автомата и управляющей таблицы ==
=== Автомат ===
Каждое состояние автомата будет состоять из LR(0)-ситуации.
|id=def_LR0_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] </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>{[} A \to \alpha \cdot B \beta] \xrightarrow{\varepsilon} {[} B \to \cdot \gamma] </tex>
<tex>{[} A \to \alpha \cdot B \beta] \xrightarrow{\text{B}} {[} A \to \alpha B \cdot \beta] </tex>
Таким образом, мы определяем новые состояния, в которое которые автомат перейдет после переноса того или иного терминала или нетерминала.
=== Управляющая таблица ===
После того, как автомат построен, перейдем построения автомата можно перейти к построению управляющей таблицы.
Обращение к таблице происходит слудующим следующим образом <tex>\mathtt{T[state, token]}</tex>, где
*<tex>\mathtt{state}</tex> {{---}} состояние автомата,
*<tex>\mathtt{token}</tex> {{---}} входной символ;
В соответствии со [[LR(k)-грамматики#Управляющая программа анализатора |структурой]] управляющей таблицы будем действовать следующим образом: <ol> <li>Для каждого ребра <tex>I \xrightarrow{\text{X}} J </tex> (из состояния <tex>I</tex> в состояние <tex>J</tex> по <tex>X</tex>) мы поместим в позицию <tex>T[I,X]</tex>*<tex>s(J)</tex> (сокр. от ''shift'') , если <tex>X</tex> {{---}} терминал,*<tex>J</tex>, если <tex>X</tex> {{---}} нетерминал.</li> <li>Для состояния <tex>I</tex>, содержащего ситуацию <tex>[A\to w \cdot]</tex> в позицию <tex>T[I, Y]</tex> для каждого терминала <tex>Y</tex>* Поместим <tex>r(n)</tex> (сокр. от ''reduce''), где <tex>n</tex> {{---}} это номер правила в изначальной грамматике.</li>* Запись <tex>r(0)</tex> означает допуск. <li>Пустая ячейка означает ошибочную ситуацию.</li></ol> == Иллюстрация алгоритма Пример ==
Для иллюстрации алгоритма LR(0)-разборщика мы будем использовать грамматику:
T \to (E) \\
</tex>
Обратим внимание, что данная грамматика является [[Устранение левой рекурсии|леворекурсивной]], поэтому нисходящий разборщик не сможет осуществить разбор слова из этой грамматики.
=== Пополнение грамматики===
Для начала переходим к ''Пополненной пополненной грамматике'':
<tex>
=== Построение автомата ===
[[Файл:LRk_dfa.png|600px]]
=== Построение Заполнение управляющей таблицы ===
<tex>
|style="background-color:#FFF;padding:2px 20px"| <tex>1</tex>
|style="background-color:#FFF;padding:2px 20px"| <tex>2</tex>
|style="background-color:#FFF;padding:2px 20px"| <tex>s3s(3)</tex>
|style="background-color:#FFF;padding:2px 20px"|
|style="background-color:#FFF;padding:2px 20px"| <tex>s4s(4)</tex>
|style="background-color:#FFF;padding:2px 20px"|
|style="background-color:#FFF;padding:2px 20px"|
|style="background-color:#FFF;padding:2px 20px"|
|style="background-color:#FFF;padding:2px 20px"|
|style="background-color:#FFF;padding:2px 20px"| <tex>s5s(5)</tex>
|style="background-color:#FFF;padding:2px 20px"|
|style="background-color:#FFF;padding:2px 20px"|
|style="background-color:#FFF;padding:2px 20px"| <tex>6</tex>
|style="background-color:#FFF;padding:2px 20px"| <tex>2</tex>
|style="background-color:#FFF;padding:2px 20px"| <tex>s3s(3)</tex>
|style="background-color:#FFF;padding:2px 20px"|
|style="background-color:#FFF;padding:2px 20px"| <tex>s4s(4)</tex>
|style="background-color:#FFF;padding:2px 20px"|
|style="background-color:#FFF;padding:2px 20px"|
|style="background-color:#FFF;padding:2px 20px"|
|style="background-color:#FFF;padding:2px 20px"| <tex>7</tex>
|style="background-color:#FFF;padding:2px 20px"| <tex>s3s(3)</tex>
|style="background-color:#FFF;padding:2px 20px"|
|style="background-color:#FFF;padding:2px 20px"| <tex>s4s(4)</tex>
|style="background-color:#FFF;padding:2px 20px"|
|style="background-color:#FFF;padding:2px 20px"|
|style="background-color:#FFF;padding:2px 20px"|
|style="background-color:#FFF;padding:2px 20px"|
|style="background-color:#FFF;padding:2px 20px"| <tex>s5s(5)</tex>
|style="background-color:#FFF;padding:2px 20px"|
|style="background-color:#FFF;padding:2px 20px"| <tex>s8s(8)</tex>
|style="background-color:#FFF;padding:2px 20px"|
|-
|}
== Пример = LR(0)-разбора конкретной строки===
Пример будет для строки <tex>(n_1+n_2)+n_3</tex>
!style="background-color:#EEE"| Строка
!style="background-color:#EEE"| Стек
!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:#EEE"| Комментарий
|-
|style="background-color:#FFF;padding:2px 20px"| <tex>(</tex>
|style="background-color:#FFF;padding:2px 20px"| <tex>shift\ 4</tex>
|style="background-color:#FFF;padding:2px 20px"| Перенос <tex>"("</tex>. Переход в <tex>4</tex> состояние.
|-
|style="background-color:#FFF;padding:2px 20px;text-align: right;"| <tex>n_1+n_2)+n_3\$</tex>
|style="background-color:#FFF;padding:2px 20px"| <tex>n_1</tex>
|style="background-color:#FFF;padding:2px 20px"| <tex>shift\ 3</tex>
|style="background-color:#FFF;padding:2px 20px"| Перенос <tex>"n_1"</tex>. Переход в <tex>3</tex> состояние.
|-
|style="background-color:#FFF;padding:2px 20px;text-align: right;"| <tex>+n_2)+n_3\$</tex>
|style="background-color:#FFF;padding:2px 20px"| <tex>+</tex>
|style="background-color:#FFF;padding:2px 20px"| <tex>reduce\ 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;text-align: right;"| <tex>+n_2)+n_3\$</tex>
|style="background-color:#FFF;padding:2px 20px"| <tex>+</tex>
|style="background-color:#FFF;padding:2px 20px"| <tex>reduce\ 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;text-align: right;"| <tex>+n_2)+n_3\$</tex>
|style="background-color:#FFF;padding:2px 20px"| <tex>+</tex>
|style="background-color:#FFF;padding:2px 20px"| <tex>shift\ 5</tex>
|style="background-color:#FFF;padding:2px 20px"| Перенос <tex>"+"</tex>. Переход в <tex>5</tex> состояние.
|-
|style="background-color:#FFF;padding:2px 20px;text-align: right;"| <tex>n_2)+n_3\$</tex>
|style="background-color:#FFF;padding:2px 20px"| <tex>n_2</tex>
|style="background-color:#FFF;padding:2px 20px"| <tex>shift\ 3</tex>
|style="background-color:#FFF;padding:2px 20px"| Перенос <tex>"n_2"</tex>. Переход в <tex>3</tex> состояние.
|-
|style="background-color:#FFF;padding:2px 20px;text-align: right;"| <tex>)+n_3\$</tex>
|style="background-color:#FFF;padding:2px 20px"| <tex>)</tex>
|style="background-color:#FFF;padding:2px 20px"| <tex>reduce\ 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;text-align: right;"| <tex>)+n_3\$</tex>
|style="background-color:#FFF;padding:2px 20px"| <tex>)</tex>
|style="background-color:#FFF;padding:2px 20px"| <tex>reduce\ 1 </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;text-align: right;"| <tex>)+n_3\$</tex>
|style="background-color:#FFF;padding:2px 20px"| <tex>)</tex>
|style="background-color:#FFF;padding:2px 20px"| <tex>shift\ 8</tex>
|style="background-color:#FFF;padding:2px 20px"| Перенос <tex>")"</tex>. Переход в <tex>8</tex> состояние.
|-
|style="background-color:#FFF;padding:2px 20px;text-align: right;"| <tex>+n_3\$</tex>
|style="background-color:#FFF;padding:2px 20px"| <tex>+</tex>
|style="background-color:#FFF;padding:2px 20px"| <tex>reduce\ 4</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;text-align: right;"| <tex>+n_3\$</tex>
|style="background-color:#FFF;padding:2px 20px"| <tex>+</tex>
|style="background-color:#FFF;padding:2px 20px"| <tex>reduce\ 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;text-align: right;"| <tex>+n_3\$</tex>
|style="background-color:#FFF;padding:2px 20px"| <tex>+</tex>
|style="background-color:#FFF;padding:2px 20px"| <tex>shift\ 5</tex>
|style="background-color:#FFF;padding:2px 20px"| Перенос <tex>"+"</tex>. Переход в <tex>5</tex> состояние.
|-
|style="background-color:#FFF;padding:2px 20px;text-align: right;"| <tex>n_3\$</tex>
|style="background-color:#FFF;padding:2px 20px"| <tex>n_3</tex>
|style="background-color:#FFF;padding:2px 20px"| <tex>shift\ 3</tex>
|style="background-color:#FFF;padding:2px 20px"| Перенос <tex>"n_3"</tex>. Переход в <tex>3</tex> состояние.
|-
|style="background-color:#FFF;padding:2px 20px;text-align: right;"| <tex>\$</tex>
|style="background-color:#FFF;padding:2px 20px"| <tex>\$</tex>
|style="background-color:#FFF;padding:2px 20px"| <tex>reduce\ 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;text-align: right;"| <tex>\$</tex>
|style="background-color:#FFF;padding:2px 20px"| <tex>\$</tex>
|style="background-color:#FFF;padding:2px 20px"| <tex>reduce\ 1</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;text-align: right;"| <tex>\$</tex>
|style="background-color:#FFF;padding:2px 20px"| <tex>\$</tex>
|style="background-color:#FFF;padding:2px 20px"| <tex>reduce\ 0</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]
* [http://gas-teach.narod.ru/au/tfl/tfl13.pdf Лекции по теории формальных языков, LR(0)-, SLR(1)-, LR(1)- и LALR(1)-анализ ]
[[Категория: Методы трансляции]]
[[Категория: Восходящий разбор]]