А.В. Ахо, М.С. Лам, Р. Сети, Дж. Д. Ульман - Компиляторы - принципы, технологии и инструментарий (1114947), страница 98
Текст из файла (страница 98)
Поскольку сначала выполняется объединение, количество классов эквивалентности перед рекурсивной проверкой уменьшается, что гарантирует завершение работы алгоритма. Подстановка выражения вместо переменной реализуется путем добавления листа переменной в класс эквивалентности, содержащий узел этого выражения. 490 Глава 6. Генерация промежуточного кода Предположим, что либо т, либо н представляет собой лист дпя переменной. Предположим также, что этот лист помещен в класс эквивалентности с узлом, представляющим выражение с конструктором типа или фундаментальным типом. Тогда афпг! вернет представительный узел, который отражает этот конструктор типа или фундаментальный тип, так что переменная не может быть унифицирована с двумя разными выражениями.
а Пример 6.20. Предположим, что два выражения в примере 6.18 изначально представлены графом на рис. 6.33, где каждый узел принадлежит собственному классу эквивалентности. При вычислении алгоритмом 6.!9 ипф (1,9) выясняется, что узлы 1 и 9 представляют один и тот же оператор. Следовательно, выполняется обьединение 1 и 9 в один класс эквивалентности и вызываются ила(2, 10) и ипф (8, 14). Результатом вычисления ипф (1, 9) оказывается граф, ранее показанный на рис.
6.31. и Рнс. 6.33. Начальный граф, в котором каждый узел принадлежит собственному классу эквивалентности Если алгоритм 6.19 возвращает г ие, подстановку Я, которая выступает в роли унификатора, можно построить следующим образом. Для каждой переменной гз ДпЫ(гт) дает узел и, который является представителем класса эквивалентности гг. Выражение, представленное и, и есть Я(гг). Например, на рис. 6.31 видно, что представителем гтз является узел 4, который представляет гтг.
Представителем гть является узел 8, представляющий 11зг (аз). Окончательная подстановка приведена в примере 6.18. 6.5.6 Упражнения к разделу 6.5 Упражнение 6.5.1. В предположении, что функция н Ыеп на рис. 6.26 может работать с любым типом в иерархии на рис. 6.25, а, транслируйте приведенные ниже выражения (считаем, что с и с! имеют тип с!так, в и с — в!тогс, з и 3— хпт., а х — й1оас): а)х=в+ с б)1=а+с 491 б.б. Поток управления в)х = (в+ с) * (Г + с1) Упражнение 6.5.2.
Предположим, как в языке программирования Ада, что каждое выражение должно иметь единственный тип, но все, что можно вывести из подвыражений, — зто множество возможных типов. Иначе говоря, применение функции Е1 к аргументу Ез, представленное продукцией Š— Е~ (Ез), имеет связанное с ней правило Е.(уре = !1 ( для некоторого в из Ез.~уре в — ( принадлежит Е1 луре) Опишите СУО, которое определяет единственный тип каждого подвыражения путем использования атрибута (уре для восходящего синтеза множества возможных типов и по определении единственного типа всего выражения выполняет нисходящее определение атрибута итоне для типа каждого из подвыражений. 6.6 Поток управления Трансляция таких инструкций, как конструкции 1('-е!зе и ччЫ!е, связана с трансляцией булевых выражений.
В языках программирования булевы выражения часто используются для следующих целей. !. Изменение потока управления. Булевы выражения исгюльзуются в качестве условных выражений в инструкциях, которые изменяют поток управления. Значения таких булевых выражений неявно присутствуют в позиции, достигнутой программой.
Например, в 11(Е) Я выражение Е должно быть равно (гие, если достигнута инструкция о'. 2. Вычисление логических значений. Булево выражение может представлять ( ие нли Га(ве в качестве значений. Такие булевы выражения могут вычисляться по аналогии с арифметическими выражениями с использованием трехадресных команд с логическими операторами. Запланированное использование булевых выражений определяется нх синтаксическим контекстом. Например, выражение, следующее за ключевым словом К, используется для изменения потока управления, в то время как выражение в правой части присваивания используется для обозначения логического значения.
Такой синтаксический контекст может определяться несколькими способами: можно использовать два разных нетерминала, воспользоваться наследуемыми атрибутами или устанавливать флаг в процессе синтаксического анализа. В качестве альтернативы можно построить синтаксическое дерево и вызывать различные процедуры для двух различных использований булевых выражений.
492 Глава 6. Генерация промежуточного кода В этом разделе мы остановимся на использовании булевых выражений для изменения потока управления. Для ясности для этой цели мы введем новый нетерминал В. В разделе 6.6.6 будет рассмотрено, как компилятор может разрешить булевым выражениям представлять логические значения. 6.6.1 Булевы выражения Булевы выражения составлены из булевых операторов (которые будут обозначаться осот, ~~ и ! с помощью обозначений языка программирования С для операторов И, ИЛИ и НЕ соответственно), примененных к элементам, представляю|цим собой булевы переменные или выражения отношений.
Выражение отношения имеет вид Е1 ге! Ез, где Е1 и Ез — арифметические выражения. В этом разделе будут рассматриваться булевы выражения, генерируемые грамматикой  — В!!В ~ В агМа В !!В ! (В) ! Е ге! Е ) !гпе ~ Та)ае Для указания, какой нз шести операторов сравнения («,=, =, ! =, > или >=) представлен при помощи ге), будет использоваться атрибут ге!.ор. По привычке мы полагаем, что операторы ~~ и осот левоассоциативны и что у оператора ~~ приоритет меньше, чем у оператора Йос, приоритет которого, в свою очередь, меньше приоритета оператора !. Если для данного выражения В1 ~)Вз определено, что В1 равно ггие, то можно заключить без вычисления Вз, что все выражение равно ггие.
Аналогично, если в В1 !сй Вз В| равно ~а)зе, то значение всего выражения также равно /а)зе. Семантическое определение языка программирования указывает, должны ли вычисляться все части булева выражения. Если определение языка программирования допускает (илн требует) оставить часть логического выражения не вычисленной, то компилятор может оптимизировать вычисления булевых выражений путем вычисления только той части, которая достаточна для определения значения выражения в целом. Таким образом, в выражении наподобие В~!!Вз ни Вп ни Вз не обязаны вычисляться полностью. Если либо Вы либо Вз представляет собой выражение с побочным действием (напрнмер, содержит вызов функции, которая изменяет глобальную переменную), то может быть получен не тот результат, которого вы ожидаете.
6.6.2 Код сокращенного вычисления При сокращенных (в!топ-с)тсц)!) вычислениях булевы операторы 8сос, ~~ и ! транслируются в переходы. Сами операторы в коде отсутствуют; вместо этого значение булева выражения представлено в виде позиции в последовательности команд. 493 б.б. Поток управления Пример 6.21. Инструкция 1й ( х < 100 11 х > 200 ьь х 1= у ) х = 0; может быть транслирована в код, приведенный на рис.
6.34. В этой трансляции булево выражение истинно, если управление достигает метки Аз. Если выражение ложно, управление передается непосредственно к метке Лм минуя Лз и присваивание х = О, о хт х ( 100 алого Ьз тйта1ае х > 200 досо Ь1 1йта3ве х 1= у досо Ь1 1з. х = 0 Рис. 6.34. Кол сокращенных вычислений 6.6.3 Инструкции потока управления Рассмотрим теперь трансляцию булевых выражений в трехадресный код в контексте таких инструкций, как генерируемые следующей грамматикой: Я 1г (В) 51 Я вЂ” и (В) 51 е1яе Яа Я вЂ” ттй11е (В) 51 В этих продукциях нетерминал В представляет булево выражение, а нетерминал Я вЂ” инструкцию.
Приведенная грамматика обобщает рабочий пример выражения ттйяе из примера 5.19. В этом примере и В, и Я имели синтезируемый атрибут соде, который давал трансляцию в трехадресные команды. Для простоты мы строим трансляции В.сос1е и Я.сне с использованием синтаксически управляемых определений в виде строк. Семантические правила, определяющие атрибуты сог1е, могут быть реализованы также посредством построения синтаксических деревьев и генерацией кода в процессе обхода дерева, а также с использованием иных методов, рассмотренных в разделе 5.5. Трансляция !Г (В) 51 состоит из В.соЫе, за которым следует Япсог1е, как показано на рис. 6.35, а.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
