297
правок
Изменения
→Алгоритм
LR(0)-разборщик это частный случай [[LR(k)-грамматики#LR-разборщик|LR(k)-разборщикa]], для которого сейчас будет рассмотрено построение автомата и управляющей таблицы.
== Алгоритм Формальное описаное 2 ==
Заметим, что LR(0)-разборщик принимает решение о своих действиях только на основании содержимого стека, не учитывая символы входной цепочки.
}}
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</tex> {{---}} нетерминал, добавленный при пополнении грамматики, <tex>E</tex> {{---}} стартовый нетерминал.
Для терминалов или нетерминалов, мы строим переходы к другим ситуациям по следующей схеме:
<tex>{[} A \to \alpha \cdot B \beta] \xrightarrow{\varepsilon} {[} B \to \cdot \gamma] </tex>
Получаем следующий [[Недетерминированные конечные автоматы|НКА]]:.
=== Построение управляющей таблицы ===
== Иллюстрация алгоритма ==
Для иллюстрации алгоритма LR(0)-разборщика мы будем использовать грамматику:
