Кук Д., Бейз Г. - Компьютерная математика (1048841), страница 44
Текст из файла (страница 44)
8.8 раабора. Конечно, в большинстве примеров величина !И бесконечна, и поэтому этот процесс невозможен; однако если грамматика не имеет неудачных продукций, то это приближение обеспечивает основу техники раабора, которая, по крайней мере в локальном контексте, мон«ет использоваться на практике. Если длина сентенциальпых форм не может уменьшаться при применении С, то при проверке а«вЬ(С), !с«! и можно отбросить все формы (перед получением строк над Т), чья длина превосходит и. Предложения, длина которых не превосходит и, могут сравниваться с и обычным путем; в разумной грамматике все такие возможные строки должны порождаться аа конечное число шагов.
Сейчас мы займемся приведением грамматики и построени,м ее аквивалентной версии, которая обладает <более легким» грамматическим разбором. Для того чтобы процесс порождения, связанный ю данным предложением, был конечен, необходимо гарантировать, что все последовательности вывода действительно могут быть получены. Следовательно, появление таких ситуаций, как Х- Х и Х- Л, представляет интерес, Записывая их непосредственно как продукции, это 287 легко обнаружить; однако более общие ситуации Х=».Х иХ=».Л труднее локалиаовать.
Болев того, два типа вы водов связаны таким обрааом, как ето продемонстрировано в следующем примере. П р и м е р 4.2. Предположим, что включенные лродукции некоторой грамматики имеют вид Х У, У»т', 2 У, тр Я, У Х. Следуя во»можной последовательностью вывода ив Х, по« лучаем, что Х =~ Х, и, следовательно, как только Х встречается в сентенциальной форме, мы могли бы вставить прогрессию Х«. У-' И' «2.» У"-Х (снова и снова), не получая, таким обравом, ничего, кроме неодновначности. Как нетрудно видеть, вто «петля» иа нетерминалов внутри № Заметим, однако, что мы могли бы иметь практически такую же ситуацию в вавуалированном виде, если вместо Х - У и У - РУ имели бы, например, Х- АУ, У- АИ'А, А - Л.
г' Определение. Л-нродркцией является продукция вида КСГ С (У, Т, Р, Я) называется Л-свободной если а) или Р не имеет Л-продукций, б) или существует только одна Л-продукция 8- Л и Я пе появляется в правой части произвольной продук» ции иа Р. Продукция является одиночной, если она имеет вид Х- У, где Х, Уы№ Продукция вида Х- Х при ХыУ нааывается тривиаль- ной. КСГ б ° (№ Т, Р, 8) нааывается циклически сво- бодной если не существует выводов вида Х=» Х для лю- бого Хы№ У Как уже отмечалось, обнаруя«ение и удаление циклов и Л-выводов тесно свяаапы.
Мы начнем с места располо- жения всех нетерминалов, иа которых может быть до- стигнуто Л. Замечание. Для ааданной грамматики б (У, Т, Р, д) череа № будем обоапачать множество (Х: Х=». Л~ с ж№ д Алгоритм. Вычисление №. Вход: произвольная КСГ 6 (Л<, Г, Р, Я). Выход: №. Метод: пусть Р=(Р<, ..., Р<н), где каждое Р< имеет вид а<--()<: а,жУ, 8<жом«; тогда, рассматривая № как «переменную» типа множе- ства, имеем № Э, !Р!, гереа1 (И(<х< ф !Ул) авд (р< си Ул) 1Ьеп(№ №О(<х,), ! - !Р!) е)вел -1-1) нн(И2 О. г Алгоритм.
Переход к Л-свободной грамматике. Вход: произвольная КСГ б (У, Т, Р, Б). Выход: эквивалентная Л-свободная КСГ б' (Л<', Т, Р', б'). Метод: 1) определяем №', 2) строим Р' следующим образом: а) Пусть А - а«В<а<В»с«»...В,а,<нР, где й > О и нри 1 «< < й каждое В< есть в №, но ни один символ в а<«в У«(О<1~й) не находится в №. Тогда добавим к Р' продукции вида А - ааХ<а<Х»и»...
Х«им где Х, есть или В< или Л, без добавления А - Л к Р' (это могло бы иметь место, если бы все а< совпали с Л), б) Пусть еж№. Тогда добавим к Р' продукции о'- ЛЫ, где Б' — новый символ, и тогда <т" ° ЖО (Я'); в против- ном случае У' У и о' Я. У Сейчас мы можем рассмотреть удаление циклов из КСГ.
Месторасположение циклов может быть легко най- дено выделением отношения р ((А, В): А - ВжР! н формированием замыкания р+. Тогда ясно, что произ- вольное Х: Хр+Х должно быть в цикле. Объединим это вместе со схемой «обратной замены», которая удаляет !9 д. Ктй, г. Б«ЗВ 289 все петерминалы внутри произвольного цикла. (Она также удаляет лсобую тривиальную продукцию.) Алгоритм.
Переход от КСГ к эквивалептпой циклически свободной грамматике. Вход: Л-свободная КС1" С =(ЛУ, Т, Р, Я). Выход: эквивалентная циклически свободная грамматика С' (У', Т', Р', Я'). (Петермииалы С переименованы: А~ па А„, где и !У!У), Я на Аь а каждую продукцию Р выражают через а~ — 6,.) Дополнительно мы используом множество 1ХСУСЬЕЯ, а и котермипалов обозначаем через ВЕРЬАСЕу, где ! ~1-= и.
Ллгорптм будет иметь следующий впд: !) определяем р над г(„так, что уру тогда и только тогда, когда А, — А,<а Р; 2) пусть о р+; 3) 1ХСУСЬЕЯ вЂ” В; 4) 1ог ! 1гоп1 ! !о и — ! ао (! у !. + ! Ь и йо И (у Ф1ХС'х'СЬЕВ апй !оу аж! уо! ) !(хеп (11чС'х'СЬЕВ - 1МСУСЬЕЯ О (у), ВЕРЬЛСЕу А,) ) 5)у-О 1ог ! !гол ! !о!Р! оо (1ог а!! угж1ХСУСЬЕЯ !в Р, гер!асе А„Ьу ВЕРЬАСЕй и!г!пп пеи Р, И(пеъ Р; ф (Р;, ..., Р;) апс)а, Ф ~, 1п пеп Р,) !!гоп (у»-у + 1, Р;» — пе~т Р;)) 6) С' =(УУ~1МСУСЬЕЯ, Т, Р', Я). УУ Говорит, что КСГ явзяетсп приведенной, если она Л-свободна, циклически свободна и редуцврована.
Полу- 290 чив собственную КСГ С, мы можем использовать ее для проверки условия аж Ь(С) для данного аж Т». 4.2. Ыодифпкацпп грамматического разбора, Как было установлено во введенпи к 9 4, задача грамматического разбора строки состоит в заполнении треугольника вывода (рис. 8:7) с соответствующим порезом. Конечно, в болыпнпстве случаев зто заполнение нельзя разумно выполнить за один шаг, п обычно апо получается при помощи последовательности поддеревьев. Зтн последовательности поддеревьев могут быть получены многими способами; три наиболее пспользуомых способа изображены на рис.
8.9. а,... ... о» вк.. ...а, а,... и ь е Рис. 8.9 Стратегия грамматического разбор», изображенная на рнс. 8.9,а, называется грамматическим разбором сверху вниз. В нем применяют продукции (в некотором выбранном порядке) к септеппнальпым формам, пытаясь расширить Я внутрь строки а~...а.. При таком разборе естественно использовать е качестве гида часть. строки (а1...а„), чтобы управлять выводом. Для практических рассмотрений, согласугощихся с чтением а1...а„ слева направо (рис. 8.9, Ь) п желанием начать разбор перед включением полной строки, необходимо нснользовать начало строкв.
Следовательно, в поиске сентенциальных форм, которые начинаются с а~я Т (и соответственно исследуя терминальные строки как начальные подстроки последовательных частой входной строки), мы должны отвергнуть возможность вьшодов аида Х=~Хр (Хан М, ~~ Г~). Таким образом, чтобы начать разбор сверху вниз, мы должны удалить левую рекурсию. В общем случае вто может быть сделано с использованием процесса, аналогичного решению системы линейных алгебраических уравнений. Часто возможно рассматрпват» одну рекурсию за один раа и удалять ее, ис- 19» 39» пользуя довольно простое тождество.
Оправданием такого подхода слуя«нт порождаемый язык. Рассмотрим Х з- Х««. Путем «обратной подстановки» правых частей продукций мы можем получить прямую рекурсию как элемент Р; таким образом, имеем Х- Хс«! !!. Рассматривая это как полную грамматику над И, р) (!) представляет все другие нелеворекурсивные возможности для Х), очевидным ооразом получаем, что «.
(Х) (ра": п = О или л ж Ю. Это множество может порождаться также продукциями Х- ЬУ, У- аУ!Л, которые не являются леворекурсивными (они нраворекурсивны), Чтобы закончить преобразование, продукция Х- рУ должна быть расширена при необходимости до правильного числа тернов. П р и м е р 4.3. Рассмотрим грамматику с продукциями А - Вс ! сС, В - хА ! Се, С ° АЫ й, Она леворекурсивна, поскольку А «.
Вс «. Сес « АЬес. Путем обратной подстановки для С в В и В в А полу- чаем В- хА !(АЬ !ю)с В- хА ! АЬе ! юе, А-«ВС! ИСм«А-» (хА !АЬ«! ие)с!сС~ виА -и хАс ! АЬес ! и ес )НС виА -ь А Ьес ! хА с ! и сс ! бС. а а Поэтому, используя преобразование А- ру, У- с«У!Л, получаем А- (хАс ! юес ! «(С)У А- хАсУ ! юесУ! НСУ, У- Ьссу!Л,  — хА!Се, С АЬ!ю. К Заметим, что в этом примере В может быть «вырезаноз и может не принимать никакого участия в произвольком предложении, порожденном из коркя А (следовательно, надо удалить все следы В иа грамматики). 292 Отметим также, что мы ввели Л-продукцию. Эта продукция, созданная как побочный эффект «преобразования грамматического разбора», вызвала бы меньше проблем, чем аналогичная продукция, встречающаяся естественным образом.
Символ В может быть удален при помощи алгоритма для удаления бесполезного символа. Хотя обычно будет достаточно частичного удаления отдельных лееорекурснвкых цепей внутри М, мы должны нспольаовать матричное обобщение описанного процесса для того, чтобы справиться с удалением внутренних левых рекурсий.
Напомним, что в обычном случае мы заменяем Х- ~ Ха ! р прп помощи Х !)У, У~ ау !Л. Если мы имеем и нетермнналов Хь ..., Х„, которые являются взаимно леворекурсивпыми, так что не сводятся путем последовательности обратных замен к простому случаю, тогда мы можем представить соответствующие продукции схематически следующим образом: Х~ - Х~А~| ! ХзАм 1." ! Х.А.~ ! Вь Хз Х~А и ! ХзАм ! .. ! Х„А„з ! Вь Х„- Х,Аы ! ХзАз, ! ... ! Х„А„„!В„, где каждое Ае представляет собой остаток всех операций, которые могут быть выведены нз Х, и которые начина- ются с Х„и аналогично каждое В, представляет все аль- тернативы для нетерминалдв Х„которые не начинаются с элементов !Хь ..., Х„). Теперь, поскольку Ае и В~ являются множествами строк, отсюда следует, что: 1) если Х,- Х„то ЛыАо,' 2) если Х~ - и и и ть Х<р для р ж У», то а ьч В;, 3) если Х, ~ Х,т для любого т ж У", то Ае И.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
