А.В. Ахо, М.С. Лам, Р. Сети, Дж. Д. Ульман - Компиляторы - принципы, технологии и инструментарий (1114947), страница 77
Текст из файла (страница 77)
Прн рассмотрении порядка вычислений атрибутов в разделе 5.2 мы позволим семантическим правилам вычислять произвольные функции, возможно, с побочными действиями. Я-атрнбутное СУО может быть естественным образом реализовано вместе с ЬК-синтаксическим анализатором. Фактически СУО на рис. 5.1 отображает гасо-программу, представленную на рис. 4.58, которая иллюстрирует трансляцию во время синтаксического анализа. Отличие заключается в том, что в правиле для продукции 1 Хасс-программа в качестве побочного действия выводит Е из! вместо определения значения атрибута Ьюа1.
СУО без побочных эффектов иногда называют атрибутной грамматикой. Правила атрибутной грамматики определяют значения атрибутов через значения других атрибутов и констант и не выполняют никаких иных действий. 387 5.1. Синтаксически управляемые определения 5.1.2 Вычисление СУО в узлах дерева разбора Визуализировать трансляцию, определяемую СУО, может помочь работа с деревом разбора, хотя в действительности транслятор может его и не строить.
Представим, что правила СУО применяются путем построения дерева разбора с последующим использованием этих правил для вычисления атрибутов в каждом узле дерева. Дерево разбора с указанием значений его атрибутов называется аннотированным деревом разбора. Каким образом строится аннотированное дерево разбора? В каком порядке вычисляются его атрибуты? Перед тем как вычислять атрибут в узле дерева разбора, следует вычислить все атрибуты, от которых может зависеть вычисляемое значение. Например, если все атрибуты являются синтезируемыми, как в примере 5.1, то, прежде чем приступить к вычислению значения атрибута на! в узле, требуется вычислить атрибуты на! во всех его дочерних узлах.
Синтезируемые атрибуты можно вычислять в произвольном восходящем порядке, таком как обратный порядок обхода дерева разбора; вычисление Я-атрибутных определений рассматривается в разделе 5.2.3. Для СУО с атрибутами обоих типов — наследуемыми и синтезируемыми — не существует гарантии наличия даже одного порядка обхода для вычисления всех атрибутов в узлах дерева разбора.
Рассмотрим, например, нетерминалы А и В с синтезируемым и наследуемым атрибутами А.в и В.з соответственно, а также следующую продукцию и правила; Продукция СемАнтические пРАВилА А.в = В.т А- В Вл' = А.в+ 1 Данные правила циклические; невозможно вычислить ни А.в в узле зУ, ни Вл' в дочернем по отношению к )т' узле, не зная значение другого атрибута. Циклическая зависимость А.в и В.т' в некоторой паре узлов дерева разбора проиллюстрирована на рис. 5.2.
Задача поиска циклов в дереве разбора для данного СУО вычислительно достаточно сложна . К счастью, существуют подклассы СУО, для которых можно гарантировать существование порядка вычисления (этот вопрос рассматривается в разделе 5.2). Пример 5.2. На рис. 5.3 показано аннотированное дерево разбора для входной строки 3 * 5+ 4 и, построенное с применением грамматики и правил, представленных на рис. 5.1. Предполагается, что значения !еоа! предоставляются лексическим анализатором.
Каждый из узлов для нетерминалов имеет атрибут на1, Не вдаваясь в детали, отметим, что хотя данная задача и разрешима, онв не может быть решена алгоритмом с нояиномияяьным временем работы !деже если Р = АгР) в силу зясноненнивяьной сложности. 388 Глава 5. Синтаксически управляемая трансляция Рис. 5.2. Циклическая зави- симость атрибутов А.е и В.г' друг от друга вычисляемый в восходящем порядке; на рисунке показаны значения атрибутов в каждом узле дерева разбора. Например, к узлу, среди дочерних узлов которого имеется узел, помеченный *, после вычисления значений атрибутов Тла! = 3 и Е.га! = 5 в его первом и третьем дочернем узлах применяется правило, гласящее, что Т.га! является произведением указанных значений, или 15.
Т.еа! = 4 Ееа/= !5 е.еа/ = 4 1 4/я/К/ехеа/ = 4 Т еа! = 3 ! Деа! =5 ! а!я/К/ехеа! = 5 Ела! = 3 4!Вче !ехеа! = 3 Рнс. 5.3. Аннотированное дерево разбора для 3 * 5+ 4 а Наследуемые атрибуты полезны в случае, когда структура дерева разбора "не соответствует" абстрактному синтаксису исходного кода. Приведенный далее пример показывает, как наследуемые атрибуты могут использоваться для преодоления такого несоответствия, возникшею вследствие того, что грамматика разрабатывалась для синтаксического анализа, а не для трансляции.
389 5,1. Синтаксически управляемые определения Пример 5.3. СУО на рис. 5.4 вычисляет выражения наподобие 3 *5 и 3 а 5 * 7. Нисходящий синтаксический анализ входной строки 3*5 начинается с продукции Т вЂ” Г Т. Здесь г генерирует цифру 3, но оператор * генерируется нетерминалом Т'. Таким образом, левый операнд 3 находится в дереве разбора в другом поддереве, не в том, в котором находится оператор *. Следовательно, для передачи операнда оператору используются наследуемые атрибуты. Рис. 5.4. СУО на основе грамматики, пригодной для нисходящего синтаксического анализа Грамматика в этом примере представляет собой фрагмент нелеворекурсивной версии знакомой нам грамматики выражений; мы использовали такую грамматику в примере, иллюстрирующем нисходящий синтаксический анализ (см.
раздел 4.4). Каждый из нетерминалов Т и г имеет синтезируемый атрибут га(; терминал Жйй имеет синтезируемый атрибут!ехга!. Нетерминал Т' имеет два атрибута: наследуемый атрибут (лл и синтезируемый атрибут гул. Семантические правила основаны на той идее, что левый операнд оператора * является наследуемым. Точнее, заголовок Т' продукции Т' — * г Т,' наследует левый операнд оператора * в теле продукции. У выражения х * у * г корень поддерева для *д * з наследует х.
Далее, корень поддерева *г наследует значение х * у, и так далее при наличии большего количества сомножителей в выражении. Когда все сомножители накоплены, результат передается назад по дереву с использованием синтезируемых атрибутов. Чтобы увидеть, как используются семантические правила, рассмотрим аннотированное дерево разбора для выражения 3 * 5 на рис.
5.5. Крайний слева лист дерева, помеченный йй(т, имеет значение атрибута (ехга( = 3, где 3 передается лексическим анализатором. Родительским узлом для него является узел продукции г — ййй. Единственное семантическое правило, связанное с этой продукцией, определяет, что Гл а( = ййй.(ехга(, равному 3. Во втором дочернем узле корня наследуемый атрибут Т'ллем определяется семантическим правилом Т'.тЬ = Ела(, связанным с продукцией 1. Таким образом, 390 Глава 5. Синтаксически управляемая трансляция =3 =!5 г,'лая =!5 Т,'.ьуа = !5 а!яв. !еаеа! = 3 деа!=5 йпь(ехеа! = 5 Рнс. 5.5, Аннотированное дерево разбора для выраже- ния 3 э 5 левый операнд оператора * — 3 — передается слева направо между дочерними узлами корня.
Продукция в узле для Т' — Т' — * Е Т,' !индекс 1 оставлен в аннотированном дереве разбора для того, чтобы различать два узла Т'). Наследуемый атрибут Т,'.!и!! определяется семантическим правилом Т!!.!и)! = Т!.!и!! х Е.га1, связанным с продукцией 2. При Т'.т!! = 3 и Г.уп! = 5 мы получаем Т,'.!л!! = 16. Узлу для Т,' соответствует продукция Т' — е. Семантическое правило Т'.зуп = Т!лп7е определяет значение Т~!.зул = 1б. Атрибут зуп в узлах для нетерминала Т' передает значение 15 вверх по дереву до узла для нетерминала Т, так что Тли! = !5. П а) (3 + 4) * (5 + 6) и; б) 1 е 2 э 3 э (4 + 5) и; в) (9 + 8 а (7 + 6) + 5) * 4 и. Упражнение 5.1.2.
Расширьте СУО на рис. 5.4 так, чтобы оно могло обрабатывать те же выражения, что и СУО на рис. 5.1. Упражнение 5.1.3. Повторите упражнение 5.!. ! с использованием СУО, постро- енного вами при решении упражнения 5.1.2. 5.1.3 Упражнения к разделу 5.1 Упражнение 5.1.1. Для СУО на рис. 5.1 постройте аннотированные деревья разбора для следуюших выражений: 391 5.2.
Порядок вычисления в СУО 5.2 Порядок вычисления в СУО Полезным инструментом для установления порядка вычисления атрибутов в конкретном дереве разбора является граф зависимостей. В то время как аннотированное дерево разбора показывает значения атрибутов, граф зависимостей помогает определить, каким образом эти значения могут быть вычислены. В этом разделе в дополнение к графам зависимостей мы определим два важных класса СУО: Б-атрибутные и более общие В-атрибутные СУО. Трансляции, определяемые этими двумя классами, хорошо согласуются с изучавшимися нами методами синтаксического анализа, и большинство трансляторов, встречающихся на практике, могут быть написаны так, чтобы соответствовать требованиям как минимум одного из упомянутых классов.
5.2.1 Графы зависимостей Граф зависимостей (дерепбепсу агар)з) изображает поток информации между экземплярами атрибутов в определенном дереве разбора; ребро от одного экземпляра атрибута к другому означает, что значение первого атрибута необходимо для вычисления второго. Ребра выражают ограничения, следующие из семантических правил. Вот более детальное описание графа зависимостей. ° Для каждого узла дерева разбора, скажем, узла, помеченного грамматическим символом Х, в графе зависимостей имеются узлы для каждого из атрибутов, связанных с Х.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
