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

       

с помощью правого вывода, можно


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

 
  
     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).  Отличия в процедуре построения проявляются во второй части.


                                                                         LR(1)
                                                                            |
                                                                            |
                                             ------------------SLR(1)----------------
                                            |                                |                              |


                                            |                                |                              |
                                         LR(0)                   со слабым                    LL(1)
                                                                предшествованием
                                                                     Рис. 3.1
 
 
Содержание раздела