Грамматика SLR

SLR-грамматики — это класс формальных грамматик, принимаемых парсером Simple LR . Грамматики SLR представляют собой надмножество всех грамматик LR(0) и подмножество всех грамматик LALR(1) и LR(1).

При обработке анализатором SLR грамматика SLR преобразуется в таблицы синтаксического анализа без конфликтов сдвига/сокращения или сокращения/сокращения для любой комбинации состояния анализатора LR(0) и ожидаемого символа просмотра вперед. Если грамматика не является SLR, таблицы синтаксического анализа будут иметь конфликты сдвига/сокращения или конфликты свертывания/сокращения для некоторых состояний и некоторых символов просмотра вперед, и результирующий отклоненный синтаксический анализатор больше не будет детерминированным. Синтаксический анализатор не может решить, следует ли смещать или сокращать следующее, или не может выбрать между двумя возможными сокращениями. Синтаксические анализаторы SLR используют вычисление Follow(A) для выбора символов просмотра вперед для каждого завершенного нетерминала.

Парсеры LALR используют другие вычисления, которые иногда дают меньшие и более точные наборы опережающего просмотра для одних и тех же состояний синтаксического анализатора. Эти меньшие наборы могут устранить перекрытие с действиями сдвига состояния и перекрываться с опережением других сокращений в этом же состоянии. Конфликты перекрытия, о которых сообщают анализаторы SLR, в этом случае являются ложными и являются результатом приблизительного расчета с использованием Follow(A).

грамматика Неоднозначная будет иметь неизбежные конфликты сдвига/сокращения или конфликты свертывания/сокращения для каждого метода анализа LR, включая SLR. Распространенный способ неоднозначности грамматик компьютерного языка заключается в том, что некоторый нетерминал является как лево-, так и право-рекурсивным:

Выражение → Выражение * Значение

Выражение → Значение + Выражение

Выражение → Вал

Определения

Правило вида B → y • в состоянии автомата SLR(1) называется неприводимым или находящимся в приведенном состоянии, поскольку оно полностью расширено и неспособно совершить какой-либо сдвиговый переход. Правила в этом состоянии будут иметь точку ( • , текущая позиция просмотра вперед), расположенную в самом правом конце их правой части (правая сторона).

Правила

Грамматика называется SLR(1) тогда и только тогда, когда для каждого состояния s в автомате SLR(1) не нарушено ни одно из следующих условий:

Для любого приводимого правила A → a • Xb в состоянии s (где X — некоторый терминал) не должно существовать некоторого неприводимого правила B → a • в том же состоянии s такого, что последующий набор B содержит терминал X . Говоря более формально, пересечение множества, содержащего терминал X , и последующего множества B должно быть пустым. Нарушение этого правила является конфликтом Shift-Reduce .
Для любых двух полных элементов A → a • и B → b • в s Follow (A) и Follow(B) не пересекаются (их пересечение — пустое множество). Нарушение этого правила является конфликтом «сокращение-сокращение» .

Алгоритм парсинга

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

Если состояние s содержит любой элемент формы A → a • Xb , где X — терминал, а X — следующий токен во входной строке, то действие состоит в том, чтобы переместить текущий входной токен в стек, и новое состояние для помещения в стек — это состояние, содержащее элемент A → aX • b .
Если состояние s содержит полный элемент A → y • и следующий токен во входной строке находится в Follow(A) , то действие заключается в сокращении по правилу A → y . Приведение по правилу S' → S , где S — начальное состояние, эквивалентно акцепту; это произойдет только в том случае, если следующим входным токеном будет $ . Во всех остальных случаях новое состояние вычисляется следующим образом. Удалите строку y и все соответствующие ей состояния из стека синтаксического анализа. Соответственно, бэкап в ДФА до состояния, из которого началось построение y . По построению это состояние должно содержать элемент вида B → a • Ab . Поместите A в стек и поместите состояние, содержащее элемент B → aA • b .
Если следующий входной токен не соответствует ни одному из двух вышеперечисленных случаев, объявляется ошибка.

См. также

Ссылки

«Построение компилятора: принципы и практика» Кеннета К. Лаудена.