![]() |
|
Главная Промышленная автоматика. 5.1.10. Покажите, что G = (N, 2, Р, 5) является ЬЬ(1)-грамма-тикой тогда и только тогда, когда для каждого множества Л-правил Л - «11 «21 ... I о;„ (1) FIRST?(a/)nFIRST?(a,)-0 для (2) если а,- Ф* е, то FlRST?(ay) П ЕОЬЬОШ?(Л) = 0 для 1 <; < п, 1ф] (обратите внимание, что е может выводиться не более чем из одной цепочки а,-). **5.1.П. Докажите неразрешимость проблемы: существует ли такое число k, что КС-грамматика G является ЬЬ(й)-граммати-кон? (В противоположность этому, если произвольное число к фиксировано, узнать, является ли G ЬЬ()-грамматикой для этого определенного значения к, можно.) *5.1Л2. Докажите неразрешимость проблемы: порождает ли КС-грамматика G LL-язык? *5.1.13. ЬЬ(/г)-грамматику часто определяют так. Пусть G = = (N, S, Р, 5) -КС-грамматика. Если S=*wAx для некоторых х2* и Л N, то для каждой цепочки г/2** существует не более одного такого правила Л-j-ct, что г/FlRST(ax). Покажите, что это определение эквивалентно определению в разд. 5.1.1. 5.1.14. Дополните доказательство теоремы 5.4. 5.1.15. Докажите лемму 5.1. 5.1.16. Докажите теорему 5.8. " **5.1Л7. Покажите, что если L является ЕЕ(/г)-языком, то он определяется ЕЕ(й)-грамматикой в нормальной форме Хомского. 5.1.18. Покажите, что ЕЕ(0)-язык содержит не более одной цепочки. 5.1.19, Покажите, что грамматика G с правилами S-> aaSbb \а\е является ЬЬ(2)-грамматикой. Найдите эквивалентную ей ЕЕ(1)-грамматику. **5.1.20. Покажите, что {a"Ob"\n0}\j\a"W"\nO} не LL-язык. Упражнения 5.1.21-5.1.24 будут решены в гл.8. Возможно, читатель захочет сделать их сейчас. **5.1.21. Докажите разрешимость проблемы: для двух LL()-трамматик Gj и G выяснить, верно ли, что L{G) === L{G. **5.1.22. Покажите, что для каждого кО существуют LL(fe-l-1)-языки, которые не являются ЕЕ(й)-языками. На шаге (2) к этим множествам добавить нечего. Например, так как есть правило 5-> Л5 и о{А, А) содержит \е\, то на шаге (26) надо добавить к o{S, А) множество L - {}фРШ5ТД5) {е, а, Ь\. Но 0(5, А) уже содержит множество {е, а, Ь\, так как его содержит Oq{S, А). Таким образом, о [А) = \{е, а, Ь}} и о(5)-{{е}). Чтобы проверить, что G - ЬЬ(1)-грамматика, нужно убедиться в том, что (FlRSTi(5)©i{e))n(FlRSTi(e)©i{e})=--0. (Это делается для двух 5-правнл и единственного элемента {е\ множества а(5, 5).) Так как FIRST,(AS) = FIRST,(A) FlRST,(S) {а, b] и FIRSTi(e) = {e), то действительно \а, Ь}П{е)-0. Для двух А-правил нужно показать, что (FIRST,(aA){е, а, Ь}) п (FIRST,(b) ф, {е, а, Ь}) = 0 Это сводится к проверке равенства {а)п{Ь} = 0, которое, очевидно, верно. Итак, G -это ЬЬ(1)-грамматика. □ УПРАЖНЕНИЯ 5ЛЛ. Покажите, что если грамматика G леворекурсивна, то она не LL-грамматика. 5Л.2. Покажите, что если грамматика G содержит два правила Л-аа\ф, где ар, то она не может быть ЬЬ(1)-грамма-тикой. 5Л.З. Покажите, что каждая LL-грамматика однозначна, 5Л.4. Покажите, что каждая грамматика, удовлетворяющая условию (5ЛЛ), является ЕЕ(й)-грамматикой. 5Л.5. Покажите, что грамматика с правилами S-aAaB\bAbB А~а\аЬ В->аВ\а является ЕЕ(3)-грамматикой, но не ЕЕ(2)-грамматикой. 5Л.6. Постройте ЕЕ(3)-таблицы для грамматики из упр. 5Л.5. 5Л.7. Постройте детерминированный левый анализатор для грамматики из примера 5.17. 5Л.8. Дайте алгоритм вычисления РОЬЬОШ?(Л) для нетерминала Л. *5.1.9. Покажите, что каждое регулярное множество порождается ЬЬ(1)-грамматнкой. ![]() Рис. 5.7. Разбор по левому участку. слева направо, но делающего разбор по левому участку. Содержательно грамматика G=(N, 2, Р,5) является ГС(й)-граммати-кой, если, зная левый вывод 5=>1о)Лб, можно однозначно определить, что к Л должно применяться правило Л-Ху...Хр, когда уже известна часть входной цепочки, выведенная из Ху (символ Ху называется левым участком правила Л--Ху-.-Х), и следующие k входных символов. В формальном определении, если Х, -терминал, можно посмотреть только на следующие k-1 символов. Это ограничение налагается ради простоты формулировки одной интересной теоремы, приведенной в упр. 5.1.33-На рис. 5.7 отражено, что правило Л-уХу ... Х распознается по цепочке wx и первым k символам (или k - 1 символам, если X € 2) цепочки у. Заметим, что если бы грамматика G была 1д)-грахМматикой, то можно было бы распознать это правило быстрее", а именно сразу после того, как прочитаны w и FlRSTft(xy). В определении ГС(й)-грамматики будут участвовать выводы следующего типа: Определение. Пусть G - КС-грамматика. Будем писать S:=*icwA6, если 5=>;*ьгЛб и нетерминал Л пе является левым участком того правила, благодаря которому он в ходе этого вывода оказался в левовыводимой цепочке wA6. Например, для грамматики G неверно, что £"= + 7, так как Е появляется в Е-\-Т в качестве левого участка правила Е~-Е-\-Т. С другой стороны, верно, что Яфй + Г, так как Г не является левым участком правила Е Е-\-Т, благодаря которому символ Т в ходе вывода ЕЕд + Т оказался в цепочке а-\-Т. Определение. КС-грамматика C = (N, 2, Р, S) называется ЬС(/г)-грамматикой, если она удовлетворяет таким условиям: Допустим, что S=%wAb. Тогда для каждой цепочки и 2** и вывода Л =>* 5у существует не более одного такого правила В-* а, что (1) (а) если а-Ср, где CgN, то w € FIRST(Py6), (б) если, кроме того, С = А, то wFlRST(6), (2) если а начинается терминалом, то w FIRST.(a76). Условие (1а) гарантирует, что правило В -> Ср, которое нужно применить, определяется однозначно, как только мы увидим терминальную цепочку выведенную из С (левого участка), и цепочку FIRST(Py6) (аванцепочку). Условие (16) гарантирует, что если нетерминал Л леворекурсивный (в LC-грамматике это возможно), то после того, как обнаружено его вхождение, можно сказать, является ли оно левым участком правила ВАу или это вхождение Л в лево-выводимую цепочку wAb. Условие (2) говорит о том, что FIRST.(ay6) однозначно определяет правило В-а, которое при разборе по левому участку нужно применить сразу после того, как в поле зрения оказалась цепочка wB (если цепочка а пуста или начинается терминальным символом). Для каждой ЬС(й)-грамматики G можно построить детерминированный алгоритм разбора по левому участку, который анализирует входную цепочку, распознавая левый участок применяемого правила восходящим методом, а остальную часть этого правила -сверху вниз. **5.1.23. Покажите, что каждый ЬЬ(/г)-язык определяется LL(fe+1)-грамматикой без е-нравил. **5Л.24. Покажите, что каждый ЬЬ(й)-язык определяется LL(ft-f-1)-грамматикой в нормальной форме Грейбах. *5.1.25. Допустим, что Л-~н-арау-такие два правила грамматики G, что из а не выводится а р и у начинаются разными символами. Покажите, что G ие ГГ(1)-грамматика. При каких условиях замена этих правил правилами Л->аЛ Л->Р17 преобразует грамматику G в эквивалентную ГГ(1)-грамматику? 5.1.26. Покажите, что если G = (N, 2, Р, 5) является LL(fe)-грамматикой, то для каждого ЛN грамматика G, получающаяся из грамматики (N, 2, Р, Л) удалением всех бесполезных правил и символов, также является ГЬ(/г)-грамматикой. Существует класс грамматик, называемых LC-грамматиками, которые, подобно LL-грамматикам, можно анализировать с помощью детерминированного МП-преобразователя, читающего вход Теперь покажем в общих чертах, как по ЬС(1)-грамматике строить соответствующий анализатор. Пусть G (N, 2, Я, S)~ ЬС(1)-грамматика. Построим по ней такой анализатор по левому участку Л, что х {Л)= {{х, n)\xL{G) и п - разбор по левому участку цепочки х\. Анализатор Л использует входную ленту, магазин и выходную ленту так, как это делает й-предсказываю-щий анализатор. Множеством магазинных символов служит Г - N U 2 и (NxN)U{$). Вначале магазин содержит 5$ (причем 5 - верхний символ). Один нетерминальный или терминальный символ, расположенный наверху магазина, можно интерпретировать как очередную цель, которую нужно распознать. Если верхним символом магазина является пара нетерминалов вида [Л, В], то первую компоненту Л можно рассматривать как текущую цель, которую нужно распознать, а вторую компоненту В - как левый участок, только что распознанный. Для удобства построим таблицу Г, управляюиую разбором по левому участку. Она отображает множество Гх (2 U {е\) в (Г*х (Я и {е})) и {выброс, допуск, ошибка}. Эта управляющая таблица похожа на таблицу, управляющую 1-предсказывающим алгоритмом разбора для ЕЬ(1)-грамматик. Конфигурацией анализатора Л будет тройка [w, Ха, п), где w-необработанная часть входной цепочки, Ха - содержимое магазина (ХГ-верхний символ) и л-часть выходной цепочки, образовавшаяся к данному моменту. Если 7 (X, а) (р, г), где X N U (Nx N), то будем писать (aw, Ха, я) 1- (aw, pa, ni). Если Т {а, а) = выброс, то пишем {aw,aa, n)\-{w, а, п). Будем говорить, что п - разбор (по левому участку) цепочки х, если (х, 5$, е) [--* (е, $, л). Пусть G = (N, 2, Р, S) - ЬС(1)-грамматика. Таблица Т строится по G следующим образом: (1) Допустим, что В-уа - правило из Я с номером г. (а) Если аСр, где С - нетерминал, то Т{[А,С],а) = (Р[Л, В], г) для всех Л и а FIRSTi(Py6), таких, что 5=?>]сЛб и Л=>*5у. Здесь Л распознает левые участки снизу вверх. Заметим, что Л - либо 5, либо левый участок некоторого правила, так что в какой-то момент разбора Л будет целью. (б) Если а не начинается нетерминалом, то Т{Л,а) (а [Л, В], i) для всех ЛН и а FIRSTi(ay6), таких, что S=%wA6 и Л=?>*5у. (2) Т{[А, А],а) = {е, е) для всех Л N и FIRSTi(6), таких, что 5=»*саЛб. (3) 7 (а, (З) = выброс для всех aS. (4) Т(%, е)-допуск. (5) В остальных случаях (Х, а) = ошибка. Пример 5.20. Рассмотрим грамматику G с правилами (1) 5 -5 + Л (2) 5->Л (3) А-АВ (4) А-В (5) й-><5> (6) В--а G является ЕС(1)-грамматикой, причем это фактически грамматика G„, слегка измененная. Таблица, управляющая разбором по левому участку для грамматики G, приведена на рис. 5.8. входной символ
Рис. 5.8. Таблица, управляющая разбором по левому участку для грамматики G. Анализатор, управляемый этой таблицей, для входной цепочки <.аау проделает такую последовательность тактов: (<а*а>, 5$, е)Ь-<5>[5,5]S, 5) h-(«*«>. 5>[5, 5]$, 5) И(а*>, a[S, B]>[S, В]$, 56) 1-(*а>, [5, 5]>[S, 5]$, 56) h-(*«>. [5. Л]>[5, В]$, 564) 1-(*а>, *й[5, Л]>[5, 5]$, 5643) 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 [66] 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 0.0047 |