Алгоритм восходящего разбора с возвратами

Мы опишем восходящий разбор в виде алгоритма синтаксического анализа, который называют алгоритмом типа «перенос-свертка». Он представляет собой по существу правый анализатор, который перебирает всевозможные обращенные правые выводы, совместимые с входной цепочкой. Один шаг алгоритма состоит в считывании цепочки, расположенной в верхней части магазина, чтобы выяснить, образуют ли верхние символы правую часть какого-нибудь правила. Если да, то производится свертка, заменяющая эти символы левой частью того самого правила. Если возможна более чем одна свертка, го эти свертки упорядочиваются произвольным образом и применяется первая из них.

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

Этот метод можно рассматривать как процедуру прослеживания всевозможных последовательностей тактов недетерминированного правого анализатора для данной грамматики. Однако так же, как в случае нисходящего разбора, надо избегать ситуаций, в которых число возможных последовательностей тактов бесконечно.

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

Для реализации алгоритма также будем использовать два магазина и .

Вход: КС-грамматика без циклов и пустых правил (ВСЕХ!!!) и входная цепочка . Предполагается, что правила из занумерованы числами .

Выход: Один обращенный правый разбор, если таковой существует. В противном случае – слово «ошибка».

Метод:

1. Произвольным образом упорядочить правила;

2. Определим конфигурацию алгоритма как упорядоченную четверку вида , где - состояние алгоритма, - номер позиции указателя чтения входной цепочки (предполагается, что -м входным символом является специальный символ (маркер) , означающий конец входной строки), - содержимое первого магазина (верх которого расположен справа), - содержимое второго магазина (верх которого расположен слева).

Алгоритм может находиться в одном из трех состояний , где - состояние нормальной деятельности, - состояние возврата, - заключительное состояние.

В магазине будет храниться цепочка терминалов и нетерминалов, из которой выводится часть входной цепочки, расположенная слева от входного указателя. В магазине будет храниться история переносов и сверток, необходимых для получения из входной цепочки содержимого магазина ;

3. Начальная конфигурация алгоритма - ;

4. Сам алгоритм работает так. Начинаем с попытки применить шаг 1.

Шаг 1. Попытка свертки

,

где правило принадлежит и имеет номер , - первая альтернатива для нетерминала и является суффиксом цепочки . Номер этого правила записывается в . Пока применим продолжаем Шаг 1, иначе, переход к шагу 2;

Шаг 2. Перенос

,

если . Затем перейти к шагу 1.

Если перейти к шагу 3.

Здесь при выполнении этого шага -й входной символ переносится в верхнюю часть магазина , позиция входного указателя увеличивается и в магазин записывается , чтобы указать, что сделан перенос;

Шаг 3. Допускание

Достигнут конец входной цепочки и найдена правовыводимая цепочка, совпадающая с входной. Обращенный правый разбор входной цепочки восстанавливается по цепочке с помощью гомоморфизма , где . После этого остановиться.

Если шаг 3 неприменим, то перейти к шагу 4;

Шаг 4. Переход в состояние возврата

при условии, что . Переход к шагу 5;

Шаг 5. Возврат.

a.

,

если правило из с номером , а следующим правилом в упорядочении, правая часть которого (правила) является суффиксом цепочки , является правило с номером . (Заметим, что ). Затем перейти к шагу 1.

Примечание. Здесь происходит возврат к предыдущей свертке и делается попытка свертки с помощью следующей альтернативы;

b.

,

если правило из с номером и для цепочки не остается никакой другой свертки. Перейти к шагу 5.

Примечание. Если других сверток не существует, надо «взять назад» данную свертку и продолжать возврат, оставляя входной указатель на позиции ;

c.

,

если правило из с номером и для цепочки не остается никакой другой свертки. Здесь символ переносится в магазин , а символ поступает в . Перейти к шагу 1.

Примечание. Мы вернулись к предыдущей свертке и, так как других сверток нет попробуем сделать перенос;

d.

,

если наверху магазина находится символ переноса .

Примечание. Здесь в позиции исчерпаны все альтернативы и надо «взять назад» операцию переноса. Входной указатель сдвигается влево, терминальный символ устраняется из , а символ переноса - из .

Если этот шаг не выполним, объявить об ошибке.

Пример №1

Задание.

Пусть задана КС-грамматика . Требуется построить обращенный правый разбор для цепочек вида