с помощью правого вывода, можно
Пред.Страница
След.Страница Раздел Содержание
Каждую цепочку, построенную с помощью правого вывода, можно преобразовать в начальный символ грамматики, последовательно заменяя правые части правил, выделенные в цепочки, левыми частями. Такая операция замены, являющаяся обратной по отношению к операции вывода, называется сворачиванием или сверткой. Восходящий распознаватель работает, последовательно выполняя операции переноса и свертки. Вначале он переносит символы входной цепочки в магазин до тех пор, пока в магазине не образуется правая часть какого-либо правила, а затем он выполняет операцию сворачивания.Формальной моделью восходящего распознавателя является расширенный автомат, допускающий, в отличие от простого автомата, при переходе чтение цепочки, находящейся в вершине магазина.
Детерминированные восходящие распознаватели могут быть построены для 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
