Теория синтаксического анализа, перевода и компиляции - Том 1 (943928), страница 92
Текст из файла (страница 92)
Так как характеристика начальной конфигурации равна 2п, то количество всех С-конфигураций не превосходит 2п. Теперь достаточно показать, что найдется такая константа с, что между двумя последовательными С-конфигурациями анали'атор может делать нс более с шагов. Для этого рассмотрим ГЛ.
Б. ОДНОПРОХОДНЫЙ СИНТАКСИЧЕСКИЙ АНАЛИЗ ВЕЗ ВОЗВРАТОВ упРАжнения Д)л)П-автомат, работающий с магазином так же„как 1.К(е)- анализатор. Из доказательства теоремы 2.22. извлечем такую константу с, что если ДМП-автомат за с шагов не сделает переноса входного символа и не уменьшит обьем магазина, то он зациклнтся. Следовательно, то же произойдет и с анализатором. Но, как мы заметили раньше, если обработанную часть входной цепочки нельзя продолжить до цепочки, принадлежащей 1.(б), анализатор сигнализирует об ошибке. Поэтому зациклп. ванне анализатора означало бы, что найдется цепочка из! (6), имеющая сколь угодно длинные правые выводы. Это противоречит однозначности 1.К(е)-грамматики, Таким образом можно за. ключить, что анализатор не зацикливается и нужная константа с существует. С) $.2.6.
Реапнзвцня Щй]- н 1.ЩЦ-анализаторов На первый взгляд кажется, что при реализации 11.(я)- и 1К(й)-анализаторов придется помещать в магазин большие таблицы. На самом деле этого можно избежать следующим образом: (!) Поместить в память по одному экземпляру каждой таблицы, а в магазине заменить сами таблицы указателями на пх место в памяти. (2) Так как в 1.1(я)- и ).К(е)-таблицах есть ссылки на другие таблицы, вместо имен таблиц люжно использовать указатели. Заметим также, что наличие в л1агазине символов грамматики излишне и на практике их можно туда не записывать.
УПРАЖНЕНИЯ 5.2.!. Определите, какие из следующих грамматик являются 1.К(! )-грамматиками: (а) 6„ (б) 5 — АВ, А ОА1!е, В- !В!1, (в) 5- 051(Л, Л !А!1, (г) 5- 5+А(А, А — (5))а(5)!а. Последняя из этих грамматик порождает скобочные выражениа с операцией + и идентификаторами, обозначенными символом а, возможно с индексом. 5.2.2. Какие из грамматик упр.
5.2.! являются ЬК(0)-граль матиками? 5.2.3. Постройте системы 1К(1)-таблиц для тех грамматик из упр. 5.2.1, которые являются ).К(1)-грамматиками. Не за- будьте сначала пополнить эти грамматики. 5.2.4. Напишите последовательность шагов, которую сделает 1,К(1)-анализатор для грамматики 6, прн входе (а+а) В (а+ (а+ а) Р а). *5.2.5.
Докажите или опровергните каждое из следующих утверждений: (а) Каждая праволпнейиая грамматика является 1.1.-грамматикой. (б) Каждая праволинейная грамматика является 1.Ксграмматнкой. (в) Каждая регулярная грамматика является !.(.-грамматикой. (г) Каждая регулярная грамматика является 1.К-грамматикой. (д) Каждое регулярное множество определяется 1.1(1)-грамматикой. (е) Каждое регулярное множество определяется 1.К(1)-грамматикой. (ж) Каждое регулярное множество определяется 1.К(0)-грамматикой.
5.2.6. Покажите, что каждая ЬК.грал!матика однозначная. "5 27. Для б-- (!з, г', Р, 5) определим бе=-(й), Х, Ря, 5), где Ра — это множество Р, правые части правил которого записаны в обРатном поРЯдке, т. е. Ря=(Л аа!Л слЕР). ПРиведите пример, показывающий, что бя не обязательно будет 1.К(й)- грамматикой, даже если б такова. *5.2.8.
Пусть 6=-(!х, Х, Р, 5) — произвольная КС-грамматика. Для и Е Е*л и номера правила ! определим множество КАО(л, и) = !а(!и !5=О„'аАш =>, сл()ш, где и = К!КЗТА(ил) н А — 5 — 1-е правило). Покажите, что К)л(1, и) — регулярное множество. 5.2.9. Постройте новый алгоритм разбора для СК(е)-грамматик, который для всех 1 и и следит за состояниями конечного автомата, распознающего глл' (1, и). "5.2.10.
Покажите, что б является 1.К(Ф)-грамматикой тогда и только тогда, когда для всех а, р, и и с соотношения ас КОЕ(1, и) и слр ч КАО(!', Р) влекут за собой 5 = — е и ! =1. *5.2.11. Покажите, что б является 1К(й)-грамматикой тогда и только тогда, когда она однозначна и для всех ш, х„у н г из г.' выполнение четырех условий 5=О "ЕРАу, А=>'к, 5==;>' шхг н НКЗТА(у)=-г)КВТА(г) влечет за собой 5~'шАг. **5.2,12. Докажите неразрешимость проблемы: является ли КС- грамматика 1.К(я)-грамматикой для какого-нибудь е? **5 2.13.
Докажите неразрешимость проблемы: является ли 1.К (й)-грагаллатика 1Л.-грамматикой? А, Ало. Дж, ульилы, н 1 449 ГЛ, Б. ОДНОПРОХОДНЫЙ СИНТАКСИЧЕСКИЙ АНАЛИЗ БЕЗ ВОЗВРАТОВ УПРАЖНЕНИЯ 5.2.!4. Докажите разрешимость проблемы: является ли ЕК(й). грамматика 11(н)-гралгматикой для того же значения й. *5.2.15. Покажите, что каждый КС-язык, не содержащий пустой цепочки е, порождается обратимой КС-грамматикой без е-правил.
*5.2.16, Пусть 6=((Л(, Е, Р, 5) — КС-грамматика и иг=а,...агг цепочка из Е". Допустим, что, применяя к б алгоритм Зрли, мы обнаружнм в списке уг ситуацию [А — а р, !! (в смысле алгоритма Эрли). Покажите, что существует такой вывод Я ==;>*„ух, что ситуация [А — а (5, и1 (в смысле 1К(й)-алгоритма) допустима для у, причем и =Г1КВТ»(х) и у=~'аг...аг *5.2.17. Докажите утверждение, обратное утверждению в упр. 5.2.16, *5.2.18, С помощью упр. 5.2,16 покажите, что если 6— 1К (й)-грамматика, то алгоритм Эрли, заглядывающий на й символов вперед (см. упр. 4,2.17), тратит линейное время и емкость памяти. 5.2.19, Пусть Х Е Х В Е, Покажите, что ЕГГ» (Ха) = ЕГГ» (Х) Я» Г1КЕТ» (а).
5.2.20. Используя упр. 5,2.!9, дайте эффективный алгоритм вычисления ЕГГ(гг) для любой цепочки сг. 5.2.21. Доведите до формальных деталей доказательство того, что в случаях 1 и 3 теоремы 5.9 нарушается 1 К (й)-условие. 5.2.22. Дополните доказательство теоремы 5.1!. 5.2.23. Докажите корректность алгоритма 5.!О. 5,2.24. Докажите корректность алгоритма 5.! 1, обосновав каждое нз замечаний, следующих за описанием этого алгоритма. В гл. 8 будут доказаны разные теоремы, касающиеся 1К- грамматик.
Читатель, возможно, захочет уже сейчас испытать себя на некоторых из них (упр. 5.2.25 — 5.2.28). **5.2.25. Докажите, что каждая (.1 (й)-грамматика является ЕК()г)-грамлгатикой. »*5.2.26. докажите, что каждый детерминированный КС-язык определяется !.К(!)-гралгматггкой. *5.2.27. Покажите, что существуют (детерминированно) прз воаналнзируемые грамматики, которые не являются 1К-грамма тиками. *5.2.28.
Г!окажите, что существуют 1К-языки„которые нс являются Е1 языками. **5.2.29. Докажите, что каждая 1.С(й)-грамматика является ЕК(й)-грамматикой. **5.2.30. Каково максимальное число множеств допустимых ситуаций 1К(й)-грамлгатики, рассматриваемое как функция от числа символов грамматики, количества правил и длины самого длинного правила? *5.2.31.
Назовем ЕК(й)-ситуаггию существенной. если точка находится в пей не наг левом конце (т. е. она появляется иа шаге (2а) алгоритма 5.8), Покажите, что если отвлечься от множества ситуаций, соответствующего е и от „сверток" пустой цепочки, то в определении ЕК(!г)-таблиггы, соответствующей множеству ситуаций, можно ограничиться существенными ситуациями и при этом таблица не изменится, *5.2.32. Покажите, что действием 1.К(1)-таблицы для символа а будет перенос тогда и только тогда, когда в некоторой ситуации из множества, по которому построена таблица, а находится непосредственно справа от точки. Упражнения на ггроераммироеание 5.2.33. Напишите программу, проверяющую, является ли произвольная грамматика ЕК(!)-гралгматнкой.
Оцените время и емкость памяти, требуемые Вашей программой, как функции от объема входной грамматики. 5.2,34. Напишите программу, использующую для разбора входных цепочек 1.К(1)-таблицу, такую, как на рис. 5.9. 5.2.35. Напишите программу, которая строит ЬК(1)-аналггзатор для 1К(!)-грамлгатики. 5.2.36, Постройте (.К(1)-анализатор для какой-нибудь небольшой грамматики. *5,2.37. Напишите программу, проверяющую, образует ли произвольная система ЕК(1)-таблиц корректный анализатор для данной КС-грамматики. Допустим, что 1.К(1).анализатор находится в конфигурации (аТ, ах, и) и таблица Т ассоциирует с символом а операцию ошибка. Как и при Ы.-разборе, нам хотелось бы в этот момент объявить об ошибке и перейти к процедуре исправления ошибок, которая должна модифицировать входную цепочку Итиля содержимое магазина так, чтобы можно было продолжить ЕК(1)- анализ.
Как и в случае 1.(.-анализа, можно устранить входной символ, изменить его или вставить другой входной символ в зависимости от того, какая стратегия кажется наиболее подх~дящей в рассматриваемой ситуации. г5' 351 ГЛ. б. ОДНОПРОХОДНЫЙ СИНТАКСИЧЕСКИЙ АНАЛИЗ БЕЗ ВОЗВРАТОВ б,з граммАтики пРедшестВОВАния Лейниус [1970~ описывает более изощренную стратегию, в которой участвуют [.[[(1)-таблнцы, хранящиеся в магазине. 5.2.38. Напишите [.П(1)-граьгматику для какого-нибудь про стого языка, Разработайте процедуру исправления опшбок, которую можно было бы использовать вместе с 1гс(!)-анализатором для этой грамматики.
Оцените эффективность Вашей про. цедуры. Замечания по литературе 1.[((1г)-грамматики впервые били определены Кнутом [1965!. Метод построения 1[(-анализатора, описанный в этом разделе, дает, к сожалению, очень большие по обьему анализаторы для грамматик, представлшощих практическкй интерес. В гл. 7 мы изучим технику, предложеннуюДе Рсмером [1969[, Кореиьяком [1969! и Ахо и Ульмаиом [1971), которая часто позволяет строить Ей-анализаторы меньшего обьсма. Идея [.[[(й[-грамматики была распростраисиа Уолтерсом [1970[ па кон. текстио-зависимые грамматики ').
Ответы к упр. 5.2.8 — 5.2.10 можно найти в книге Хопкрофта и Ульмаиа [1969[. Упр. 5.2.12 взято из работы Кнута !1965! '!. 5З. ГРАММАТИКИ ПРЕДШЕСТВОВАНИ[[ Среди грамматик, анализируемых алгоритмами типа „перенос— свертка", можно выделять различные подклассы [.К(й)-грамматик. В этом разделе мы точно определим алгоритм разбора типа яперенос — свертка" и рассмотрим класс грамматик пред- шествования, которые анализируются легко реализуемым алгоритмом этого типа.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
