Каждую цепочку, построенную с помощью
правого вывода, можно преобразовать в начальный символ грамматики,
последовательно заменяя правые части правил, выделенные в цепочки,
левыми частями. Такая операция замены, являющаяся обратной по отношению
к операции вывода, называется сворачиванием или сверткой.
Восходящий распознаватель работает, последовательно выполняя операции
переноса и свертки. Вначале он переносит символы входной цепочки
в магазин до тех пор, пока в магазине не образуется правая
часть какого-либо правила, а затем он выполняет операцию
сворачивания.Формальной моделью восходящего распознавателя является расширенный
автомат, допускающий, в отличие от простого автомата, при переходе
чтение цепочки, находящейся в вершине магазина.
Детерминированные восходящие распознаватели
могут быть построены для LR(k) грамматик, которые являются подклассом контекстно-свободных
грамматик. Процедура построения LR(k)-распознавателя оказывается
весьма сложной и трудоемкой, поэтому в настоящем пособии рассматриваются
грамматики LR(0) и SLR(1), которые включаются в подкласс LR(1) грамматик.
Подкласс грамматик SLR(1) грамматик является достаточно широким. Кроме
грамматик LR(0) он включает грамматики LL(1) и грамматики слабого предшествования.
Диаграмма включения подклассов LR(1) грамматики приведена на рис.3.1.
Принадлежность к подклассу LR(0) или SLR(1) грамматик устанавливается
путем проверки возможности построения соответствующего распознавателя.
Процедура построения восходящих распознавателей состоит из двух частей:
построение таблицы переходов и построение таблицы действий. Первая
часть этой процедуры оказывается одинаковой для преобразователей LR(0)
и SLR(1). Отличия в процедуре построения проявляются во второй части.
LR(1)
|
|
------------------SLR(1)----------------
|
|
|
|
|
|
LR(0)
со слабым
LL(1)
предшествованием
Рис. 3.1