А.В. Ахо, М.С. Лам, Р. Сети, Дж. Д. Ульман - Компиляторы - принципы, технологии и инструментарий (1114947), страница 88
Текст из файла (страница 88)
+ Реалшация Е-атрибутного СУО на основе П:гральиатики. Каждое Е-атрибутное определение с лежащей в его основе Ь(.-грамматикой может быть реализовано одновременно с синтаксическим анализом. Записи для хранения синтезируемых атрибутов нетерминалов размещаются в стеке под записями нетерминалов, в то время как наследуемые атрибуты нетерминалов хранятся в стеке вместе с нетерминалами. Записи действий также размещаются в стеке для выполнения вычислений атрибутов в соответствующие моменты времени. + Реализация (:атрибутного СУО на основе й1;грамматики при восходящем синтаксическом аналше.
1.-атрибутное определение с лежащей в его основе ЕЕ-грамматикой может быть преобразовано в трансляцию на основе Ей-грамматики и трансляцию, выполняемую в процессе восходящего синтаксического анализа. Преобразование грамматики включает нетерминалы-маркеры, которые появляются в стеке восходящего синтаксического анализатора и хранят наследуемые атрибуты нетерминалов, находящихся в стеке над ними. Синтезируемые атрибуты хранятся в стеке вместе с их нетерминалами.
5.7 Список литературы к главе 5 Синтаксически управляемые определения представляют собой вид индуктивных определений, в которых индукция проявляется в синтаксической структуре. Как таковые опн давно неформально используются в математике. Их применение к языкам программирования началось с А18о! 60. Идея синтаксического анализатора, который вызывает семантические действия, может быть найдена у Сеймельсона (Бате!зоп) и Бауэра (Вацег) [81, а также у Брукера (Вгоо)сег) и Морриса (Мопзз) [1].
Айронс (1гопз) [2! создал один из первых синтаксически управляемых компиляторов с использованием синтезируемых атрибутов. Класс 1 -атрибутных определений введен в [61. Наследуемые атрибуты, графы зависимостей и проверка цикличности СУО (т.е, выяснение, существует ли некоторое дерево разбора, для которого не существует порядка вычисления атрибутов) обязаны своим происхождением Кнуту 442 Глава 5.
Синтаксически управляемая трансляция (Кпц!Ь) [5]. Джазаери (1ахауеп)„Огден (08г(еп) и Раунде (КошмЬ) [3] показали, что проверка цикличности требует времени, экспоненциально зависящего от размера СУО. Генераторы синтаксических анализаторов„такие как Уасс [4] (см. также список литературы к главе 4), поддерживают вычисление атрибутов в процессе синтаксического анализа. Обзор Планки (Раа!г!а) [7] может служить хорошей отправной точкой для литературного поиска по синтаксически управляемым определениям и трансляциям. 1.
Вгоокег, К. А. апг! 13. Могпя, "А 8епега! !галя!айоп рго8гаш Тог рЬгаяе яГгцсгцге 1ап8ца8ея", Х АСМ 9:1 (1962), рр. 1 — 10. 2. !гоня, Е. Т., "А лунгах Йгесгег! сошрг!ег Гог А!8о! 60", Сотт. АСМ 4:1 (1961), рр. 51-55. 3. )ахауеп', М., %. К Ойг1еп, апб %. С. КоцпгЬ, "ТЬе !пП!пз!с ехропепйа! согпр!ех!гу оГ гЬе с!гсц!апту ргоЫеш Гог анпЬц!е 8гапцпагз", Сотт. АСМ 18:12 (1975), рр. 697-706. 4. ЯоЬпяоп, Я.
С., "Уасс — Уег АпогЬег Сошр!1ег Сошрйег", Сошрцйп8 Яс!епсе Тес1ппса! Кероп 32, Ве!1 ЬаЬогасопез, Мцпау Н!!1, Х1, 1975. Доступно по адресу Ьсср: //Жповацк. сошрз2ексоо1в. пес/уасс/. 5. КпцгЬ, Р. Е., "Бешапг!ся оГ сопгехпТгее !апйца8ея**, Магйетаг!са! Яуегете Тйеогу 2;2 (1968), рр. 127 — 145. См. также Маг/гетаг!са! Яулгете 7йеогу 5:1 (1971), рр. 95-96.
6. Ьецчз, Р. М. 11, О. Ь Колец)ггапгг, апг) К. Е. 8геагпя, "АйпЬц!его !ганя!аг!опз", Х Сотригег апг! Булгет Яс!епсег 9:3 (1974), рр. 279 — 307. 7. РааИг1, 1., "АппЬцге 8гапцпаг рагаг!!8гпя — а Ь!8Ь-1ете! гпегЬог!о!ойу ш !ап8ца8е ппр!егпепГаг!оп", Сотриг!п8 Яигкеуг 27:2 (1995), рр. 196 — 255. 8. Каше!яоп, К. апг! К 1.. Вацег, "Яегрзепйа! Гоппц!а ггапя!ацоп", Сотт. АСМ 3:2 (1960), рр. 76-83. ГЛАВА б Генерация промежуточного кода Заключительная стадия Начальная стадия Рнс. 6.1. Логическая структура начальной стадии компилятора Статические проверки включают проверку типов, которая гарантирует применение операторов к совместимым операндам.
Они также включают любые синтаксические проверки, оставшиеся после синтаксического анализа. Например, статическая проверка проверяет, что инструкция Ьгеа1с в языке С находится В модели анализа-синтеза компилятора на начальной стадии анализируется исходная программа и создается промежуточное представление, из которого на заключительной стадии генерируется целевой код.
В идеальном случае детали исходного языка ограничены начальной стадией, а детали целевой машины— заключительной стадией компилятора. При наличии соответствующим образом определенного промежуточного представления компилятор для языка т и целевой машины т' может быть построен путем комбинации начальной стадии для языка т и заключительной — для машины т'. Этот подход к разработке набора компиляторов может сэкономить значительное количество работы: т х п компиляторов могут быть созданы путем написания т начальных стадий и и заключительных. В этой главе будут рассмотрены вопросы промежуточного представления, статической проверки типов и генерации промежуточного кода.
Для простоты мы полагаем, что начальная стадия компилятора организована так, как показано на рис. 6.1, где синтаксический анализ, статические проверки и генерация промежуточного кода выполняются последовательно; однако иногда они могут быть скомбинированы и включены в синтаксический анализ.
Для определения проверок и трансляции мы воспользуемся синтаксически управляемым формализмом из глав 2 и 5. Многие схемы трансляции могут быть реализованы в процессе восходящего или нисходящего синтаксического анализа с применением методов из главы 5. Все схемы могут быть реализованы путем построения синтаксического дерева с его последующих обходом. 444 Глава 6.
Генерация промежуточного кода в охватывающей конструкции тупт1е, Гог или зтуйсл; если такой охватывающей конструкции нет, генерируется сообщение об ошибке. Подход, описанный в этой главе, может использоваться для широкого диапазона промежуточных представлений, включая синтаксические деревья и трехадресный код, описанные в разделе 2.8. Термин "трехадресный код" происходит от команд общего вида ж = р ор с с тремя адресами: два — операндов р и а и один— результата т.
В процессе трансляции программы на некотором исходном языке в код для заданной целевой машины компилятор может построить последовательность промежуточных представлений, как показано на рис. 6.2. Высоюуровневые представления близки к исходному языку, а низкоуровневые — к целевому коду. Синтаксические деревья представляют собой высокий уровень; они описывают естественную иерархическую структуру исходной программы и хорошо подходят для задач наподобие статической проверки типов. Исходная Высокоуровневое Низкоуровневое Целевой — — промежуточное -ы- ... -ы- промежуточное -~ программа код представление представление Рис.
6.2. Компилятор может использовать последовательность промежуточных представлений Низкоуровневое представление подходит для машинно-зависимых задач, таких как распределение регистров и выбор команд. Трехадресный юд может варьироваться в широких пределах — от высокоуровневого до низюуровневого, в зависимости от выбора операторов. Как мы увидим в разделе 6.2.3, для выражений различие между синтаксическими деревьями и трехадресным кодом невелико. Но для конструкций циклов, например, синтаксическое дерево представляет компоненты конструкции, в то время как трехадресный код для представления потока управления использует метки и команды перехода — так же, как и машинный язык. Выбор или дизайн промежуточного представления варьируется от компилятора к компилятору.
Промежуточное представление может как использовать реальный язык, так и состоять из внутренних структур данных, совместно используемых фазами компилятора. С представляет собой язык программирования, но он очень часто используется в качестве промежуточного в силу его гибкости, возможности компиляции в эффективный машинный код и распространенности компиляторов. Например, первоначально компилятор С++ состоял из начальной стадии, которая генерировала код С; при этом компилятор С можно рассматривать как заключительную стадию. 445 6.!.
Варианты синтаксических деревьев 6.1 Варианты синтаксических деревьев Узлы синтаксического дерева представляют конструкции в исходной программе; их дочерние узлы представляют значимые компоненты конструкций. Ориентированный ациклический граф (Йгес(ег) асус)(с ятарЬ) для выражения идентифицирует общие подвьгражеиил (сопппоп знЬехргезз(опз), т.е. подвыражения, встречающиеся в выражении более одного раза. Как мы увидим в этом разделе далее, ориентированный ациклический граф может быть построен с помощью тех же методов, которые использовались при построении синтаксических деревьев.
6.1.1 Ориентированные ацикличеекие графы для выражений Подобно синтаксическому дереву для выражения ориентированный ациклический граф имеет листья, соответствующие атомарным операндам, и внутренние узлы, соответствующие операторам. Отличие состоит в том, что узел Х в ориентированном ациклическом графе имеет более одного родителя, если М представляет собой общее подвыражение; в синтаксическом дереве поддерево для общего подвыражения будет продублировано столько раз, сколько раз это подвыражение встречается в исходном выражении.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
