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

л() < "(0 < - рассматривается аналогично с привлечением множества значений перевода Tj. Таким образом, Bj ни для какого ii не покрывает {а,}. Если Bj покрывает содержащее то Bj, разумеется, покрывает {а). Следовательно, по лемме 3.11 Bi покрывает некоторое множество, содержащее а, н, значит, покрывает {aJ. □

Лемма 3.13. Если А покрывает "L (ft 4), то существует такое правило А~В ... В, Ci ... С„ и такой индекс г, 1/т, что Bi покрывает

Доказательство. Рассмотрим случай, когда k четно. Случай нечетного ft рассматривается аналогично и оставляется в качестве упражнения. Пусть Л -... В,, С -пра-

вило, удовлетворяющее лемме 3.11. Так как по предположению mk-1, то некоторый нетерминал В; должен покрывать два элемента множества 2, скажем {а, aJ, где гфз. Следовательно, В{ покрывает {а} и {а}, а если at находится между и а, то по лемме 3.12 Bi покрывает {а\ и By нн для какого 1фс не покрывает {а\.

Рассмотрим множество значений перевода Г. Если нетерминал Bi покрывает {й/а} и {ak/ + i], то он покрывает {а} для всех (22 и никакой другой нетерминал By не покрывает никакого {а}. В силу леммы 3.11 Bi покрывает 2. Далее, если В; покрывает {а„} и где mk/2 и п > ft/2, то, исследуя область определения, убеждаемся, что Bi покрывает {а/з} и {Uk/ + i}.

Таким образом, если одно из чисел г и s не превосходит ft/2, а другое превосходит ft/2, то нужный результат получается сразу.

Остались случаи г ft/2, sft/2 и г > ft/2, s > ft/2. Но в множестве значений для любых различных г и s, не превосходящих ft/2, между а и а найдется символ й, для которого t > ft/2. Аналогично, если г > ft/2 и s > ft/2, то между ними найдется символ at, для которого В любом случае лемма до-

казана. □

Лемма 3.14. Tf,etc~k-i для ft>4.

Доказательство. Ясно, что Tf. Остается показать, что вопреки предположению для не существует СУ-схемы Т порядка ft - 1. Так как S, разумеется, покрывает 2, то по лемме 3.13 в N найдется такая последовательность нетерминалов Лц, Ai, Л#м, что Ло = 3 н для каждого 0t<;#N существует правило Л/- сС/Л(- 1 ,р, у/Л-б,-, причем Л/ покрывает 2;. Так как все Л,- не могут быть различными, найдутся такие i </, что Л/ -Лу. По лемме 3.6 можно иайти такие

W „ что для всех рО

(5, S)=*iwAiW, wAiW,)

=*{wwAiWw, W:,wAiWWi)

=*{wwAiWWj, wwPAiWw)

По лемме 3.9(1) не все сс,-, Э,-, Y/ и 6,- пустые, а по лемме 3.9(2) не все w„ w,, w, и w, пустые.

Для каждого й € 2д цепочки ww и ww должны иметь одно и то же число вхождений а, потому что иначе в переводе т(Т) была бы пара, которой нет в Т. Так как Л,- покрывает 2, то если бы w,„ w, и KJg содержали какой-нибудь символ, кроме а или йд, можно было бы подобрать так, чтобы получить пару, не принадлежащую Т. Следовательно, в или входит а или «д. Так как Л- покрывает 2, можно выбрать w так, чтобы получилась пара, не входящая в Гд. Итак, Т не существует

Теорема 3.8. За исключением k = 2, для любого ftI класс Sjt собственно включает

Доказательство. Случай ft~I доказан в лемме 3,5. Остальные случаи охватываются леммой 3.14. □

Интересное практическое следствие теоремы 3.8 состоит в том, что, хотя кажется заманчивым сконструировать такую систему построения компиляторов, чтобы входная грамматика была в нормальной форме Хомского, эта система не в состоянии выполнить любую синтаксически управляемую трансляцию, а более общая система смогла бы это сделать. Однако похоже, что на практике СУ-переводы в худшем случае будут принадлежать классу (и, следовательно, са).

УПРАЖНЕНИЯ

*3.2.1. Пусть Т-СУ-перевод. Покажите, что существует такая константа с, что для каждой цепочки х из области его определения найдется такая цепочка у, что [х, у)Т п \у\с (\х\- I).

*3.2.2. (а) Покажите, что если Tj -регулярный перевод и HfC " Р"" ™ Ю1(л:,/)€Г и (у,г)Т, для

некоторой цепочки }-СУ-перевод).

сцвя* сто эта операция над переводами, называемая композицией, запи-налп? операндами в обратном порядке, так что в нашем определении как ° писать То Т, а не ТоТ. Мы не изменим нашей записи, так "на выглядит более естественной.



(б) Покажите, что если перевод простой, то перевод о тоже простой.

3.2.3. (а) Покажите, что если СУ-перевод, то Т-тоже СУ-перевод.

(б) Покажите, что если перевод Т простой, то перевод Т" тоже простой.

*3.2.4. (а) Пусть - регулярный перевод, а -СУ-перевод. Покажите, что То7\-СУ-перевод.

(б) Покажите, что если перевод Т. простой, то перевод 3 1 тоже простой.

3.2.5. Найдите сильно характеризующие языки для СУ-переводов из

(а) примера 3.5,

(б) примера 3.7,

(в) примера 3.12.

3.2.6. Для СУ-перевода из упр. 3.2.5 найдите язык, характеризующий его, но не сильно.

3.2.7. Дополните доказательство леммы 3.4.

3.2.8. Дополните доказательство случая 2 в примере 3.17.

3.2.9. Покажите, что каждый простой СУ-перевод определяется простой СУ-схемой, ие содержащей бесполезных нетерминалов.

3.2.10. Пусть Tj -простой СУ-перевод, а -регулярный перевод. Всегда ли П Tg-простой СУ-неревод?

3.2.11. Докажите лемму 3.6.

3.2.12. Докажите лемму 3.9.

3.2.13. Постройте СУ-схему порядка k, определяющую Т/.

3.2.14. Пусть r-(N, 2, 2, S), где N = {5, Л, Б, С, D}, "St {а, Ь, с, d} и R состоит из правил

Л-аЛ, аЛ А-е, е В-ЬВ, ЬВ В->е, в С-усС, сС с-е, е D-ydD, dD D-t\ е

и одного из приведенных ниже. Найдите наименьший порядок перевода х{Т) для каждого из этих дополнительных правил:

(а) S -ЛВС, ABCD {b)SABCD, DBCA

(б) S-ABCD, BCDA (y)S~ABCD, BDAC

3 2.15- Покажите, что если Т определяется ДМП-преобразо-вателем, то Т сильно характеризуется детерминированным КС-языком.

3.2.16. Верно ли обращение упражнения 3.2.15?

3.2.17. Докажите следствия теорем 3.3 и 3.4.

Замечания по литературе

"Понятие характеризующего языка н результаты разд. 3.2.1 и 3.2.2 взяты из работы Ахо и Ульмана [I9G9 6J, а результаты разд. 3.2.3 -из работы Ахо и Ульмана [1969а].

3.3. ЛЕКСИЧЕСКИЙ АНАЛИЗ

Лексический анализ образует первый этап процесса компиляции. На этом этапе символы, составляющие исходную программу, считываются и группируются в отдельные лексические элементы, называемые лексемами. Лексический анализ важен для процесса компиляции по нескольким причинам. Наибольшее значение имеет, по-видимому, то, что замена в программе идентификаторов и констант лексемами делает представление программы удобнее для дальнейшей обработки. Далее, лексический анализ уменьшает длину программы, устраняя из исходного ее представления несущественные пробелы и комментарии. На следующих стадиях ком]шляции компилятор может несколько раз , просматривать внутреннее представление программы. Поэтому, . уменьшая с помощью лексического анализа длину этого пред- ставления, можно сократить общее время процесса компиляции. •

Во многих ситуациях выбор конструкций, которые будут выделяться как лексемы, довольно произволен. Например, если в языке разрешены комплексные константы вида

<комплексная константа> -5- (<вещественное>, <веществеиное»

то возможны две стратегии. Можно трактовать <вещественное> как лексический элемент и отложить распознавание конструкции «вещественное), <вещественное>) как комплексной константы до фазы синтаксического анализа. Другая стратегия состоит в том, чтобы с помощью более сложного лексического анализа-ора распознать эту конструкцию как комплексную константу на лексическом уровне и передать тип лексемы синтаксическому анализатору. Важно также отметить, что если в вычислительном центре изменяется принятое в нем множество терминальных символов, то это отражается лишь па лексическом анализе.

