297
правок
Изменения
Нет описания правки
LR(0)-разборщик это частный случай [[LR(k)-грамматики#LR-разборщик|LR(k)-разборщикa]], заметим. Заметим, что в данном случае <tex>k=0</tex>, то есть решение о своих действиях принимается только на основании содержимого стека, не учитывая символы входной цепочки.
== Построение автомата и управляющей таблицы ==
Как было сказано в статье про LR(k)-разборщик, управляющая программа одинакова для всех LR-анализаторов, а таблица и автомат изменяются от одного анализатора к другому. Надо заметить, что алгоритм LR-разбора похож на [[Алгоритм Эрли]].
=== Автомат ===
Пусть <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>closure (I)</tex> и <tex>goto (I, X)</tex>, где <tex>I</tex> – множество ситуаций, <tex>X</tex> – символ грамматики (терминал или нетерминал). Операция <tex>closure</tex> добавляет ситуации к множеству ситуаций, у которых точка стоит слева от нетерминала. Добавляются те ситуации, которые получаются из правил, в левой части которого находится этот нетерминал.
{| border="0"
</font>
|}
=== Управляющая таблица ===
После того, как автомат построен, можно построить управляющую таблицу.
Обращение к таблице происходит слудующим следующим образом <tex>\mathtt{T[state, token]}</tex>, где
*<tex>\mathtt{state}</tex> {{---}} состояние автомата,
*<tex>\mathtt{token}</tex> {{---}} входной символ;
В соответствии со [[LR(k)-грамматики#Управляющая программа анализатора |структурой]] управляющей таблицы будем действовать следующим образом:
1. для каждого ребра <tex>I \xrightarrow{\text{X}} J </tex> (из состояния <tex>I</tex> в состояние <tex>J</tex> по терминалу <tex>X</tex>) мы поместим в позицию <tex>[I,X]</tex> таблицы
* <tex>s\ J</tex> (сокр. от ''shift'') , если <tex>X</tex> {{---}} терминал,
*<tex>J</tex>, если <tex>X</tex> {{---}} нетерминал.
3. пустая ячейка означает ошибочную ситуацию.
== Иллюстрация алгоритма Пример ==
Для иллюстрации алгоритма LR(0)-разборщика мы будем использовать грамматику:
[[Файл:LRk_dfa.png|600px]]
=== Построение Заполнение управляющей таблицы ===
Пронумеруем правила для выполнения свертки:
|}
== Пример = LR(0)-разбора конкретной строки===
Пример будет для строки <tex>(n_1+n_2)+n_3</tex>
