Грамматика SLR - SLR grammar

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

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

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

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

Expr → Expr * Val
Выражение → Вал + Выражение
Expr → Val

Определения

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

Правила

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

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

Алгоритм разбора

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

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

Смотрите также

Ссылки

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