Большую часть того, что происходит в течение лексического анализа, можно моделировать с помощью конечных преобразователей, работающих последовательно или параллельно. Напри-



мер, лексический анализатор может состоять из ряда последовательно соединенных конечных преобразователен. Первый пре-образователь в этой цепи может устранять из исходной программы все несущественные пробелы, второй ликвидирует комментарии, третий ищет константы и т. д. Другая возможность-завести набор конечных преобразователей, каждый из которых ищет определенную лексическую конструкцию.

В этом разделе мы рассмотрим методы, которые можно использовать при построении эффективных лексических анализаторов. Как уже отмечалось в разд. 1.2.1, лексические анализаторы бывают по существу двух видов - прямые и непрямые. Мы покажем, как по регулярным выражениям, описывающим соответствующие лексемы, строятся анализаторы обоих видов.

3.3.1. Язык расширенных регулярных выражений

Множества допустимых цепочек знаков, образующих идентификаторы и другие лексемы языков программирования, почти всегда оказываются регулярными. Например, идентификаторы Фортрана описываются как цепочки, „содержащие от одной до шести латинских букв или цифр и начинающиеся буквой". Очевидно, что это множество регулярно и его описывает регулярное выражение

(Л+...4-г)(е + (Л + ...+2 + 0 4-.-. +9) (е + {Л+...-Ьг + 0+...+9)( + (Л+... + + 0 + ...-f9) ( + (Л+...+г + 0+...+9)( + Л + .-.+2 + 0+...+9))))

Это выражение чересчур громоздко, так что имеет смысл ввести расширенные регулярные выражения, удобнее описывающие это и другие интересные с практической точки зрения регулярные выражения.

Определение. Расширенные регулярные выражения и множества, которые они обозначшопг, определяются рекурсивно следующим образом.

(!) Если -регулярное выражение, то оно расширенное и обозначает множество R

(2) Если R - расширенное регулярное выражение, то

(а) R"" - расширенное регулярное выражение, обозначаю- -щее множество RR*,

(б) i?*" -расширенное регулярное выражение, обозначающее множество {с)- и и и ... \}R",

i) Напомним, что мы не различаем регулярное выражение н обозначаемое нм множество, когда ясно, о чем идет речь.

