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

Рассмотрим алгоритм нисходящего разбора с возвратами. Для реализации алгоритма будем использовать два магазина (и ) и счетчик, в котором будет находиться текущая позиция входного указателя.

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

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

Метод:

1. Для каждого нетерминала упорядочить альтернативы. Пусть - индекс -ой альтернативы нетерминала . Например, если - все правила из и альтернативы упорядочены так, как записаны, то индексы их соответственно примут вид ;

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

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

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

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

4. Существует всего 6 типов шагов. Шаги будем описывать в терминах их воздействия на конфигурацию алгоритма. Запись вида означает переход из одной конфигурации алгоритма в другую . Число , если не оговорено обратное, , где - множество индексов альтернатив, .

а) Разрастание дерева

где и - первая альтернатива нетерминала .

Этот шаг соответствует разрастанию частичного дерева вывода, при котором применяется первая альтернатива самого левого нетерминала дерева;

б) Успешное сравнение входного символа с порожденным символом

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

в) Успешное завершение

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

г) Неудачное сравнение входного символа с порожденным символом

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

д) Возврат по входу

для всех , т.е в состоянии возврата входные символы переносятся назад из в ;

е) Испытание очередной альтернативы

i. , если - -я альтернатива нетерминала (Заметим, что в заменяется на );

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