LR(0) (LR(0))

LR(0) — Восходящий алгоритм синтаксического разбора контекстно-свободных грамматик, один из видов LR.

LR(0) редко применяется на практике из-за узкого класса разбираемых грамматик, но является основой для более мощных алгоритмов SLR(1) и LALR(1), последний из которых имеет богатое практическое применение.

Все три упомянутых алгоритма имеют одинаковую фазу исполнения по входному потоку, различаясь лишь в фазе построения таблицы разбора для грамматики.

Такая фаза исполнения работает очень быстро (линейное время), способна разбирать все LALR(1)-языки, то есть почти все используемые языки программирования. Кроме того, она способна генерировать внятные синтаксические ошибки вида «неразбираемый символ такой-то в такой-то позиции» и, в случае, если во всей строке таблицы разбора есть только 1 операция сдвига — вида «ожидался такой-то символ».

Ввиду высокой сложности построения таблицы разбора для алгоритмов LR(0), SLR(1) и LALR(1) обычно для этого используется генератор анализаторов типа yacc, при необходимости быстро написать анализатор вручную используется метод рекурсивного спуска или же LL(1).

Построение таблицы разбора при генерации анализатора

Введем понятие «цепочка». Это — правая часть некоего правила в грамматике, и позиция в ней, от 0 дo N (длина правой части), позиция N означает — за концом правой части правила. Обозначим цепочку R(K, L), где K — номер правила, а L — позиция в правой части.

Цепочку, где L = длина правой части правила K, назовем завершенной.

Введем понятие «символ R(K, L)», то есть символ, на который указывает цепочка. Это L-й символ из правой части правила K. Завершенная цепочка не указывает ни на какой символ.

Введем понятие «множество начальных цепочек для нетерминала». Для нетерминала A в множество начальных цепочек входят:

все цепочки R(K, 0), если K-е правило имеет A в левой части.
все цепочки R(M, 0), если M-е правило имеет в левой части нетерминал, на который указывает одна из уже найденных начальных цепочек.

Введем понятие «состояние» как множества цепочек.

Введем понятие «начальное состояние» как множество начальных цепочек символа E — начала грамматики.

Введем понятие «сдвиг» (shift) как переход из состояния в состояние под действием символа (нетерминала или терминала). Новое состояние строится из старого при сдвиге по символу A следующим образом:

из множества удаляются все цепочки, которые указывают на символ, отличный от A
оставшиеся цепочки заменяются R(K, L) → R(K, L + 1)
для каждой из замененных цепочек определяется символ, на который они указывают, и, если это нетерминал, к множеству добавляется множество начальных цепочек для этого нетерминала.

Сдвиг называется невозможным, если в результате получается пустое множество.

Для грамматики строится начальное состояние.

Далее для всех терминалов и нетерминалов строятся все возможные состояния (множества цепочек), полученные сдвигом из ранее известных состояний. При этом удаляются повторные состояния.

Далее строится таблица разбора, по вертикали — номера состояний (0 — начальное состояние), по горизонтали — символы (терминалы, нетерминалы и символ «конец потока»).

В таблицу заносятся сдвиги следующим образом: если для символа C и состояния S возможен сдвиг, то в клеточку (S, C) заносится значение «сдвиг в состояние S-штрих» (полученное в результате сдвига).

Далее заменяется начало грамматики S → E и для нового начала S в клеточку (S, конец потока) заносится значение «успешное окончание разбора».

Далее в таблицу заносятся действия приведения (reduce), только для терминалов, следующим образом: если в состоянии S есть завершенная цепочка, то во все клеточки (S, терминал) заносится значение «приведение по правилу R, правая часть длиной N символов, получаем нетерминал C из левой части правила».

Попытка занести приведение в уже занятую клеточку таблицы (например, в случае двух завершенных цепочек в состоянии) называется «конфликт сдвиг-приведение» или «конфликт приведение-приведение». В этом случае построение анализатора LR(0) невозможно, но может оказаться возможным построение по немного более сложному алгоритму SLR(1) или LALR(1), которые отличаются только способом занесения приведений в таблицу.

Исполнение анализатора по потоку символов

Используется стек анализатора, где находятся номера состояний, входной (терминалы и конец потока) и выходной (номера правил) потоки.

Вначале в стек заносится 0.

Далее, пока не получена синтаксическая ошибка или успешное окончание разбора:

по состоянию на вершине стека S и следующему символу входного потока I производится обращение к клеточке (S, I) таблицы разбора
если клеточка пуста — это синтаксическая ошибка.
если в клеточке «успешное окончание разбора» — это успешное окончание разбора (возникает только в конце входного потока, и не всегда).
если в клеточке «сдвиг в состояние S-штрих» — то затолкнуть S-штрих в стек, и поглотить символ из входного потока.
если в клеточке «приведение по правилу R, правая часть длиной N символов, получаем нетерминал C из левой части правила» — то а) вывести R в выходной поток, б) вытолкнуть верхние N номеров из стека, в) обратиться к клеточке таблицы (S, C), получить оттуда номер состояния и г) затолкнуть его в стек. Символ входного потока не поглощается.

Ссылки