(в) -расширенное регулярное выражение, обозначающее множество RyjRRU .. • \JR"-

(3) Если Ri и R-i - расширенные регулярные выражения, -/?2 и /?1 П R2 - расширенные регулярные выражения,

обозначающие соответственно множества {х х Rj и х R}

и \x\xeRi и x£R}.

(4) Ничто другое не является расширенным регулярным выражением.

Соглашение. В расширенных регулярных выражениях мы будем обозначать бинарную операцию объединения знаком вместо -f, чтобы различие между этой операцией и унарными операциями и было более заметным.

Другое полезное качество аппарата, служащего для определения регулярных множеств,- это возможность давать им имена. Нужно позаботиться о том, чтобы определения, в которых участвуют имена, ие приводили к порочному кругу или чтобы не получилась по существу система определяющих уравнений, подобная системе, рассмотренной в разд. 2.6, с помощью которой можно определить любой КС-язык. В принципе пет ничего плохого в том, чтобы при определении лексем использовать всю Мощь определяющих уравнений (или распознавать лексемы с помощью МП-преобразователя). Однако, как правило, лексический анализатор имеет простую структуру- обычно это структура конечного автомата. Поэтому мы предпочитаем пользоваться механизмом, который может определять только регулярные множества и по которому легко строить соответствующие конечные преобразователи. Су1цественно контекстно-свободные аспекты языка анализируются на этапе синтаксического разбора, гораздо более сложном, чем лексическая фаза.

Определение. Последовательностью регулярных определений в алфавите 2 назовем список определений A = Ri, A,R, п=Р-п где Л, Л„ - различные символы, не принадлежа-

щие 2, и -расширенное регулярное выражение в алфавите 2и{Л, Ai J (!</<«). Для lin определим расширенное регулярное выражение R[ в алфавите 2:

(2) Ri получается из Ri заменой каждого вхождения Aj для */<i выражением R]-.

Множество, обозначаемое символом Л-, это множество, обозначаемое выражением RI

Должно быть ясно, что множества, обозначаемые расширенными регулярными выражениями и последовательностями ре-





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