А.В. Ахо, М.С. Лам, Р. Сети, Дж. Д. Ульман - Компиляторы - принципы, технологии и инструментарий (1114947), страница 78
Текст из файла (страница 78)
° Предположим, что семантическое правило, связанное с продукцией р, определяет значение синтезируемого атрибута А.Ь через значение Х.с (правило может использовать для определения А.Ь и другие атрибуты, помимо Х.с). В таком случае в графе зависимостей имеется ребро от Х.с к А.Ь. Точнее, в каждом узле )т", помеченном А, в котором применяется продукция р, создается ребро к атрибуту Ь в )т' от атрибута с в дочернем по отношению к )т' узле, соответствующем экземпляру символа Х в теле продукции'. ° Предположим, что семантическое правило, связанное с продукцией р, определяет значение наследуемого атрибута В.с с использованием значения Хль Тогда граф зависимостей содержит ребро от Х.а к В.с.
Для каждого узла зУ, помеченного В, который соответствует появлению этого В в теле продукции р, создается ребро к атрибуту с в )т' от атрибута а в узле ЛХ, который соответствует данному вхождению Х. Заметим, что ЛХ может быть родителем либо братом )т'. 'Поскольку узел зу может иметь несколько дочерних узлов, помеченных Х, считаем, что различать один и тот же символ в разных местах продукции позволяют их индексы. 392 Глава 5. Синтаксически управляемая трансляция Пример 5.4. Рассмотрим следующую продукцию и правило: ПРОДУКЦИЯ СЕМАНТИЧЕСКОЕ ПРАВИЛΠŠ— Е! + Т Е.уа1 = Е2.уа! + Т.га! В каждом узле Х, помеченном Е, с дочерними узлами, соответствующими телу этой продукции, синтезируемый атрибут уа1 в 1У вычисляется с использованием значений Ра1 в двух дочерних узлах, помеченных Е и Т.
Таким образом, часть графа зависимостей для каждого дерева разбора, в котором используется эта продукция, выглядит так, как показано на рис. 5.6. По соглашению ребра дерева разбора будут изображаться пунктирной, а ребра графа зависимостей — сплошной линией. и Е~ ее! Т еа! Рис. 5.б. Е.еа! синтезируется нз Е2.яа1 и Тяа1 Пример 5.5. Пример полного графа зависимостей приведен на рис.
5.7. Узлы графа зависимостей, представленные числами от ! до 9, соответствуют атрибутам в аннотированном дереве разбора на рис. 5.5. Т 9 ке! Р 3 еа! йаз 1 2ехеа! ы и Йял 2 2ехеа! Рис. 5.7. Граф зависимостей для аннотированного дерева разбора, представленного на рис. 5.5 Узлы ! и 2 представляют атрибут 1ех»а1, связанный с двумя листьями с метками й!й1К Узлы 3 и 4 представляют атрибут уа1, связанный с двумя узлами с метками Е.
Ребра в узел 3 из ! и в узел 4 из 2 получаются из семантического правила, определяющего Е.уа! через еИйзча1ехга1. В действительности Е.иа! равно й!й!г.!ех»а1, но ребро представляет зависимость, а не равенство. 393 5.2. Порядок вычисления в СУО Узлы 5 и 6 представляют наследуемый атрибут Т'лпп, связанный с каждым появлением нетерминала Т'. Причиной наличия ребра из 3 в 5 служит правило Т'.1пп = г.га1, определяющее Т'йпп в правом дочернем узле корня с использованием значения Г.га! в левом дочернем узле. Имеются также ребра в узел 6 из узлов 5 (атрибут Т'йпп) и 4 (атрибут 7 яа!), поскольку указанные значения перемножаются для получения атрибута !пй в узле 6.
Узлы 7 и 8 представляют синтезируемый атрибут луп, связанный с вхождениями Т'. Ребро из узла 6 в узел 7 связано с семантическим правилом Т'луп = Т'йпп, назначенным продукции 3 на рис. 5.4. Ребро из узла 7 в узел 8 связано с семантическим правилом, назначенным продукции 2. Наконец, узел 9 представляет атрибут Тла1. Ребро из узла 8 в узел 9 вызвано семантическим правилом Тла! = Т'луп, связанным с продукцией 1. а 5.2.2 Упорядочение вычисления атрибутов Граф зависимостей определяет возможные порядки вычисления атрибутов в различных узлах дерева разбора. Если граф зависимостей имеет ребро из узла М в узел Ю, то атрибут, соответствующий М, должен быть вычислен до атрибута !У.
Таким образом, допустимыми порядками вычисления атрибутов являются последовательности узлов 1УП Хз,..., 1Уь, такие, что если в графе зависимостей имеется ребро от Х; к 1У1, то ( < т1 Такое упорядочение графа зависимостей выстраивает его узлы в линейном порядке и называется топологической сортировкой графа. Если в графе имеется цикл, топологическая сортировка такого графа невозможна, а значит, невозможно и вычисление СУО для данного дерева разбора. Если циклов нег, то существует как минимум одна топологическая сортировка. Чтобы понять, почему это так, убедимся, что в графе без циклов всегда имеется узел, в который не входит ни одно ребро. Если бы это было не так, то, переходя по входящим ребрам от предшественника к его предшественнику, мы бы в конечном счете попали в узел, в котором уже бывали, т.е.
обнаружили бы цикл. Сделаем узел без входящих в него ребер первым в топологическом порядке, удалим его из графа зависимостей и повторим тот же процесс с оставшимися узлами. Пример 5.6. Граф зависимостей на рис. 5.7 не имеет циклов. Одной из топологических сортировок является порядок, в котором пронумерованы узлы: 1, 2,..., 9. Заметим, что все ребра графа идут из узла с меньшим номером в узел с большим номером, так что данный порядок определенно является топологической сортировкой. Имеются и другие топологические сортировки, например 1, 3, 5, 2, 4, б, 7, 8,9. а 394 Глава 5.
Синтаксически управляемая трансляция 5.2.3 Я-атрибутные определения Как упоминалось ранее, для заданного СУО очень трудно сказать, существует ли дерево разбора, граф зависимостей которого содержит циклы. На практике трансляция может быть реализована с использованием классов СУО, для которых гарантированно существует порядок вычислений атрибутов, поскольку они не допускают наличия графов зависимостей с циклами. Два класса, рассматриваемых в этом разделе, могут быть эффективно реализованы в связи с нисходящим и восходящим синтаксическим анализом.
Первый из этих классов определяется следующим образом. ° СУО является Я-атрибутным, если все его атрибуты синтезируемые. Пример 5.7. СУО на рис. 5.1 является примером Б-атрибутного определения. Каждый из атрибутов Е яа1, Ела1, Тла1 и Ема1 является синтезируемым. о Когда СУО является Я-атрибутным, его атрибуты могут вычисляться в любом восходящем порядке узлов в дереве разбора. Зачастую особенно просто вычислить атрибуты путем обхода дерева разбора в обратном порядке и вычисления атрибутов в узле Х, когда обход покидает узел последний раз, т.е. если применить определенную ниже функцию рол1оп1ег к корню дерева разбора (см. также врезку "Обходы в прямом и обратном порядке" из раздела 2.3.4): рол1оЫег (Х) 1 1ог ( каждый дочерний узел С узла Х, начиная слева) рол1оп1ег (С); Вычислить атрибуты, связанные с узлом Х; Я-атрибутные определения могут быть реализованы во время нисходящею синтаксического анализа, поскольку нисходящий синтаксический анализ соответствует обходу в обратном порядке.
В частности, обратный порядок обхода в точности соответствует порядку, в котором ЬК-синтаксический анализатор сворачивает тела продукций в их заголовки. Этот факт будет использован в разделе 5.4.2 для вычисления синтезируемых атрибутов и сохранения их в стеке в процессе 1.К- синтаксического анализа без явного создания узлов дерева разбора. 5.2.4 Е-атрибутные определения Второй класс СУО называется Т;атрибутнычи определениями. Идея, лежащая в основе этого класса, заключается в том, что ребра графа зависимостей между атрибутами, связанными с телом продукции, идут только слева направо, но не справа налево (отсюда и название — "1.-атрибутный"). Точнее, каждый атрибут должен быть либо 395 5.2.
Порядок вычисления в СУО 1. синтезируемым, либо 2. наследуемым, но при выполнении определенных ограничивающих правил. Предположим, что имеется продукция А — ХгХз... Х„и что существует наследуемый атрибут Х,.а, вычисляемый при помощи правила, связанного с данной продукцией. Тогда это правило может использовать только а) наследуемые атрибуты, связанные с заголовком А; б) наследуемые либо синтезируемые атрибуты, связанные с вхождениями символов Хы Хз,... Х, г, расположенных слева от Х,; в) наследуемые либо синтезируемые атрибуты, связанные с вхождениями самого Х,, но только таким образом, что в графе зависимостей, образованном атрибутами этого Х;, не имеется циклов. Пример 5.8. СУО на рис, 5А является ).-атрибутным. Чтобы увидеть, почему это так, рассмотрим семантические правила для наследуемых атрибутов, которые для удобства повторим еще раз: ПРОДУКЦИЯ СЕМАНТИЧЕСКОЕ ПРАВИЛО Т вЂ” Р' Т' Т'лпЬ = Р'ла) Т~ — эГ Тг Т.,'лпЬ = Т'лпЬ х Г.га) Первое из этих правил определяет наследуемый атрибут Т'лпЬ, использующий только Гла1, причем, как и требуется, Ь' находится в теле продукции слева от Т'.
Второе правило определяет Т,'лпЬ с использованием наследуемого атрибута Т'лпЬ, связанного с заголовком, и Р.га1, где Г располагается слева от Тг в теле продукции. В каждом из этих случаев правила используют информацию "сверху или слева", как и требуется определением класса. Остальные атрибуты синтезируемые. Следовательно, рассмотренное СУО является Ь-атрибутным. и Пример 5.9. Любое СУО, содержащее следующие продукции и правила, не мо- жет быть 1 -атрибутным: ПРОДУКЦИЯ СЕМАНТИЧЕСКИЕ ПРАВИЛА А- ВС А.а = В.Ь Вл' = г'1С.с, А.я) Первое правило, А.в = В.Ь, является корректным как для Б-атрибутного, так и для 1.-атрибутного СУО.
Оно определяет синтезируемый атрибут А.в с использованием атрибута в дочернем узле (т.е. символа в теле продукции). Второе правило определяет наследуемый атрибут Вл', так что СУО, в целом, не может быть 5-атрибутным. Далее, хотя правило и корректно, СУО не может 396 Глава 5. Синтаксически управляемая трансляция быть Ь-атрибутным, поскольку в определении Вл' участвует С.с, а С находится справа от В в теле продукции. Чтобы в Ь-атрибутном СУО могли использоваться атрибуты из братских узлов, они должны располагаться слева от символа, для которого определяется рассматриваемый атрибут. и 5.2.5 Семантические правила с контролируемыми побочными действиями На практике трансляция включает побочные действия: настольный калькулятор может выводить результат вычисления, генератор кода может вносить тип идентификатора в таблицу символов.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
