А.В. Ахо, М.С. Лам, Р. Сети, Дж. Д. Ульман - Компиляторы - принципы, технологии и инструментарий (1114947), страница 83
Текст из файла (страница 83)
1. Два смежных бокса, первый из которых, Вы находится слева от второго, Вз. 2. Бокс и бокс нижнего индекса. Второй бокс имеет меньший размер и находится ниже и правее первого бокса. 417 5.4. Синтаксически управляемые схемы трансляции точками. Базовая линия индекса (на рисунке — базис бокса, содержащего 1) находится ниже основной базовой линии. в) Бокс имеет высоту (Ье)й)зг), представляющую собой расстояние от базовой линии до вершины бокса. Высота бокса В определяется его синтезируемым атрибутом ВЖ. г) Бокс имеет глубину (оер1п), представляющую собой расстояние от базовой линии до дна бокса. Глубина бокса В определяется его синтезируемым атрибутом В.др. СУО на рис.
5.25 содержит правила для вычисления кегля, высоты и глубины боксов. Продукция ! используется для назначения атрибуту В.ра начального значения кегля 10. Рис. 5.25. СУО для текстовых боксов Продукция 2 обрабатывает смежные боксы. Кегль копируется вниз по дереву разбора, т.е. два подбокса основного бокса наследуют тот же кегль, что и у большего бокса.
Высота и глубина вычисляются вверх по дереву при помощи функции поиска максимального значения, т.е. высота большего бокса представляет собой максимальную из высот своих двух компонентов; то же касается и глубины бокса. Продукция 3 обрабатывает индексы, что является немного более сложной задачей, чем предыдущая. В этом очень упрощенном примере считается, что кегль ин- 418 декса составляет 70',4 от родительского. Реальность существенно более сложная, поскольку индексы не могут уменьшаться до бесконечности; на практике после нескольких уровней размеры индексов перестают уменьшаться.
Далее, в примере полагается, что базовая линия бокса индекса опущена на 25'.4 от размера родителя; ситуация в реальности существенно сложнее, чем зта упрощенная модель. Продукция 4 копирует атрибуты при использовании скобок. Наконец, продукция 5 обрабатывает листья, представляющие боксы текста. Здесь опять же реальная ситуация весьма сложна, так что в СУО показаны две не определенные функции яегН~ и дегВР, которые работают с таблицами, указывающими для каждого шрифта максимальную высоту и максимальную глубину любого символа текстовой строки. Сама по себе строка передается как атрибут!ехуа! терминала гех1. Наша последняя задача состоит в преобразовании СУО в СУТ, следуя правилам для 1.-атрибутных СУО, к каковым относится и СУО на рис.
5.25. Соответствующая СУТ показана на рис. 5.26. Для большей удобочитаемости ставшие весьма длинными тела продукций разбиты на несколько строк. Тело каждой продукции состоит из всех строк, расположенных выше заголовка следующей продукции. и ДейстВиЯ ПРОДУКЦИЯ В.рз = 10; ) !) В В В.рз; ) В.рз; ) тах(В1.Ь|, Вг.Ь|); тах(В1.др, Вг.йр); ) 2) В в, Вг В.рз; ) 0.7 х В.рз; ) тах(в~.йб Вг.М вЂ” 0.25 х В.рз)' тах(В1.ЫР, Вгл1р + 0.25 х В.рз)' ) 3) В В1 впЬ Вг В.рз; ) в .)и; В,.1р; ) 4)  — ( в,) ( Вырз В.Ь| в.лр В.Ь| в.ар Язву (В.рз, 1ех1.
1ех1 а1); 8еЮр (В.рз, техт.)ехга1); ) 5) В -~ Фехт Рис. 5.26. СУТ для текстовых боксов ( Впрз 1Вгрз В.Ы В.1р ( Вырз )вгрз ( В.Ь| в.ар Глава 5. Синтаксически управляемая трансляция 5.4. Синтаксически управляемые схемы трансляции 419 Следующий пример связан с простой инструкцией и Ь1!е и генерацией промежуточного кода для данного типа инструкций. Промежуточный код рассматривается как атрибут со строковым значением. Позже мы познакомимся с методами, которые включают запись частей строковых атрибутов в процессе синтаксического анализа, что позволяет избегать копирования длинных строк для построения еше более длинных строк.
Такого рода метод использовался в примере 5.17, при генерации постфиксной записи инфиксного выражения "на лету" вместо вычисления атрибута. Однако пока что будем создавать строковые атрибуты путем конкатенации. Пример 5.19. В этом примере нам достаточно одной продукции: Я вЂ” зги!1е (С) Я~ Здесь Я вЂ” нетерминал, который генерирует все виды инструкций, вероятно, включая условные конструкции, присваивания и др. В нашем примере С представляет собой условное выражение — булево выражение, которое после вычисления принимает значение 1гие или Га!зе. В этом примере единственный объект, который мы будем генерировать, — это метки. Все прочие команды промежуточного кода считаются генерируемыми не показанными частями СУТ. В частности, мы генерируем явные команды вида 1аЬе1 Х, где Т вЂ” идентификатор, указывающие, что Т вЂ” метка следующей за ней команды.
Предполагается, что промежуточный код подобен рассматривавшемуся в разделе 2.8.4. Конструкция иИе работает следующим образом. Сначала вычисляется условное выражение С. Если оно истинно, управление передается в начало кода для ЯП если оно ложно, управление передается коду, следующему за конструкцией вИе. Код Я~ должен по завершении выполнения передать управление в начало конструкции иЫ!е, к коду, который вычисляет значение С и который не показан на рис. 5.27.
Я вЂ” ~ зтЬ11е(С) Я~ Ы = лен(,); Т2 = лен(); Я~ шея! = з 1; С.)л1зе = Я.лехд С.лие = Т2; Я.сос!е = 1аЬе1 11 Ы (1 С.сос(е )~ 1аЬе1 ~~ Л2 1( Я~.сос(е Рис. 5.27. СУО для конструкции ч Ие Для генерации корректного промежуточного кода используются следующие атрибуты. 420 Глава 5. Синтаксически управляемая трансляция 1. Наследуемый атрибут Я.лехт помечает начало кода, который должен быть выполнен после завершения Я.
2. Синтезируемый атрибут Я.соНе представляет собой последовательность шагов промежуточного кода, которая реализует инструкцию Я и завершается переходом к метке Ялехь 3. Наследуемый атрибут С.а ие помечает начало кода, который должен быть выполнен, если значение С истинно. 4. Наследуемый атрибут С.1а1зе помечает начало кода, который должен быть выполнен, если значение С ложно.
5. Синтезируемый атрибут С.сос1е представляет собой последовательность шагов промежуточного кода, которая реализует условие С и переходит в зависимости от вычисленного значения С либо к метке Сагие, либо к метке С~а1зе. СУО, вычисляющее эти атрибуты конструкции юЫ!е, приведено на рис. 5.27.
Некоторые моменты этого СУО требуют пояснений. ° Функция лен генерирует новые метки. ° Переменные Ы н Л2 хранят метки, которые потребуются в генерируемом коде. Л1 представляет начало кода конструкции тгЫ!е, и код Я~ по окончании работы должен выполнять переход к ней. Именно поэтому выполняется присваивание Ы атрибуту Яз яехп Ь2 представляет начало кода Я~ и становится значением атрибута Сагие, поскольку именно сюда выполняется переход, если вычисленное условие истинно. ° Обратите внимание, что С.1а!зе устанавливается равным Я.лехд поскольку, когда условие ложно, выполняется код, следующий за кодом 5. ° Символ ~! используется для обозначения конкатенации фрагментов промежуточного кода.
Таким образом, значение Я.соНе начинается с метки Ы, за которой следуют код условия С, другая метка Ь2 и код Яи Данное СУО является 1.-атрибутным. При его преобразовании в СУТ остается единственный вопрос — как обрабатывать метки Л1 и Л2, представляющие собой переменные, а не атрибуты? Если рассматривать действия как фиктивные нетерминалы, то такие переменные могут трактоваться как синтезируемые атрибуты фиктивных нетерминалов. Поскольку Ы и Ь2 не зависят от каких-либо других атрибутов, они могут быть назначены первому действию продукции. В результате получается СУТ со встроенными действиями, реализующая рассмотренное 1.- атрибутное определение и показанная на рис. 5.28.
и 5А. Синтаксически управляемые схемы трансляции 421 Я вЂ” ч'Ь!!е ( ( Ы = пеи (); Т2 = пет()' С./аЬе = Я.пехб Сагие = Т2; ) С ) ( Я1,пехг = Т1; ) Я1 ( Я.сойе = !аЬе! '8 Т1 !! С.сойе (! !аЬе! '8 Т 2 8 Яысойе; ) Рис. 5.28. СУТ для конструкции и41!е 5.4.6 Упражнения к разделу 5.4 Упражнение 5.4.1. В разделе 5.4.2 упоминалось, что из 1,К-состояния в стеке синтаксического анализатора можно вывести, какой именно грамматический символ представлен этим состоянием. Каким образом можно это сделать? Упражнение 5.4.2. Перепишите СУТ А — А (а) В ~ А В (Ь) ! Π — В (с) А$ВА (й) /1 так, чтобы лежащая в ее основе грамматика перестала быть леворекурсивной.
Здесь а, 6, с и с! — действия, а О и 1 — терминалы. ! Упражнение 5.4.3. Приведенная ниже СУТ вычисляет значение строки из О и 1, рассматривая ее как положительное бинарное число.  — В1 О (В га1 = 2 х Выса!) В1 1 (В га! = 2 х В|.та! + 1) 1 (В га1 = 1) Перепишите эту СУТ так, чтобы лежащая в ее основе грамматика перестала быть леворекурсивной, но вычисленное значение В га1 для входной строки оставалось тем же.
! Упражнение 5.4.4. Разработайте 1.-атрибугное СУО, аналогичное СУО из примера 5.!О, для приведенных ниже продукций, каждая из которых представляет собой знакомую конструкцию управления потоком, имеющуюся в языке программирования С. Вам может потребоваться сгенерировать трехадресную команду для перехода к конкретной метке  — в этом случае генерируйте команду иоана 1.
а) Я вЂ” П (С) Я1 е!яе Яз б) Я вЂ” по Я1 иЬ!!е (С) и) Я вЂ” ~ ( Ь ); т — >ТЯ Обратите внимание на то, что любая инструкция может содержать переход из средины к следующей инструкции, так что просто по порядку сгенерировать код для каждой инструкции недостаточно. 422 Глава 5.
Синтаксически управляемая трансляция Упражнение 5.4.5. Преобразуйте каждое из ваших СУО из упражнения 5.4.4 в СУТ, как это было сделано в примере 5.19. Упражнение 5.4.6. Модифицируйте СУО на рнс. 5.25 так, чтобы оно включало сннтезируемый атрибут Взе, длину бокса. Длина двух смежных боксов равна сумме их длин. Затем добавьте новые правила в соответствующие места СУТ на рис. 5.26. Упражнение 5.4.7. Модифицируйте СУО на рис.
5.25 так, чтобы оно включало надстрочные индексы, с использованием оператора яир между боксами. Если бокс Вз является надстрочным индексом бокса Вы то позиция базовой линии Вз находится на 0.6 кегля бокса В1 выше базовой линии бокса Вь Добавьте новую продукцию н правила в СУТ на рис. 5.26. 5.5 Реализация Е-атрибутных СУО Поскольку многие приложения трансляций используют 1.-атрибутные определения, в этом разделе мы рассмотрим их реализацию более подробно. Трансляция путем обхода дерева разбора осуществляется следующими методами. 1.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
