КАТЕГОРИИ: Архитектура-(3434)Астрономия-(809)Биология-(7483)Биотехнологии-(1457)Военное дело-(14632)Высокие технологии-(1363)География-(913)Геология-(1438)Государство-(451)Демография-(1065)Дом-(47672)Журналистика и СМИ-(912)Изобретательство-(14524)Иностранные языки-(4268)Информатика-(17799)Искусство-(1338)История-(13644)Компьютеры-(11121)Косметика-(55)Кулинария-(373)Культура-(8427)Лингвистика-(374)Литература-(1642)Маркетинг-(23702)Математика-(16968)Машиностроение-(1700)Медицина-(12668)Менеджмент-(24684)Механика-(15423)Науковедение-(506)Образование-(11852)Охрана труда-(3308)Педагогика-(5571)Полиграфия-(1312)Политика-(7869)Право-(5454)Приборостроение-(1369)Программирование-(2801)Производство-(97182)Промышленность-(8706)Психология-(18388)Религия-(3217)Связь-(10668)Сельское хозяйство-(299)Социология-(6455)Спорт-(42831)Строительство-(4793)Торговля-(5050)Транспорт-(2929)Туризм-(1568)Физика-(3942)Философия-(17015)Финансы-(26596)Химия-(22929)Экология-(12095)Экономика-(9961)Электроника-(8441)Электротехника-(4623)Энергетика-(12629)Юриспруденция-(1492)Ядерная техника-(1748) |
Алгоритм нисходящего разбора с возвратами
Рассмотрим алгоритм нисходящего разбора с возвратами. Для реализации алгоритма будем использовать два магазина (и ) и счетчик, в котором будет находиться текущая позиция входного указателя. Вход: Нелеворекурсивная КС-грамматика и входная цепочка . Предполагается, что правила из занумерованы числами . Выход: Один левый разбор цепочки , если таковой существует. В противном случае – слово «ошибка». Метод: 1. Для каждого нетерминала упорядочить альтернативы. Пусть - индекс -ой альтернативы нетерминала . Например, если - все правила из и альтернативы упорядочены так, как записаны, то индексы их соответственно примут вид ; 2. Введем понятие конфигурации алгоритма – это упорядоченная четверка вида , где - состояние алгоритма, - номер позиции указателя чтения входной цепочки (предполагается, что -м входным символом является специальный символ (маркер) , означающий конец входной строки), - содержимое первого магазина, - содержимое второго магазина; Примечание: Будем считать, что верх первого магазина расположен справа, а верх второго слева. Магазин служит для представления «текущей» левовыводимой цепочки, т.е. той, которая получилась к данному моменту в результате развертки нетерминалов. Другими словами, верхний символ магазина будет символом, помечающим активную вершину порожденного к данному моменту дерева вывода. В магазине представлены текущая история проделанных выборов альтернатив и выходные символы, по которым прошла входная головка. Алгоритм может находиться в одном из трех состояний , где - состояние нормальной деятельности, - состояние возврата, - заключительное состояние. 3. Начальная конфигурация алгоритма - ;
4. Существует всего 6 типов шагов. Шаги будем описывать в терминах их воздействия на конфигурацию алгоритма. Запись вида означает переход из одной конфигурации алгоритма в другую . Число , если не оговорено обратное, , где - множество индексов альтернатив, . а) Разрастание дерева , где и - первая альтернатива нетерминала . Этот шаг соответствует разрастанию частичного дерева вывода, при котором применяется первая альтернатива самого левого нетерминала дерева; б) Успешное сравнение входного символа с порожденным символом при условии, что . Если -й входной символ совпадает с очередным порожденным терминальным символом, то он передается из в , а позиция входного указателя увеличивается на единицу; в) Успешное завершение . Достигнут конец входной цепочки и найдена левовыводимая цепочка, совпадающая с входной. Левый разбор входной цепочки восстанавливается по цепочке с помощью гомоморфизма , что , , где - номер правила и - -ая альтернатива нетерминала ; г) Неудачное сравнение входного символа с порожденным символом Переходим в состояние возврата, как только обнаруживается, что порожденная левовыводимая цепочка не совместима с входной цепочкой; д) Возврат по входу для всех , т.е в состоянии возврата входные символы переносятся назад из в ; е) Испытание очередной альтернативы i. , если - -я альтернатива нетерминала (Заметим, что в заменяется на ); ii. Следующая конфигурация невозможна, если и имеет только альтернатив. (Это условие указывает на то, что всевозможные цепочки, совместимые с входной цепочкой уже исчерпаны, а ее разбор не найден); iii. в оставшихся случаях. (Здесь исчерпаны альтернативы нетерминала и дальнейший возврат происходит путем удаления из и замены в цепочки на ). Алгоритм выполняем следующим образом Шаг 1. Исходя из начальной конфигурации, вычислять последующие конфигурации , пока их можно вычислить;
Шаг 2. Если последняя вычисленная конфигурация - , то выдать и остановиться, в противном случае – «ошибка»;
Пример: Пусть задана КС-грамматика вида . Требуется построить левый разбор для цепочек вида , , . Решение: 1. Сделаем приведение грамматики, т.е. удалим пустые и цепные правила 2. Перенумеруем правила грамматики ; Определяем левый разбор как последовательность вида ; ; Определяем левый разбор как последовательность вида ; ; .
Дата добавления: 2014-01-07; Просмотров: 1627; Нарушение авторских прав?; Мы поможем в написании вашей работы! Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет |