А.В. Ахо, М.С. Лам, Р. Сети, Дж. Д. Ульман - Компиляторы - принципы, технологии и инструментарий (1114947), страница 80
Текст из файла (страница 80)
Третий вид линий — пунктирные — представляет значения Е.лойе и Т.ног1е; каждая линия указывает на соответствующий узел синтаксического дерева. Внизу находятся листья для а, 4 и с, построенные с применением конструктора 1.еаг. Считаем, что лексическое значение Ы.елггу указывает на запись в таблице символов, а лексическое значение ппт.ва1 представляет собой числовую константу. Эти листья, или указатели на них, становятся значениями Т.лойе трех узлов дерева разбора, помеченных Т, согласно правилам 5 и 6. Заметим, что в соответствии с правилом 3 указатель на лист а является также значением Е.лойе для крайнего слева Е в дереве разбора. Правило 2 заставляет создать узел с ор, равным знаку †, и указателями на два первых листа. Затем правило 1 создает корневой узел синтаксического дерева, объединяя узел для — с третьим листом.
Если правила вычисляются в процессе обратного обхода дерева разбора или при свертках в процессе восходящего синтаксического анализа, то последовательность шагов, показанная на рис. 5.12, заканчивается указателем ра, указывающим на корень построенного синтаксического дерева. и 402 Есподе диоде Т.поде Диоде,' — Тподе Тпод» пив пс К записи дпп о Рис. 5. ! !. Синтаксическое дерево для а — 4+ с Рис.
5.12.Шаги построения синтаксического дерева для а — 4 4- с В случае грамматики для нисходящего синтаксического анализа строятся те же синтаксические деревья с использованием той же последовательности шагов, несмотря на то что структура деревьев разбора существенно отличается от структуры синтаксических деревьев. Пример 5.12. Ь-атрибутное определение на рис. 5.13 выполняет ту же трансляцию, что и Я-атрибутное определение на рис.
5.10. Атрибуты для грамматических символов Е, Т, Ы и пшп рассмотрены в примере 5.11. Правила для построения синтаксических деревьев в этом примере подобны правилам для настольного калькулятора из примера 5.3. В примере с калькулятором член х * у вычислялся путем передачи х как наследуемого атрибута, поскольку х и *у находятся в разных частях дерева разбора. Здесь идея состоит в том, чтобы построить синтаксическое дерево для х + у, передавая х в качестве насле- 1) 2) 3) 4) 5) Глава 5. Синтаксически управляемая трансляция р! = пете ЕеаДЫ, епгту-а); рз = петя 2,еаТ'!пинг, 4); рз = петтМоде(' — ',рырз); р4 = пезт ьеаДЫ, епгту-с); рь = не\У Массе ( + рз~ р4) ! 403 5.3. Применения синтаксически управляемой трансляции Рис.
5.13. Построение синтаксических деревьев в процессе нисходящего синтаксического анализа дуемого атрибута, поскольку х и +у находятся в разных поддеревьях. Нетерминап Е' является копией нетерминала Т' из примера 5.3. Сравните граф зависимостей для а — 4+ с на рис. 5.14 с графом зависимостей для 3 * 5 на рис.
5.7. Е 13 ейе т 2 лоие И ! ела Т 4 поде Мяб Е' Ы УУЯ авп 3 ин и Т 8 поде 2ля9 Е' 10зг" Ы 7 евет Рис. 5.14. Граф зависимостей для выражения а — 4+ с при использовании СУО на рис. 5.! 3 Нетерминал Е' имеет наследуемый атрибут пй и синтезируемый атрибут яуи. Атрибут Е' 1пЬ представляет неполное синтаксическое дерево, построенное к этому моменту. А именно, он представляет корень дерева для префикса входной строки, находящегося слева от поддерева для Е'. В узле 5 графа зависимостей на рис. 5.14 Е'.1пл обозначает корень неполного синтаксического дерева для идентификатора а, т.е. попросту лист для а.
В узле б Е'лил обозначает корень неполного 404 Глава 5. Синтаксически управляемая трансляция синтаксического дерева для входной строки а — 4. В узле 9 Е'.тЬ обозначает корень синтаксического дерева для а — 4 + с. Поскольку на этом входная строка заканчивается, в узле 9 Е'ЗлЬ указывает на корень всего синтаксического дерева. Атрибут зул передает это значение обратно вверх по дереву разбора, пока оно не становится значением Елок.
Точнее, значение атрибута в узле 10 определяется правилом Е'.луп = Е'лл6, связанным с продукцией Е' — е. Значение атрибута в узле 11 определяется правилом Е'.эул = Е',.зул, связанным с продукцией 2 на рис. 5.13. Аналогичные правила определяют значения атрибутов в узлах 12 и 13. П 5.3.2 Структура типа Наследуемые атрибуты полезны, когда структура дерева разбора отличается от абстрактного синтаксиса входной строки; тогда атрибуты могут использоваться для передачи информации из одной части дерева разбора в другую. Приведенный далее пример показывает, что несоответствие структуры может являться следствием дизайна языка, но не ограничений, накладываемых методом синтаксического анализа. Пример 5.13. В С тип 1пт [2[ [3] можно прочесть как "массив из двух массивов по 3 целых числа*'.
Соответствующее выражение типа аггау (2, аггау (3, 1лгедег)) представлено деревом на рис. 5.15. Оператор аггау принимает два параметра, число и тип. Если типы представлены деревьями, то этот оператор возвращает дерево с меткой аггау с двумя дочерними узлами — для числа и для типа. ~л1еяег Рис. 5.15. Выражение ти- па для!пт [2) [3] При использовании СУО, представленного на рис. 5.1б, нетерминал Т генерирует либо фундаментальный тип, либо тип массива. Нетерминал В генерирует один из базовых типов: 1пг или Иоак Т генерирует фундаментальный тип, если Т порождает В С, а С порождает е.
В противном случае С генерирует компоненты массива, состоящие из последовательности целых чисел, каждое из которых заключено в квадратные скобки. Нетерминалы В и Т имеют синтезируемый атрибут 1, представляющий тип. Нетерминал С имеет два атрибута: наследуемый атрибут 6 и синтезируемый атрибут г. Наследуемые атрибуты 6 передают фундаментальный тип вниз по дереву, а синтезируемые атрибуты 1 накапливают результат.
405 5ти Применения синтаксически управляемой трансляции РАВИЛА а1, Сг.1) Рис. 5.16. Т генерирует либо фундаментальный тип, либо тип массива Аннотированное дерево разбора для входной строки 1п1 [2[[3[ показано на рис. 5.17. Соответствующее выражение типа на рис. 5.15 построено путем передачи типа 1лгелег от В вниз по цепочке С посредством наследуемых агрибутов 6. Тип массива синтезируется при продвижении вверх по цепочке С посредством атрибутов 1. Рис. 5.17.
Синтаксически управляемая трансляция типов массивов Говоря более подробно, в корне для Т вЂ” В С нетерминал С наследует тип от В при помощи наследуемого атрибута С.б. В крайнем справа узле для С используется продукция С вЂ” ~ е, так что С.1 равно С.б. Семантические правила для продукции С вЂ” [ппт[ Сг образуют СЛ путем применения оператора апау к операндам ппщ.та1 и Сг.1. и 406 Глава 5. Синтаксически управляемая трансляция 5.3.3 Упражнения к разделу 5.3 Упражнение 5.3.1.
Ниже приведена грамматика для выражений, включающих оператор + и операнды, представляющие собой целые числа либо числа с плавающей точкой (числа с плавающей точкой распознаются по наличию десятичной точки): Š— ~ Е+Т(Т Т вЂ” пцш. ппш ~ пшп а) Разработайте СУО для определения типа каждого члена Т и выражения Е. б) Распространите свое СУО из п. а на выражения в постфиксной записи. Воспользуйтесь унарным оператором 1птТоР1оат для преобразования целого числа в эквивалентное число с плавающей точкой. ! Упражнение 5.3.2.
Разработайте СУО для трансляции инфиксных выражений с -> и Я в эквивалентные выражения без излишних скобок. Например, поскольку оба оператора левоассоциативны, а приоритет * выше приоритета +, ((а*(6+ с)) *(а)) транслируется в а * (6+ с) * а. ! Упражнение 5.3.3. Разработайте СУО для дифференцирования выражений наподобие х * (3 *х+ х * х), которые включают операторы + и *, переменную х и константы.
Будем считать, что никакие упрощения не выполняются, т.е. 3 * х, например, транслируется в 3 * 1+ О * х. 5.4 Синтаксически управляемые схемы трансляции Синтаксически управляемые схемы трансляции представляют собой запись, дополняющую синтаксически управляемые определения. Все применения синтаксически управляемых определений в разделе 5.3 могут быть реализованы с использованием синтаксически управляемых схем трансляции. Из раздела 2.3.5 мы знаем, что синтаксически управляемая схема трансляции (СУТ) представляет собой контекстно-свободную грамматику с программными фрагментами, внедренными в тела продукций.
Эти фрагменты называются семантическими действиями и могут находиться в любой позиции в теле продукции. По соглашению действия располагаются внутри фигурных скобок; фигурные скобки, являющиеся грамматическими символами, заключаются в кавычки. Любая СУТ может быть реализована путем построения дерева разбора с последующим выполнением действий в порядке в глубину слева направо, т.е. в порядке прямого обхода дерева.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
