Теория синтаксического анализа, перевода и компиляции - Том 1 (943928), страница 57
Текст из файла (страница 57)
Так как А покрывает Х», можно выбрать ». 1 Т не с еств,ет чтобы получилась пара, нс входящая в Т». Итак, . ущ Теорема 3.8. За исключением я=2, для любого й'= 1 класс ,У'»91 собственно включает У». Доказательство. Случай 3=1 дока оказан в лемме 3.8. Остальные случаи охватываются леммой 3.1 . П Инте еспое практическое следствие теоремы мы .8 состоит в том, что, хотя кажется заманчивым сконструирова у р ть так ю систему построения компиляторов, чтобы входная р . я г амматика была В нормальной форме Хоыского, эта система н ема не в состоянии выполнить любую синтаксически управляемую транс ц т ансляцию, а более общая система смогла бы это сделать.
Однако п о похоже что иа практике СУ-переводы в худщем случае будут принадлежать классУ ЧТЯ (и, следовательно,,'Tя). УПРАЖНЕНИЯ "3 2 1 Пусть Т вЂ” СУ-перевод. Покажите, что существует такая константа с, что для каждой цепочки х из области его определения найдется такая цепочка у, что (х, у) ЕТ и (у)(с(~х)+1). *3 2.2. (а) Покажите, что соли Т,— -регулярный перевод и Тв — СУ-перевод, то Т, о Тв=((х, г) ~(х, у) ЕТ, и (у, г) ЕТ, для некоторой цепочки у) — СУ-перевод'). ) Часто зта операпия иад переводами, называемая яомпозиписй, запиовааевся с оп рапдами в обратном порядке, таи что в нашем определеиии аде быап бы писать Т,Б Т„а ие Т, 0 Тв. Рвы ие изменим нашей записи, та е к " еиа выглядит более естествеяиой.
2Е! ГЛ 3, ТЕОРИЯ ПЕРЕЗОДЛ ( ) окажите, что если перевод Т, простой, то перевод Т о Т, (б) П тоже простой, з д 1 3.2.3. а) П ... ( ) окажите, что если Т вЂ” СУ-перевод, то Т '— СУ-перевод. — — тоже (б) Покажите, что если перевод Т простой, то пе ево Т-ь тоже простой. *3.2.4. (Е) Пусть Т, — регулярный перевод, а Т, — СУ-пере. (б) Покажите, что если перевод Т, простой, то перево, 3 г д 3.2.5. Най, водов из ... Найдите сильно характеризующие языки для СУ- -пере- (а) примера 3.5, (б) примера 3.7, (в) примера 3.12. 3.2.6, Для СУ-перевода пз упр. 3.2.5 найдите язык, ха ак- теризующий его, но не сильно. 3.2. . .2.7. Дополните доказательство леммы 3.4. 3.2.8. Дополните доказательство случая 2 в примере 3.17.
3.2.9. Пок п остой С ажите, что каждый простой СУ-перевод оп р У-схемой, не содержащей бесполезных нет ределяется х нетермипалов. 3.2.10. Пусть Т, †прост СУ-перево а Т— пе ево . р д. Всегда ли Т, П Т, — простой СУ-перевод? од, а,— регулярный 3.2.11, Докажите лемму 3.6. 3.2.12. Докажите лемму 3.9. 3.2.13. П . Постройте СУ-схему порядка й, определяющую Тл, 3.2.14. Пусть Т-=(!>[, Х, Х, 7?, 5), где Х=-(5, А, В, С, Р), Х=-(а, Ь, с, д) и )? состоит из правил А- аА, ОА А е,е  — ЬВ, Ь  — «е,е С' сС, сС с- е,е  — Ы, с(В В е,е и одного из приведенных ниже.
Найдите наименьший порядок перевода т(Т) для каждого из этих дополнительиа!х правил: (а) 5-- АВСВ, АВСР (в) 5 — АВСР, ВВСА (б) 5 — АВСР, ВСВА (г) 5' — АВСР, ВРАС 282 З.З. ЛЕКСИЧРСКИй АНАЛИЗ Покажите, что если Т определяется ДМП-преобр 3 вателем, Т „льно характеризуется детерминированным КС- языком. 3 2,16, Верно ли обращение упражнения 3.2.15? 3 2 17. докажите следствия теорем З.З и 3 4 Замечания по литературе 'Понятие характеризуюиьего языка н результаты равд.
3,2.! и 3.2.2 взяты работы дхо и Ульмана [!999 б), а разультаты раза. 3.2.3 — из работы ахо и Ульмана [!969а). З.З. ЛЕКСИЧЕСКИЙ АНАЛИЗ Лексический анализ образует первый этап процесса компиляции. На этом этапе символы, составляющие исходную программу, считываются и группиру!отса в отдельные лексические элементы, называемые лексемами. Лексический анализ важен для процесса компиляции по нескольким причинам. Наибольшее значение имеет, по-видимому, то, что замена в программе идентификаторов и констант лексемами делает представление программы удобнее для дальнейшей обработки. Далее„лексический анализ уменьшает длину программы, устраняя из исходного ее представления несущественные пробелы и комментарии.
На следующих стадиях компиляции компилятор может несколько раз просматривать внутреннее представление программы, Поэтому, уменьшая с помощью лексического анализа длину этого пред- 1 ставления, можно сократить общее время процесса компиляции Во многих ситуапиях выбор конструкций, которые будут выделяться как лексемы, довольно произволен. Например, если в языке разрешены комплексные константы вида <комплексная константа> — (<вещественное>, <вещественное>) то возможны две стратегии.
Можно трактовать <вещественное> как лексический элемент и отложить распознавание конструкции (<вещественное>, <вещественное>) как комплексной константы до Фазы синтаксического анализа, Другая стратегия состоит и том, чтобы с помощью более сложного лексического анализатора распознать эту конструкцию как комплексную константу яа лексическом уровне и передать тип лексемы синтаксическому а"алнзатору.
Важно также отметить, что если в вычислительном центре изменяется принятое в нем множество терминальных символов, то это отражается лишь па лексическом анализе, аиа Вольшую часта того что происходит в течение лексического вал "за, можно моделировать с помощью конечных преобразоателей, работающих последовательно или параллельно, Напри-, 283 гл з. теоеия пеееводл аз лексический лнхлиз мер, лексический анализатор может состоять из ряда последа. вательно соединенных конечных преобразователей. Первый пре. образователь в этой цепи может устранять из исходной программы все несущественные пробелы, второй ликвидирует комментарии, третий ищет константы и т.
д. Другая возможность †завес набор конечных преобразователей, каждый из которых ищет определенную лексяческую конструкцию. В этом разделе мы рассмотрим методы, которые можно использовать при построении эффективных лексических анали. заторов. Как уже отмечалось в равд. 1.2.1, лексические анали. заторы бывают по существу двух видов — прямые и непрямые. Мы покажем, как по регулярным выражениям, описывающим соответствующие лексемы, строятся анализаторы обоих видов, З.ЗЛ. Язык расширенных регулярных выражений Множества допустимых цепочек знаков, образующих идентификаторы и другие лексемы языков программирования, почтя всегда оказываются регулярнымн, Например, идентификаторы Фортрана описываются как цепочки, „содержащие от одной до шести латинских букв илн цифр н начинающиеся буквой'", Очевидно, что это множество регулярно и его описывает регулярное выражение (А+...
+2) (е+(А+... +2+0+... +9) (в+(А+... +2+0+... +9) (е+(А+... +2+0+... +9) (е+(А+... +2+0+... +9) (в+ А+... +2+0+... +9)))) Зто выражение чересчур громоздко, так что имеет смысл ввести расширенные регулярные выражения, удобнее описывакпцие это и другие интересные с практической точки зрения регулярные выражения. Определение. Расширенные регуллрныв выразсения и множества, которые они обозначают, определяются рскурснвно следующим образом.
(1) Если ЕŠ†регулярн выражение, то оно расширенное н обозначает множество ЕЕ '). (2) Если Ес — расширенное регулярное выражение, то (а) Ес+ — расширенное регулярное выражение, обозначающее множество Ес)с'*, (б) Ес*' — расширенное регулярное выражение, обозначающее множество (е) 0 Ес 0)И 0 0Ес" ') Напомним, что мм не разлнчвеы регулярное выражение н обозначаемсс нм множество, когда нснь, о чем ндет речь.
284 (в) Ез+ь Ра сширенное регулярное выражение, обознаюшее множество И 0)с'П 0... 0И". Е ли Е(, н ЕС,— РасшиРенные РегУлЯРпые выРажениЯ, Ес д Ес — расширенные регула пые выражения, то соотвстственно множества х х . я обозначающие соот н (х(хЕ и хЕП,). (4) Ничто другое не я вляется расширенным регулярным вы- ражением. оглашение. В расширенных регулярных выражениях мы б а ную операцию объединения знаком ~ вместо е ежду й операц ей н унарн мн р ° ем обозначать ниари опе а. ~-, чтобы различие межд циями и + "" было более заметным.
гое полезное качество аппарата, служащего для опреде, — это возможность давать нм имена. ег ля иых множеств,— эт Н жно позаботиться о том, чт , чтобы определения, в которых учае приводили к порочному кругу или чтобы не ствуют имена, ие х авненнй, по- пал чнлась по существу система определяющих ур до бная системе, рассмот н т„енной в разд. 2.6, с помощью которой б КС-язык. В принципе пет ничего пло- можно определить лю ой -яз кого в том, что ы при оп ед о определении лексем использовать всю мо оп еделяющих уравнений впений (или распознавать лексемы с по- мощью МП-преобразователя, б,, Однако, как правило, лексический анализатор имеет простую структуру — обычно это структура мата. Поэтому мы предпочитаем пользоваться конечного автомата. о олька ег ля ные мно- механизмом, который может определять только ре ул р ом легко строить соответствующие конечные жества и по которому легко ст -свобо ные аспекты и еоб азователи.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
