Теория синтаксического анализа, перевода и компиляции - Том 1 (943928), страница 82
Текст из файла (страница 82)
Покажите, что если грамматика 6 леворекурсивна, то она не ЕЕ-грамматика. 5.!.2. Покажите, что если грамматика 6 содержит два правила А — аа)а(), где аФ~, то она не может быть 1.1.(1)-грамматикой. 5.1.3. Покажите, что каждая ЕЕ-грамматика однозначна.
5.1.4. Покажите, что каждая грамматика, удовлетворяющая условию (5.1.1), является 11.(й)-грамматикой. 5.!.5. Покажите, что грамматика с правилами 5 — аАаВ) ЬАЬВ А-- а)аЬ В вЂ” аВ (а является ЕЕ(3)-грамматикой, но не Щ2)-грамматикой. 5.1.8. Постройте ЕЕ(3)-таблицы для грамматики из упр. 5.1.5. 5.1.7. Постройте детерминированный левый анализатор для грамматики из примера 5.!7.
5.1.8. Дайте алгоритм вычисления ГО).).О%ДА) для петер минала А. *5.1.9. Покажите, что каждое регулярное множество порождается Щ!)-грамматикой. 400 уп РАЖ н е н и я 5.1.10. Покажите, что 6 =- (М, Х, Р, 5) является 1Л.(1)-грамматикой тогда и только тогда, когда для каждого множества А- правил А а,)а,)... (а„ (1) Р!И5Т!'(а1)ПР1ц5Т!0(а ) = Я для 1'Ф-/, (2) если а1: —..>* е, то НК5Т,(а1) П РО(10%»а(А) = !а для 1 ~/ ~~ ~п, ! ~/ (обратите внимание, что е может выводиться не более ЧЕМ ИЗ ОДНОЙ ЦЕПОЧКИ СС1). **5,1.11. Докажите неразрешимость проблемы: существует ли такое число й, что КС-грамматика 6 является ЕЕ(й)-грамматикой? (В противоположность этому, если произвольное число й фиксировано, узнать, является ли 6 ЕЕ(й)-грамматикой для этого определенного значения л, можно.) "5.1.12.
Докажите неразрешимость проблемы: порождает лн КС-грамматика 6 1.).-язык? "5.1.13. ЕЕ(й)-грамматику часто определяют так. Пусть С =- =(Х, Х, Р„5) — КС-грамматика. Если 5~" и!Ах для некоторых и1,хбХ' и АЕЬ), то для каждой цепочки у~Х*» существует не более одного такого правила А- а, что уЕР1Р5Т (ах). Покажите, что это определение эквивалентно определению в равд. 5.1.1. 5.1.14. Дополните доказательство теоремы 5.4. 5.1.15. Докажите лемму 5.1. 5.1.!8. Докажите теорему 5.8.
»»5.!.17. Покажите, что если /. является 1.1(л)-языком, то он определяется Щй)-грамматикой в нормальной форме Хомского. 5.1.18. Покажите, что 1.1.(0)-язык содержит нс более одной цепочки. 5.1.19. Покажите, что грамматика С с правилами 5— аа5ЬЬ) а(е является 1.1.(2)-грамматикой. Найдите эквивалентную ей Щ1)-грамматику **5.1.20. Покажите, что (а"ОЬ" (п~0)0(а"1Ь'")л 0) не 11- язык, Упражнения 5.1.21 — 5.1.24 будут решены в гл. 8. Возможно, читатель захочет сделать их сейчас.
*~5 1 2!. Докажите разрешнмость проблемы: для двух 1Л (й)- грамматик 6, и С„выяснить, верно ли, что В(61) =/(6,). ""5.1, ° 22. Покажите, что для каждого й ) 0 существуют 1.1-(11+!)-языки, которые не являются ЕЕ(й)-языками. 401 Гл. а. ОднопРОходныи синтаксический АнАлиз Вез ВозВРАТОВ УПРАЖНЕНИЯ **5.1.28, Покажите, что каждый 1.1.(!е)-язык определяется 1.1.(!с+ 1)-грамматикой без е-правил. ""5.1.24. Покажите, что каждый ББ(й)-язык определяется 1.1(я+1)-грамматикой в нормальной форме Грейбах. *5.1.25. Допустим, что Л вЂ” сх5(ау — такие два правила грамматики 6, что из а не выводится е, а 5 и у начинаются разными символами.
Покажите, что 6 пе 1.1.(!)-грамматика. При каких условиях замена этих правил правилами А — аЛ' А' Иг преобразует грамматику 6 в эквивалентную ББ(1)-грамматикур 5.1.26. Покажите, что если 6=(ч, Х, Р, В) является Щ!с)- грамматикой, то для каждого А ~Я грамматика 6А, получающаяся из грамматики ()ч(, Х, Р, А) удалением всех бесполезных правил и символов, также является Щ!с)-грамматикой. Существует класс грамматик, называемых БС-грамматиками, которые, подобно ББ-грамматикам, можно анализировать с помощью детерминированного ЯП-преобразователя, читающего вход Ркс. 5.7. Разбор по левому участку. слева направо, но делающего разбор по левому участку.
Содержательно грамматика 6 = ((ч, Х, Р, В) является 1.С(!е)-грамматикой, если, зная левый вывод Я=>", озА6, можно однозначно определить, что к А должно применяться правило А — Х,...Хр, когда уже известна часть входной цепочки, выведенная из Х, (символ Х, называется левым участком правила А — Х,...Х ), и следующие е входных символов. В формальном определении, если Х,— терминал, можно посмотреть только иа следующие й — 1 символов. Это ограничение налагается ради простоты фор. мулировки одной интересной теоремы, приведенной в упр.
5.1.55. На рис. 5.7 отражено, что правило А — Х, ... Х распознается по цепочке юх и первым Й символам (или Й вЂ” 1 сймволам, если 402 Х с Х) цепочки у. Заметим, что если бы грамматика 6 была (ць)-грамматикой, то можно было бы распознать это правило быстрее", а именно сразу после того, как прочитаны ю и Г1 ~БТА(ху). В определении 1С(й)-грамматики будут участвовать выводы следующего типа: Определение.
Пусть 6 — КС-грамматика. Будем писать В=.,>,",пзА6, если В=>,"юЛ6 и нетермииал А пе является левым участком того правила, благодаря которому он в ходе этого вывода оказался в левовыводимой цепочке юА6. Например, для грамматики 6, неверно, что Еь,",Е+Т, так как Е появляется в Е+Т в качестве левого участка правила Е- Е-1-7'. С другой стороны, верно, что Е=~;,а+Т, таккакТ не является левым участком правила Š— Е -!- Т, благодаря которому символ Т в ходе вывода Е=ФЕ+Т=За+Т оказался в цепочке и+Т.
Определение. КС-грамматика С=((ч', Х, Р, В) называется БС(й)-грамматикой, если она удовлетворяет таким условиям: Допустим, что Я=чз,*,соА6. Тогда для каждой цепочки иЕ Х*' и вывода А=>'Ву существует не более одного такого правила  — св, что (1) (а) если а = С(3, где С б .ч, то и С НГсЗТА(5уб), (б) если, кроме того, С.—.— А, то и( ГПАЗТА(6), (2) если а начинается терминалом, то и б НЙЯТ,(куб). Условие (1а) гарантирует, что правило  — С!), которое нужно применить, определяется однозначно, как только мы увидим терминальную цепочку ю, выведенную нз С (левого участка), и цепочку Г(КЗТ (Руб) (аванцепо|ку).
Условие (!б) гарантирует, что если нстерминал А леворекурсивиый (в 1.С-грамматике это возможно), то после того, как обнаружено его вхождение, можно сказать, является ли оно левым участком правила  — Ау или это вхождение А в лево- выводимую цспочку соА6. Условие (2) говорит о том, что ГПЮТА(ауб) однозначно определяет правило В- сс, которое при разборе по левому участку нужно применить сразу после того, как в поле зрения оказалась цепочка пзВ (если цепочка а пуста или начинается терминальным символом). Для каждой БС(й)-грамматики 6 можно построить детерминированный алгоритм разбора по левому участку, который анап"зирует входную цепочку, распознавая левый участок приме""емого правила восходящим методом, а остальную часть этого "Разила †свер вниз. 403 ГЛ. 6, ОДНОПРОХОДНЫЙ СИНТАКСИЧЕСКИЙ АНАЛИЗ ВЕЗ ВОЗВРАТОВ УПРАЖНЕНИЯ Теперь покажем в общих чертах, как по ЕС(1)-грамматике строить соответствующий анализатор.
Пусть 6= — (Ря, Х, Р, 5)— 1.С(1)-грамматика. Построим по ней такой анализатор по левому участку А, что т(А)=((х, л))хай(6) и л — разбор по левому участку цепочки х). Анализатор А использует входнузо ленту, магазин и выходную ленту так, как это делает й-предсказывающий анализатор.
Множеством магазинных символов служит Г=)А)() Х О (ТЧ х'5)() (5). Вначале магазин содержит 53 (причем 5 — верхний символ). Один петерминальный или терминальный символ, расположенный наверху магазина, можно интерпретировать как очередную цель, которую нужно распознать. Если верхним символом магазина является пара нетерминалов вида [Л, В], то первую компоненту А можно рассматривать как текущую цель, которую нужно распознать, а вторую компоненту  — как левый участок, только что распознанный. Для удобства построим таблицу Т, управляющую разбором по левому уиаепску.
Она отображает множество Г х (Х 0 (е)) в (Г'х(Р() (е)))() (выброс, допуск, ошибка). Эта управляющая таблица похожа на таблицу, управляющую 1-предсказывающим алгоритмом разбора для Щ1)-грамматик. Конфигурацией анализатора А будет тройка (се, Ха, л), где си — необработанная часть входной цепочки, Ха — содержимое магазина (Х ~ à — верхний символ) и л — часть выходной цепочки, образовавшаяся к данному моменту.
Если Т(Х, а) =(16, 1), где ХЕ ЕАс(1(14х6(), то будем писать (аш, Хсс, л) ) — (аси, ()сс, лс). Если Т (а, а) = выброс, то пишем (аси,аа, л)) — (пз, а, л). Будем говорить, что л — разбор (по левому участку) цепочки х, если (х, 55, е) ( — *(е, $, л). Пусть 6=(Р), Х, Р, 5) — 1.С(1)-грамматика. Таблица Т строится по 6 следующим образом: (1) Допустим, что  — а — правило из Р с номером 1. (а) Если а=С5, где С вЂ” нетерминал, то Т([А, С], а) = (() [А, В], 1) для всех А Е14 и аЕ НКЗТ,((126), таких, что 5=о'„сеА6 и А=>*ВТ.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
