Изменения
Исправление очепятки
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{\text{B}} {[} A \to \alpha B \cdot \beta] </tex>
Таким образом, мы определяем новые состояния, в которое которые автомат перейдет после переноса того или иного терминала или нетерминала. Можно заметить, что алгоритм LR-разбора похож на [[Алгоритм Эрли|алгоритм Эрли]].
==== Базовые операции ====
Заметим, что хранить в каждом состоянии только по одной ситуации не имеет смысла, поэтому пусть в каждое стостояние состояние будет представлять множество ситуаций, а переходы {{---}} термилалы терминалы и нетермилалынетерминалы. Для этого определим базовые операции <tex>closure (I)</tex> и <tex>goto (I, X)</tex>, где <tex>I</tex> {{---}} множество ситуаций, <tex>X</tex> {{---}} символ грамматики (терминал или нетерминал).
* Операция <tex>closure</tex> добавляет ситуации к множеству ситуаций, у которых точка стоит слева от нетерминала. Добавляются те ситуации, которые получаются из правил, в левой части которого которых находится этот нетерминал.
* Операция <tex>goto</tex> "переносит" точку после символа <tex>X</tex>. Это означает переход из одного состояния в другое под воздействием символа <tex>X</tex>.
==== Построение автомата ====
Теперь обсудим алгоритм построения конечного автомата. Обозначим <tex>T</tex> множество состояний, <tex>E</tex> {{---}} множество переходов.
# Изначальное состояние содержит одно правило: <tex>E_0 \to E</tex>,.# Для текущего состояния делаем операцию <tex>closure</tex>,.# По всем возможный символам для каждой ситуации добавляем переходы, используя операцию <tex>goto</tex>,.
# Если множество <tex>T</tex> или <tex>E</tex> во втором или третьем пункте изменилось, возвращаемся ко второму шагу.
=== Управляющая таблица ===
После того, как автомат построен, построения автомата можно построить управляющую таблицуперейти к построению управляющей таблицы.
Обращение к таблице происходит следующим образом <tex>\mathtt{T[state, token]}</tex>, где
=== Пополнение грамматики===
Для начала переходим к ''Пополненной пополненной грамматике'':
<tex>
[[Файл:eps-dfa.png|600px]]
На картинке в двойной рамке обозначены терминальные состояния {{---}} это такие состояния, из которых можно производить свертку по правилу грамматики, а из остальных возможен только перенос. Этот термин не используется в алгоритме, а нужен только для лучшего визуального восприятия.
Теперь в одно состояние перемещаем все ситуации, в которые идут <tex>\varepsilon</tex>-переходы. Получаем [[Детерминированные конечные автоматы|ДКА]]:
== Источники информации ==
* Альфред Ахо, Рави Сети, Джеффри Ульман. Компиляторы. Принципы, технологии, инструменты. Издательство Вильямс, 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)-анализ ]
[[Категория: Методы трансляции]]
[[Категория: Восходящий разбор]]
