А.В. Ахо, М.С. Лам, Р. Сети, Дж. Д. Ульман - Компиляторы - принципы, технологии и инструментарий (1114947), страница 76
Текст из файла (страница 76)
137 — 167. 7. Оаш, 1., "В!Ыю8гарЬу оп Булгак Епог Напг)1!п8 !и 1.ап8иа8е Тгапв!агюп Куя гепь", 1991. Доступен в группе новостей совр. соврз.1егв; см. Ьгср: //совр11ега.1есс.сов/соврагсЬ/агс1с1е/91-04-050. 8. ОеВ.ешег, Р., "Ргасбса! Тгаил!агота Гог ЕВ(!с) 1.ап8иа8ев", РЬ.О. 1Ьев!л, М(Т, СагпЬпд8е, МА, 1969. 9. ОеВешег, Р., тбипр!е 1 К(1с) 8гаплпагв'*, Сотт. АСМ 14:7 (1и!у, 1971), рр. 453-460. ОоппеПу, С. апд В. Яга!1шап, "В!зоп: ТЬе гАСС-согпраг!Ые Рагвег бепегагог'*, Ьсгр://вплн.дпи.ого/во1Гнаге/1з1воп/вапиа1/. 10. 11.
Еаг!еу, 1., "Ап ей)с(епГ сопгехг-1гсе рагяи8 а18ог!1Ьш'*, Сотт. АСМ 13:2 (РеЬ., 1970), рр. 94 — 102. Еаг!еу, 1., "АшЫ8шгу аиг( ргесег)енсе !и лунгах нелспр!!оп", Асса 1п/Ьгтагиа 4:2 (1975), рр. 183 — 192. 12. ! 3, Ноуг(, В. И'., "Оп ашЫ8шгу ш рЬгаве-виисшге !ап8ла8ея", Соте. АСМ 5:1О (Ос!., 1962), рр. 526-534.
14. Ноуг(, К. Иг., тбупГасбс апа!ул!л апб орега!ог ргесебепсе", Х АСМ 10:3 (1963), рр. 316-333. строки; время работы этого алгоритма в общем случае — 0 (пв), но для однознач- ных грамматик оно сокращается до О (п ). 381 4.1 !. Список литературы к главе 4 15. бгипе, В апд С.
1 Н. )асоЬя, "А рго8гапипег-й!енса! у ЬЬ(1) рагяег 8епегаГог", Бо/очаге Ргасг/се апг/ Ехрег1епсе 18:1 ()ап., 1988), рр. 29-38. См. также Ьсср://чпгн.св.чп.п1/-сег1е1/1.1.реп.ЬГда1. ! 6. Ноаге, С. А. К., "К ерогг оп гйе Ейюп А!8о! !ганя! агог", Сотргаег Х 52 (! 962), рр. 127-129. 17. Норсгой, 1 Е., К. МоПчапЬ апд 1. О.
ЫПгпап, 1пггог/исггоп го А и!атаги ТЬеогу, йап8иа8ез, апг1 Сотригаг/оп, Адйзоп-%ея!еу, Воя!оп МА, 2001. !8. Ног)зоп, Б. Е. ег а1., "С()Р ЬАЬК Рагяег бепегагог !п )ача", доступно по адресу Ьсер: //чпеы2. св. спш. ес!и/рго3ессв/сор/. !9, 1п8еппап, Р. У,, "Рашш-Вас)гпз Гопп зп88ея1ей", Сотт. АСМ 10:3 (МагсЬ 1967), р. 137. 20. УоЬпяоп, Я. С., "брасс — Уег Апогйег Сошрйег Сошрйег*', Сошригш8 Яс!епсе ТесЬп(са! Керогг 32, Вей 1.аЬогагопез, Мштау Н!П, Ы1, 1975. Доступно по адресу Ьсер: //Ыповапх. согвр11екГоо1в.
пеГ/уасс/. 21. Каяапп', Т., "Ап ешс!епГ гесо8пйюп апд зупГах апа!уяя а!8опГЬш Рог сопГехГ1гее!ап8па8ея", АРСКЬ-65-758, А!г Рогсе СашЬг)фе КеяеагсЬ 1.аЬогагогу, Ведун), МА, 1965. 22. КппгЬ, Р. Е., "Оп 1Ье ггапз!айоп оГ!ап8па8ез антош 1ей го П8Ьг",!п~огтагюп апИ Сопгго1 8:6 (! 965), рр. 607-639. 23. Когеп)а)с, А.
1., "А ргасйса1 шеГЬод Гог сопяГгпсйп8 ЬК((г) ргосеязогз", Сотт. АСМ 12:!! (14оч, !969), рр. 613 †6. 24. Ьечч!я, Р. М. 11 апд К. Е. 81еагпя, "Бупгах-йгесгед ггапяг(ис!юп", ./. АСМ 15;3 (1968), рр. 465-488. 25. МсС!пге, К М., "ТМб — а яупгах-йгессег( сошр!!ег", Ргос. 20г6 АСМ /Чагl. СопЯ (1965), рр. 262 274. 26. Хаог, Р. ег а!., "КерогГ оп йе а18ог!ГЬгшс !ап8па8е А1.бО1 60", Сотт. АСМ 3:5 (Мау, 1960), рр. 299 — 314. См.
также Сотт. АСМ 6: ! (Лап., 1963), рр. 1-17. 27. Рагг, Т., "АХТЬК", Ьсср: //ичгчг. апс1г. окд/. 28. БсЬогге, 13. Ч., "Мега-П: а зупгах-опепсег! сошрйег ччпйп8 !ап8оа8е", Ргос. !9й А СМ /чаг!. СопЯ (1964), рр. 131.3-1-О1.3-11. ГЛАВА 5 Синтаксически управляемая трансляция В данной паве развивается затронутая в разделе 2.3 тема — трансляция языков, управляемая контекстно-свободной грамматикой. Методы трансляции из этой главы будут использоваться в главе 6 для проверки типов и генерации промежуточного кода. Эти методы применимы также при реализации небольших языков для специализированных задач; в данной главе приведен пример из полиграфии.
Мы связываем информацию с конструкциями языка, назначая атрибуты символу (или символам) грамматики, представляющему конструкцию (этот вопрос уже рассматривался в разделе 2.3.2). Синтаксически управляемое определение указывает значения атрибутов при помощи связывания с грамматическими продукциямн семантических правил. Например, транслятор инфиксных выражений в постфиксные может иметь следующие продукцию и правило: СЕМАНТИЧЕСКОЕ ПРАВИЛО Е.соде = Еысог2е~йТ.соде~~' + ' ПРОДУКЦИЯ Е=Е,+Т (5.1) Š— Е1 + Т (рплю '+ ') (5.2) По соглашению семантические действия заключаются в фигурные скобки. (Если фигурная скобка встречается в качестве грамматического символа, она заключается в одинарные кавычки — '(' и ')*.) Положение семантического действия Эта продукция содержит два нетерминала, Е и Т; индекс у Е1 предназначен для того, чтобы отличать Е в теле продукции от Е в заголовке.
И Е, и Т имеют атрибут сос(е, представляющий собой строку. Семантическое правило указывает, что строка Е.согде образуется путем конкатенации строк Е1 . соде, Т.сне и символа '+'. Правило явно указывает, что трансляция Е образуется из трансляций Е, Т и 'г', но реализация в ходе непосредственной работы со строками может оказаться неэффективной. В разделе 2.3.5 схема синтаксически управляемой трансляции вставляет в тела продукций программные фрагменты, называющиеся семантическими действиями, как в следующем случае: Глава 5.
Синтаксически управляемая трансляция в теле продукции определяет порядок, в котором выполняются действия. В продукции (5.2) действие выполняется в конце, после всех грамматических символов; в общем случае семантические действия могут располагаться в любом месте тела продукции. Сравнивая эти два варианта записи, можно заметить, что синтаксически управляемые определения более удобочитаемы, а следовательно, более подходят в качестве спецификаций.
Однако схемы трансляций могут оказаться более эффективны и потому в большей степени пригодны для реализаций. Наиболее общий подход к синтаксически управляемой трансляции состоит в построении дерева разбора или синтаксического дерева с последующим вычислением значений атрибутов в узлах путем обхода узлов этого дерева. Во многих случаях трансляция может выполняться в процессе синтаксического анализа, без явного построения дерева разбора.
Мы познакомимся с классом синтаксически управляемых трансляций, которые называются "1.-атрибутными трансляциями" (здесь (. означает "слева направо") и включают почти все трансляции, которые могут выполняться в процессе синтаксического анализа. Мы также изучим меньший класс — "Я-атрибутные трансляции" (здесь Я означает "синтезируемые"), которые легко выполняются при восходящем синтаксическом анализе. 5.1 Синтаксически управляемые определения Синтаксически управляемое определение (СУО) является контекстно-свободной грамматикой с атрибутами и правилами. Атрибуты связаны с грамматическими символами, а правила — с продукциями.
Если Х представляет собой символ, а и — один из его атрибутов, то значение а в некотором узле дерева разбора, помеченном Х, записывается как Х.а. Если узлы дерева разбора реализованы в виде записей или объектов, то атрибуты Х могут быть реализованы как поля данных в записях, представляющих узлы Х.
Атрибуты могут быть любого вида: числами, типами, таблицами ссылок или строками. Строки могут представлять собой, в частности, длинные последовательности кода, например кода на промежуточном языке, используемом компилятором. 5.1.1 Наследуемые и синтезируемые атрибуты Мы будем работать с двумя типами атрибутов для нетерминалов. 1. Синтезируемый атрибут для нетерминала А в узле )ч' дерева разбора определяется семантическим правилом, связанным с продукцией в Аг.
Заметим, что в качестве заголовка этой продукции должен выступать нетерминал А. Синтезируемый атрибут в узле )ч' определяется только с использованием значений атрибутов в дочерних по отношению к )У узлах и в самом узле й(. 385 5.1. Синтаксически управляемые определения Альтернативное определение наследуемых атрибутов Если позволить наследуемому атрибуту В.с в узле Х быть определенным с использованием значений атрибутов в дочерних узлах Х, а также в самом %, его родителе и братьях, то не нужны никакие дополнительные трансляции. Такие правила могут быть "имитированы" путем создания дополнительных атрибутов В, скажем, В.сы В.сз,....
Это синтезируемые атрибуты, которые копируют необходимые атрибуты узлов, дочерних по отношению к узлу В. Затем В.с вычисляется как наследуемый атрибут с использованием атрибутов В.сп В.сз,... вместо атрибутов дочерних узлов. На практике такие атрибуты требуются редко. 2.
Наследуеиый атрибут для нетерминала В в узле Ж дерева разбора определяется семантическим правилом, связанным с продукцией в Ж. Заметим, что нетерминал В должен участвовать в продукции в качестве символа в ее теле. Наследуемый атрибут в узле М определяется с использованием значений атрибутов в родительском по отношению к Х узле, в самом узле Х и дочерних узлах его родительского узла ("братьях" )У). Наследуемые атрибуты в узле )У не могут определяться через атрибуты дочерних по отношению к Х узлов; синтезируемые же атрибуты в узле )У могут определяться через значения наследуемых атрибутов в самом узле Х.
Терминалы могут иметь синтезируемые, но не наследуемые атрибуты. Атрибуты терминалов имеют лексические значения, придаваемые им лексическим анализатором. В СУО не существует семантических правил для вычисления значений атрибутов терминалов. Пример 5.1. СУО на рис. 5.1 основано на знакомой нам грамматике для арифметических выражений с операторами + и *. Оно вычисляет выражения, завершающиеся ограничивающим маркером и. Каждый нетерминал в СУО имеет единственный синтезируемый атрибут га1. Мы также считаем, что терминал п181т имеет синтезируемый атрибут 1ех а1, представляющий собой целое значение, возвращаемое лексическим анализатором. Правило для продукции 1, Ь вЂ” Е и, устанавливает Ьюа1 равным Ела!, которое, как мы увидим, равно числовому значению всего выражения.
Продукция 2, Š— Е~ + Т, также имеет одно правило, которое вычисляет атрибут ка! заголовка Е как сумму значений Е~ и Т. В любом помеченном Е узле Ж дерева разбора значение га1 для Е представляет собой сумму значений ка1 дочерних по отношению к Ж узлов с метками Е и Т. 386 Глава 5. Синтаксически управляемая трансляция Рнс. 5.1. Синтаксически управляемое определение простого настольного калькулятора Продукция 3, Š— Т, имеет единственное правило, которое определяет значение из! для Е как значение того же атрибута у дочернего узла Т. Продукция 4 подобна продукции 2: ее правило просто умножает значения атрибутов в дочерних узлах вместо их сложения.
Правила продукций 5 и 6 копируют значения атрибутов дочерних узлов, так же, как и в продукции 3. Продукция 7 присваивает атрибуту Ела! числовое значение токена 618зт, возвращаемое лексическим анализатором.о СУО, которые включают только синтезируемые атрибуты, называются $-атрибутньгми определениями; СУО на рис. 5.! обладает данным свойством. В Я- атрибутном СУО каждое правило вычисляет атрибут нетерминала в заголовке продукции, используя атрибуты, полученные из тела продукции. Для простоты в примерах этого раздела используются семантические правила без побочных действий. На практике бывает удобно допускать в СУО небольшие ограниченные побочные действия, такие как печать результатов вычислений настольного калькулятора или работа с таблицей символов.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
