А.В. Ахо, М.С. Лам, Р. Сети, Дж. Д. Ульман - Компиляторы - принципы, технологии и инструментарий (1114947), страница 101
Текст из файла (страница 101)
Заметим, что реализация цикла иЫ(е на рис. 6.35, в имеет два ветвления на итерацию: одно — для входа в тело цикла из условия В, второе — для возврата к коду В. В результате обычно более предпочтительной является реализация и Ьйе (В) Я, как если бы это была конструкция (('(В) 1гереат Я ппй(! (В)). Приведите схему кода для такой трансляции и измените соответствующим образом правила на рис.
6.36. ! Упражнение 6.6.3. Предположим наличие оператора "исключающего ИЛИ" (который возвращает значение (гие тогда и только тогда, когда ровно один нз двух его аргументов равен пае). Напишите для такого оператора правила в стиле рис. 6.37. Упражнение 6.6.4. Транслируйте следующие выражения с использованием схе- мы трансляции с устранением переходов из раздела 6.6.5: а) 1й (а==Ь аа с==с! (! е==й) х == 1; б) Ы (а==Ъ (! с==с! (! е==й) х == 1р х == 1; в) 1й (а==Ъ аа с==с! йй е==й) Упражнение 6.6.5. Разработайте схему трансляции на основе синтаксически уп- равляемых определений, приведенных на рис. 6.36 и 6.37.
Упражнение 6.6.6. Адаптируйте семантические правила, представленные на рнс. 6.36 и 6.37, так, чтобы они допускали "проваливание" управления, используя правила, аналогичные представленным на рис. 6.39 и 6.40. ! Упражнение 6.6.7. Семантические правила для инструкций в упражнении 6.6.6 генерируют излишние метки. Модифицируйте правила, представленные на рис.
6.36, так, чтобы метки создавались по мере необходимости, с использованием специальной метки с(е)ег еИ, означающей, что метка пока что не была создана. Ваши правила должны генерировать код, подобный коду из примера 6.2!. !! Упражнение 6.6.8. В разделе 6.6.5 говорилось об использовании кода с "проваливанием" для минимизации переходов в генерируемом промежуточном коде. Однако при этом не использовались возможности замены условий на обратные, например замены И а < Ь досо 11, добро !.з фрагментом Н а >= 504 Глава 6. Генерация промежуточного кода Ь допо !з! до~о !.и Разработайте СУО, которое при необходимости исполь- зует преимущества такой замены. 6.7 Обратные поправки Ключевая проблема при генерации кода для булевых выражений и инструкций потока управления заключается в соответствии команд перехода целевым меткам.
Например, трансляция булева выражения В в зб (В) В содержит переход в случае ложного значения В к команде, следующей за кодом Я. При однопроходной трансляции В должно быть транслировано до того, как будет рассматриваться Я. Что в таком случае должно быть указано в качестве целевой метки команды до~о, которая выполняет переход через весь код Я? В разделе 6.6 мы решали эту задачу путем передачи меток в качестве наследуемых атрибутов в место, где генерируются соответствующие команды переходов.
Однако в таком случае для связывания меток с адресами требуется дополнительный проход. В этом разделе рассматривается дополнительный метод обратньп поправок (Ьасйра1сй|пд), в котором списки переходов передаются как синтезируемые атрибуты. В частности, при генерации перехода целевая метка временно остается неизвестной.
Каждый такой переход помещается в список переходов, метки которых будут указаны после того, как эти метки смогут быть определены. Все переходы в одном списке имеют одну и ту же целевую метку. 6.7.1 Однопроходная генерация кода с использованием обратных поправок Метод обратных поправок может использоваться для генерации кода булевых выражений и инструкций потока управления за один проход. Генерируемые нами трансляции будут иметь тот же вид, что и в разделе 6.6, за исключением работы с метками. В этом разделе для работы с метками кода с переходами для булевых выражений используются синтезируемые атрибуты ггие!!яг и !и!зе!!зп В частности, В.ггие!!тц представляет собой список команд условного и безусловного перехода, в которые должна быть вставлена метка, которой передается управление при истинности В.
Аналогично В !и!зе!!з! представляет собой список команд перехода, которые в конечном итоге получат метку для передачи управления при ложности В. После генерации кода В переходы к истинному и ложному выходам остаются незавершенными, с незаполненными полями меток. Эти незавершенные команды перехода помещаются в списки, на которые указывают В.ггпе!!з! и В./а!зе!!яп Аналогично инструкция Я имеет синтезируемый атрибут Я.лех!!!зд представляюший собой список переходов к команде, идущей непосредственно за кодом Я. 505 6.7. Обратные поправки Для определенности мы генерируем команды в виде массива команд, и метки представляют собой индексы этого массива.
При работе со списками переходов используются три функции. 1, еаЛе!Ьг (г) создает новый список, состоящий только из 1, индекса команды в массиве. Функция возвращает указатель на вновь созданный список. 2, тыве(ры рз) объединяет списки, на которые указывают р1 и рз, и возвращает указатель на объединенный список. 3. ЛасЛри1сЛ (р,1) вставляет г в качестве целевой метки в каждую команду списка, на который указывает р. 6.7.2 Обратные поправки для булевых выражений Теперь построим схему трансляции, пригодную для генерации кода для булевых выражений в процессе восходящего синтаксического анализа.
Маркер-нетерминал М заставляет семантическое действие получить в необходимый момент индекс очередной генерируемой команды. Грамматика выглядит следующим образом:  — В1 ~~М Вз ~ В1 ЙЛ: М Вз 1!В1 ~ (В1) ! Я, ге1 Ез' ,~гце ~ ~Гане ЛХ Схема трансляции представлена на рис.
6.43. Рассмотрим семантическое действие 1 продукции  — В~ ~~М Вз. Если В1 истинно, то истинно также н значение В в целом, так что переходы В1лгие1Ьг становятся частью списка Влгие1Ьг. Если В1 ложно, следует выполнить проверку Вз, так что целевой меткой переходов В1.1аЬе1Ьг должно быть начало кода Вз. Эта целевая метка получается с помощью маркера-нетерминала М. Этот нетерминал в качестве синтезируемого атрибута Мллиг дает индекс очередной команды непосредственно перед тем, как начнется генерация кода для Вз. Чтобы получить этот индекс, мы связываем с продукцией М вЂ” е семантическое действие (М.1лхг = пехгтзгг;).
Переменная пехг1пзгг хранит индекс очередной команды. Это значение будет вставлено в команды перехода из В1~аЬе1Ьг (т.е. каждая команда из списка В1./аЬе1Ь1 получит в качестве целевой метки значение Млтгг), когда мы достигнем конца продукции  — В1~~М Вз. Семантическое действие 2 продукции  — В1ййМ Вз аналогично действию 1. Действие 3 для  — !В1 меняет местами списки для ложного и истинного значений. Действие 4 просто игнорирует скобки.
Для простоты семантическое действие 5 генерирует две команды, условного и безусловного переходов. Ни у одной из них не заполняется поле целевой метки. Эти команды помещаются в новые списки, на которые указывают В.~псе1Ьг и В~аЬе1Ьг соответственно. 506 Глава 6. Генерация промежуточного кода 1)  — В( ! ! М Вз ( Ьас!(ра(сй(В( ~а!ее!и(, Мйпз(«); В.(гие!и( = те«де(В(.ат(е!и(, Вз.(гиейз(); ВГа!зе!Ы = Вэба(зейз(; ) 2)  — ~ В( 3(!(с М Вз ( Ьас((ра(сй(В(л«ие1Ь(, М.(ги(г); В (гпе!Ы = Вз.(гие!Ы; В~а!кейз( = те(уе(В(,!аЬейз(, Вз,!а!зейз(); ) ( В.(гае!и( = В, !аЬейа(; В~а!зе1и( = В(лгие1и(; ) в (в 4)  — (В() ( В.(гие1и( = В,.(«не!и(; В (аЬейз( = Ви(а!зе!и(; ) ( В.
((т(ейз( = та((ейз((пел((пз(г); В(а!зе1и( = та((е1и((пехй(и(г + 1); етй('1й' Е(.а(((! ге1лр Ез.ай! 'досо '); ет!(('дог.о '); ) 5) В- Е(ге1Ез ( В (гпе1и( = таке!и((пег(!пз(г); ет((('досо '); ) 6)  — (гце ( В~аЬе!Ы = та((е1и((пех(((и(г); ет!(('до1о '); ) 7) В- 1а1яе ( Мйпг(г = пел((пз(г; ) Рис. 6.43. Схема трансляции для булевых выражений 8) М- е Пример 6.24.
Вновь рассмотрим выражение х < 100 !! х > 200 йа х 1= у 100: 1й х < 100 до~о 101: дог.о Аннотированное дерево разбора для этого выражения показано на рис. 6.44. Для удобочитаемости атрибуты (гие!и(, !а!зейз( и !Уи(«представлены их начальными буквами. Действия выполняются в процессе обхода дерева в глубину. Поскольку все действия находятся на правых юнцах продукций, они могут выполняться вместе со свертками в процессе восходящего разбора. При свертке х < 100 в В в соответствии с продукцией 5 генерируются две команды: 507 6.7.
Обратные поправки Вх = (100, ! 04) ВУ= (103, 105) М.)= 102 ВУ= (101) ! ВУ= ( 105, 105) г < 200 аа яг! = 104 В.! = (102) В.! = (104) ВУ= (105) ВУ= (105) х > 200 Рис. 6.44. Аннотированное дерево разбора для х ( 100 1! х > 200 йй х) = у (Команды нумеруются начиная с произвольно выбранного индекса 100.) Маркернетерминал М в продукции  — В! (( М В2 записывает значение псх)!пя)г, которое в настоящий момент равно 102. Свертка х > 200 в В в соответствии с продукцией 5 генерирует команды 102: зх х > 200 доСо 103: добро Подвыражение х > 200 соответствует В! в продукции  — В! ЙЙ М В2. Маркер-нетерминал М записывает текущее значение иехпаяо., которое в этот момент равно 104.
Свертка х ! = у в В в соответствии с продукцией 5 генерирует 104: зй х(=у добро 105: !Зос.о Теперь можно выполнить свертку в соответствии с продукцией  — В! Йй М В2. Соответствующее семантическое действие вызывает Ьас/сра)сЬ(В!.)гие)!51, М.!пя)г) для связывания выхода из В! по значению "истинно" с первой командой В2. Поскольку список В).)!2)е1Ь! равен 1102), а М.!лз)г равно 104, этот вызов Ьас21ра)сЬ вносит метку 104 в команду 102.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
