Теория синтаксического анализа, перевода и компиляции - Том 2 (943929), страница 21
Текст из файла (страница 21)
Например, каноническое множество 5!.)((!)-грамматики нэ упр. 7.3.1(а) состоит нз 13 (.)7(1).таблиц. Алгорнтлг 7.13 даст множество, содержащее не менее !4 !.(((!)- таблиц, алгоритм 7.10 †множест нз 14 5ВП(1)-таблиц, В то же время, разумно используя отсрочку в обнаружении ошибок н выполняя слияние таблнп, можно получить множество из 7 ).к (1)-таблиц. *7.4.1. Рассмотрите класс (6о где 6„содержат правила 5 А, А, агА, А, аВ(Ь, В; агВг(Ь, Покажите, что число таблиц в наноннческом множестве Ер(0)-таблнп для 6„эксвонеицнально эаваснт от л.
7.4.2. Покажите, что все грамматики нз упр. 7.3.1 являются 5(.П(1)-грамматиками. 7.4.3. Покажите, что каждая ВР(0)-грамматика является ЯП(0)-грамматикой. "7.4.4. Покажите, что каждая простая ССП-грамматика является 5ВЙ(1)-грамматнкой. 7щ.б. Понажнте, что грамматика нз примера 7.23 не является 5ВК(Ь)-грамматикой нн для какого Ь)0. *7.4.6. Покажите, что всяная ВВ(1)-грамматика является 5!.П(1)-грамматикой.
Всякая лн ВВ(2)-грамматике является 5Ы(2).гралгматикой) 7.4.7. С помощью алгоритма 7.10 постройте анализаторы для всех грамматик яз упр. 7.3.1. 7.4.3. Пусть сн,— каионнчесная система множеств ВП(Ь)-ситуаций для 6. Пусть Фс — система множеств (.(((О)-сггтуацн(г для 6. 1Тонажвте, что д', н д'с имеют одинаковые множ~ства ядер. Указание: Полая!иге А=СОТО(Л„а), где .,1,— начальное множество системы д'„и проведите индукцию по )а), 7.4.9.
Покажите, что СО)(В(ООТО(8, а)) =-ПОТО(СОВЕ(8), и). где, как и ранее, Абдс. ГЛ 1. МЕТОДЫ ОПТИМИЭ1Ш1И СИНТАКСИЧЕСКИХ АНАЛИЗАТОРОВ УПРАЖНЬНИЯ Определение. Грамматика С = (АЕ Х, Р, 5] называется ЕК(Ь)-грамметикой с заглядыванием н обозначается ЕАЕК(Ь), если следующий алгоритм позволяет получить множество ЕР(Ь)-таблиц: (!) Построить для 6 каноническую систему д', множеств ЕР(йрситуаций. (2) Для каждого 4 Е Р, обозначим через мЕ объединение таких 31 Е рю что СОРЕ(53) =СОРЕ(А). (3) Пусть д' — множество всех А', построенных на шаге (2). Множество ЕК(АВтаблип строится по Т обычным образом. 7.4.!6. Покажите, что если С вЂ” 5ЕК(Ь)-грамматика, то она является 1.АЕК(Ь)-грамматикой. 7А.11.
Покажите, что описанный выше алгоритм построения ЕАЕК-таблиц порождает множество таблиц, эквивалентное канонячсскому множеству. 7,4.12. (а) Покажите, что грамлгатика из примера 7.26 яв. ляется 1.АЕК(1)-грамматикой. (б) Покажите, что грамматика из примера 7.27 не является !.АЕЙ(АЕграмматикой ин для какого Ь.
7.4.13. Пусть 6 — грамматика с правилами 5 Е=Р(К !. в Й(а Р Е Покажите, что С валяется ЕАЕР(!)-грамматикой и не является 5Щ1)-грамматикой. 7.4.14. Покажите, что существуют ЕАЕК-грамматики, не яв. ляюшнеся ЕЕ-грамматиками, н обратно. *7.4.!6. Пусть 6 — ЕА1.Й-грамлгатика, а Тл — каноническая система множеств ЕК(0)-ситуаций для С. Будем говорить, что дз имеет конфликт „перенос -свертка", если некоторое множество .(е Рл содержит ситуации (А аг] и (В й ау], где айЕОЕЕОуу(Л).
Покажите, что в случае такого конфликта ЕАЕР-анааизатор всегда выполняет перенос. *7А.16. Пусть (Т, Т,) — множество 5Щ!)-таблиц для 5Щ()-грамматики 6 =(КЕ Х, Р, 5). Покажите, что (1) все элементы огпибкн у функций переходов несущественны, (2) все элементы ошибки, соответствующие входному символу а у функции действия таблицы Т, существенны тогда и только тогда, когда удовлетворяется одно из сдедующих условий: (з) Т вЂ начальн таблица Тм (б) в Р есть такая таблица Т'=<), я>, что Т=6(Ь) для некоторого Ь ЕХ, 114 (в) в а есть такая таблица Т'=(Е й>, что Т принадлежит ЫЕХТ(Т',1) и )(а) =свертка.
"7.4.17. Пусть 6=(РЕ Х, Р, 5) — КС-грамматика. Покажите, что 6 является ЕК(й)-грамматикой тогда и только тогда, когда для каждого расщепляющего множества В'ЕК все грамматики- компоненты С„являются ЕР(Ь)-грамматиками, А Е КЕ (Замвчаиивг 6 моныт не быть !.Р(й)-грамматииой, но все же иметь такое расщеплныщсв Миажестно 14', что для А ЕВ' все СА будут ).Р(Ь).
грамматиками,) 7.4.!6. Выполните упр. 7.4.17 для случая 1-!.(Ь)-грамматик, 7.4.!9. Воспользуйтесь алгоритмаии 7.12 н 7.13 для ностра. ения множества ЕК(1)-таблиц для С„взяв в иачестве расщепляющего множества (Е, Т, Р). Сравните почученнос множество таблиц с множеством на рис. 7.44.
7,4.29. При каких условиях алгоритмы 7.12 и 7,13 для всех расщепляющих множеств кетерминалов будут порождать для 6 одно и то же множество ЕК(!)-таблицу А7.4.21. Предположим, что с помощью ЕАЕР(1)-алгоритма не удзетсн построить множество ЕК(!)-таблиц для грамматики С=(йЕ Х, Р, 5) из-за тога, что возникает множество ситуаций, содержащее такие ситуации (А а, а] и (В й 7, Ь], что у~в и аЕ ЕРР(7Ь). Покажите, что если !Анын — расщепляющее множество и ЛЕВ', то алгоритм 7.13 также не даст множества ЕК(!)-таблиц с однозначно определенными действиями разбзра 7.4.22.
Попытайтесь с помощью алгоритмов 7.12 и 7.13 построить множество ЕК(1)-таблиц для грамматики нз упр. 7,27, взяв в качестве расшепляющего множества (5, А). 7,4,23. Примените алгоритмы 7.12 и 7.13 для построения множества ЕР(!)-таблиц для грамматики из упр.
7.3.8(а), имеющей 7 таблиц. *7.4.24. Воспользуйтесь методами отсрочки в обнаружении ошибок и слияния таблиц для нахождения эквивалентного множества из 7 1.К(1)-таблип для грамматики нэ упр. 7.3.! (а). *7.4.26. Приведите пример (1,!)-ОПК-грамматики, которая не янляется 5ЕЙ(1)-грамматикой. "7.4.26. Покажите, что если применить алгоритм 7.9 к нно. жеству БЕЙ(1)-таблиц для грамматики, нлгеюшей не более одного цепного правила для каждого нетерминала, то все свертки по цепным правилам будут исключены. Проблемы двя исследования 7,4.27. Найдите дополнительные способы построении небольших множеств Щй)-таблиц для ЕК(й)-грамматик, не испольму- 1!5 гл.
! ИатОды ОптимизАции синтаксических АиАлизАтОРОе Т.б. АНАЛИЗИРУЮЩИЯ *ЭТОМАГЫ ющие преобразований, подробно описанных в равд. 7.3. Ваши методы не обязательно должны работать для всех СК(й).грамма. тик, ио они должны быть применимы хотя бы к грачматикам, прсдставляющим практический интерес, например к тем, которые приведены в приложении и тому 1. 7А.23, Когда !.К(й).анализатор достигает о!пнбочиой конфигурации, на практике обычно вызывается программа нейтрализации ошибок, изменяющая входпу1о цепочку н содержимое магазина так, чтобы можно было продолжить нормальный рззбор.
Один из методов преобразования ошибочной конфигурации 1.К(1)-анализатора состоит в том, что на входной лепте разыс. кивается олин из определенных входных символов. После то о нак такой вкодиой символ а найден, в магазине разыскивается таблица Т=- <7, дщ постРоеннаЯ по миожествУ ситУаций к(, содержащему ситуаци!о вида (А - а, а], А~В. Процедура нейтрализации ошибок состоит в удалении всех входных символов вплоть до а и стирании в магазине всех символов и таб.1нц, расположенных выше Т.
Затем в нагавки помещается нетермииал А и вслед за ним таблица Е(А). Из уар, 7.3 8(в) след)ет, что Е(А) Фошибна. Суть такого метода нейтрализации ошибок в тоы, что символы грамматики, расположенные в магазине выше Т, вместе с входными символамн вплоть до а рассматриваниси каи порождение символа А.
Оцените эмпирически или теоретически эффективность такой процедуры нейтрализации ошибок. Разумным критерием эффективности может служить вероятность правильной нейтрализации оп1ибок из множества „обычных" ошибок программиста. 7.4.29.
При расщеплении грамматики грвмматики-компоненты можно анализировать по-разному. Исследуйте методы объединения различных типов анализаторов для грамматик-компонент. В частности, можно ли разбирать одну компоненту снизу вверх, а другую сверху вниз! Упражнения ио программировании 7И.39. Напишите программу, строящую по ЗЬК(1).грамматике множество ИСК(1)-таблиц. 7.4.31. Напишите программу, которая в множестве СК(1)-таб. лип находит все недостижимые элементы ошибки. 7.4.32. Напишите программу, строящую по САЕК(1).грамматике САЕК(!)-анализа1ор. 7.4.33.
Построй!е 5!.К(1)-анализатор с нейтрализацией ошибок для одной из грамматик, приведенных в приложении к ток!у 1. !16 Замечания по литературе Простые !я(А) гркыкктккн к ЬАЬйй)-гркыыктккк впервые кктчаки*ь де Реиербк П969, 19711. Пм же презтожек ыегед кестрбеиея дка грккыагккк кккокаческага мкажсстзк ! Ц(9).сктгаккд к кскикькокаккк кегккепбчек Зтя разрежеккк кечдкогккккостеа крк разборе. Прием расжепкенк» граымкт «к ПРКЫЕККГЕМ.ЕЕ К Ьй-АКККЭЗКТЕРКЧ ККЕРКЫЕ ПРКЫЕККК КОРЕНЬ К !19691 Упр. 7 !.1 гакмстюэгко 7 Эрка !19681 Пропедура кезтргккзшке ежкбок, епкггькге е гкр 7,4.26, кредкежекк Деапкусаы !1979!. Уер.7,4.26 взкго .т ргбо ы А а к У. ьыккк 11972 г).
7.5. АНАЛИЗИРУЮЩИЕ АН7ОМАТЫ Вместо того чтобы смотреть иа ЕК-анализатор иак на программ) с СК-таблице!!и в качестве данных, мы будем считать в этом разделе, что СК-таблицы управляют анализатором. Такой взгляд иа СК-разбор позволяет разработать другой подход к задаче упрощения СК-анализаторов. Основная иден этого раздела заключаетс» в том, что если 1.К-таблицы размещаются в управляющем устройстве анализатора, то каждую таблицу чажно рассматривать как состояние автомата, реализующего СК-алгоритм разбора.
Такой автомат можно рассматривать кан использующий магазин конечный автомат с „побочным эффектом". Методом, аналогичным алгоритму 2.2, можно минимизировать число состояний этого автомата. 7,5.1. Каноничяскмй анализирующий автомат В СК-алгоритме разбора решение о переносе нли свертке есть результат просмотра й следуюпгих входных символов н обращения к управляющей таблвце, которой служит таблица, распо.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
