SLR(1)

SLR(1) — восходящий алгоритм синтаксического разбора.

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

Алгоритм собственно разбора (исполнения анализатора по входному потоку) одинаков и у SLR(1), и у LR(0) — и, шире, у LALR(1). Различаются только алгоритмы построения таблицы разбора по грамматике в процессе генерации анализатора.

Общие сведения
SLR(1)

Описание

Для каждого нетерминала A в грамматике генерируется множество терминалов First(A), определённое следующим образом:

  • если в грамматике есть правило с A в левой части и правой частью, начинающейся с терминала, то данный терминал входит в First(A)
  • если в грамматике есть правило с A в левой части и правой частью, начинающейся с нетерминала (обозначим B), то First(B) строго входит в First(A)
  • никакие иные терминалы не входят в First(A)

Эти же множества используются для построения анализатора LL(1).

Далее на основе множеств First(A) генерируются множества Follow(A), определённые следующим образом

  • если в грамматике есть правило, где встречается A не на последней позиции, и за ним следует терминал, то терминал входит в Follow(A).
  • если в грамматике есть правило, где встречается A не на последней позиции, и за ним следует нетерминал (обозначим B), то First(B) строго входит в Follow(A)
  • если в грамматике есть правило, где встречается A на последней позиции, то Follow(C) строго входит в Follow(A), где C — левая часть правила.
  • никакие иные терминалы не входят в Follow(A)

(возможно обобщение этих условий для случая наличия правил B -> null)

Далее производится генерация таблицы разбора, как для LR(0), с отличием при занесении действий приведения. Приведение для состояния S и входного символа C заносится в таблицу только тогда, когда в S есть цепочка, соответствующая целой правой части правила, и нетерминал N из левой части правила удовлетворяет условию «C входит в Follow(N)».

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

Практическое применение

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

Арифметические выражения с унарными и бинарными операциями и скобками разбираются по SLR(1)

См. также

Литература