LR(0)-разбор
LR(0)-разборщик это частный случай LR(k)-разборщикa, заметим, что в данном случае , то есть решение о своих действиях принимается только на основании содержимого стека, не учитывая символы входной цепочки.
Содержание
Построение автомата и управляющей таблицы
Как было сказано в статье про LR(k)-разборщик, управляющая программа одинакова для всех LR-анализаторов, а таблица и автомат изменяются от одного анализатора к другому.
Автомат
Каждое состояние автомата будет состоять из LR(0)-ситуаций.
| Определение: |
| Пусть — КС-грамматика и . Композицию назовем LR(0)-ситуацией (англ. LR(0)-item) |
В начале работы стек пуст, и указатель входной цепочки находится перед ее первым символом. Этому состоянию соответствует ситуация , где — нетерминал, добавленный при пополнении грамматики, — стартовый нетерминал. Наховем это состояние . Входная цепочка может начинаться с любого терминального символа, с которого начинается правая часть любого правила с левой частью . Построим соответствующий переход:
Теперь мы должны выяснить, что произойдет, если анализатор выполнит перенос. Предположим, что мы выполним перенос или перенос :
Таким образом, мы определяем новые состояния, в которое автомат перейдет после переноса того или иного терминала или нетерминала.
Заметим, что хранить в каждом состоянии только по одной ситуации не имеет смысла, поэтому пусть в каждое стостояние будет представлять множество ситуаций. Для этого определим базовые операции и , где – множество ситуаций, – символ грамматики (терминал или нетерминал). Операция добавляет ситуации к множеству ситуаций, у которых точка стоит слева от нетерминала. Добавляются те ситуации, которые получаются из правил, в левой части которого находится этот нетерминал.
|
[] closure (I)
do
for каждой ситуации [A w.Xv] из I
for каждого правила грамматики X u
I += [X .u] // Операция += добавляет элемент к множеству
while I изменилось
return I
|
Операция "переносит" точку после символа . Это означает переход из одного состояния в другое под воздействием символа .
|
[] goto (I, X)
J={} // {} обозначает пустое множество
for каждой ситуации [A w.Xv] из I
J += [A wX.v]
return closure (J)
|
Алгоритм построения конечного автомата
Теперь обсудим алгоритм построения анализатора. Обозначим множество состояний, – множество переходов.
|
E, T build()
E = {}
T = {closure ([S' .S])}
do
for каждого состояния I из T
for каждой ситуации [A w.Xv] из I
J = goto(I, X)
T += {J} // ко множеству состояний добавляется новое состояние
E += (I J) // ко множеству ребер добавляется ребро, идущее из состояния I в состояние J. Этот переход осуществляется по символу X
while E или T изменились
return E, T
|
Поскольку для символа операция не определена , мы выполняем действие .
Построение управляющей таблицы
После того, как автомат построен, перейдем к построению управляющей таблицы.
Обращение к таблице происходит слудующим образом , где
- — состояние автомата,
- — входной символ;
В таблице информация имеет следующий вид:
struct Cell
enum:
Shift
Reduce
Accept // допуск
Error // ошибка
struct Shift
state: int // переход в стостояние state
struct Reduce
rule: int // свертка по правилу rule
Иллюстрация алгоритма
Для иллюстрации алгоритма LR(0)-разборщика мы будем использовать грамматику:
Пополнение грамматики
Для начала переходим к Пополненной грамматике:
Построение автомата
В начале работы стек пуст, и указатель входной цепочки находится перед ее первым символом. Этому состоянию соответствует ситуация . Для терминалов или нетерминалой, мы строим переходы к другим ситуациям по следующей схеме:
Получаем следующий НКА:
Избавимся от -переходов и получим ДКА:
Управляющая таблица
Теперь можно построить управляющую таблицу. Поступим следующим образом:
1. для каждого ребра мы поместим в позицию таблицы
- (сокр. от shift) , если — терминал,
- , если — нетерминал.
2. для состояния, содержащего ситуацию , поместим (сокр. от reduce) в позицию для каждого терминала , где — это номер правила в изначальной грамматике.
3. пустая ячейка означает ошибочную ситуацию.
Вспомним грамматику и пронумеруем правила для 2 пункта:
Управляющая таблица будет выглядеть так:
Формальное описание
Базовые операции
Теперь опишем алгоритм формально.
Для построения множества состояний определим базовые операции и , где – множество ситуаций, – символ грамматики (терминал или нетерминал). Операция добавляет ситуации к множеству ситуаций, у которых точка стоит слева от нетерминала. Добавляются те ситуации, которые получаются из правил, в левой части которого находится этот нетерминал.
|
[] closure (I)
do
for каждой ситуации [A w.Xv] из I
for каждого правила грамматики X u
I += [X .u] // Операция += добавляет элемент к множеству
while I изменилось
return I
|
Операция "переносит" точку после символа . Это означает переход из одного состояния в другое под воздействием символа .
|
[] goto (I, X)
J={} // {} обозначает пустое множество
for каждой ситуации [A w.Xv] из I
J += [A wX.v]
return closure (J)
|
Алгоритм построения конечного автомата
Теперь обсудим алгоритм построения анализатора. Обозначим множество состояний, – множество переходов.
|
E, T build()
E = {}
T = {closure ([S' .S])}
do
for каждого состояния I из T
for каждой ситуации [A w.Xv] из I
J = goto(I, X)
T += {J} // ко множеству состояний добавляется новое состояние
E += (I J) // ко множеству ребер добавляется ребро, идущее из состояния I в состояние J. Этот переход осуществляется по символу X
while E или T изменились
return E, T
|
Поскольку для символа операция не определена , мы выполняем действие .
Пример LR(0)-разбора
Пример будет для строки
| Строка | Стек | Комментарий | |||
|---|---|---|---|---|---|
| Перенос | |||||
| Перенос | |||||
| Свертка: | |||||
| Свертка: | |||||
| Перенос | |||||
| Перенос | |||||
| Свертка: | |||||
| Свертка: | |||||
| Перенос | |||||
| Свертка: | |||||
| Свертка: | |||||
| Перенос | |||||
| Перенос | |||||
| Свертка: | |||||
| Свертка: | |||||
| Допуск |
См. также
Источники информации
- Альфред Ахо, Рави Сети, Джеффри Ульман. Компиляторы. Принципы, технологии, инструменты. Издательство Вильямс, 2003. Стр. 301 - 326.
- Терехов Ан.А., Вояковская Н., Булычев Д., Москаль А. - Разработка компиляторов на платформе .NET - Восходящие анализаторы
- Б.К.Мартыненко. Языки и трансляции. Стр. 198 - 223
- Лекции по теории формальных языков, LR(0)-, SLR(1)-, LR(1)- и LALR(1)-анализ
