Главная Промышленная автоматика.

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,Д],6

<S>D?,el,5

<S>lB,B\,b

[S,A]A

*В[/\,А],Ъ

[A A],4

в,е-

a

выброс

<

выброс

>

выброс

выброс

В ыброс

ДОПУСК

Рис. 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.0035