Формальные языки


Резюме


Пред.Страница 

След.Страница   Раздел   Содержание



 
  

     3.15.  Резюме.

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




- Начало -  - Назад -  - Вперед -