LR(0)

Материал из Википедии — свободной энциклопедии
Перейти к навигации Перейти к поиску
Основная статья: LR-анализатор

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), получить оттуда номер состояния и г) затолкнуть его в стек. Символ входного потока не поглощается.

Ссылки[править | править код]

Источник — https://ru.wikipedia.org/w/index.php?title=LR(0)&oldid=101790687