Part315

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

3.12. Резюме.

Одним из классов грамматик, обеспечивающих построение детерминированных магазинных распознавателей, является класс LL(1) грамматик. Этот класс включает разделенные и слаборазделенные грамматики. Чтобы определить является ли заданная грамматика LL(1) грамматикой, необходимо найти значения функций ПЕРВ и СЛЕД, а затем проверить условия принадлежности классу LL(1) грамматик. Для построения команд распознавателя нужно найти множества ВЫБОР для каждого правила грамматики. Распознаватель выполняет команды двух видов: со сдвигом и без сдвига входной головки. При работе распознавателя в магазине происходит построение вывода входной цепочки. Такой вывод соответствует левому выводу входной цепочки . Правила применяются при выводе цепочки в такой последовательности, как строится синтаксическое дерево при левом выводе от корня к конечным узлам, поэтому распознаватель называют нисходящим. Если при построении грамматики для заданного языка получилась не LL(1) грамматика, то ее можно попытаться преобразовать, применяя приемы устранения леворекурсивных правил, выделения общих частей и построения неукорачивающей грамматики. Однако, эти приемы не всегда приводят к успеху.

Каждую цепочку, построенную с помощью правого вывода, можно преобразовать в начальный символ грамматики, последовательно заменяя правые части правил, выделенные в цепочки, левыми частями. Такая операция замены, являющаяся обратной по отношению к операции вывода, называется сворачиванием или сверткой. Восходящий распознаватель работает, последовательно выполняя операции переноса и свертки. Вначале он переносит символы входной цепочки в магазин до тех пор, пока в магазине не образуется правая часть какого-либо правила, а затем он выполняет операцию сворачивания.Формальной моделью восходящего распознавателя является расширенный автомат, допускающий, в отличие от простого автомата, при переходе чтение цепочки, находящейся в вершине магазина.

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

                                                                         LR(1)
                                                                            |
                                                                            |
                                             ------------------SLR(1)----------------
                                            |                                |                              |
                                            |                                |                              |
                                         LR(0)                   со слабым                    LL(1)
                                                                предшествованием

Рис. 3.3. Диаграмма включения подклассов LR(1).