Теория и реализация языков программирования

         

Код правого поддерева Код левого


Код правого поддерева Код левого поддерева Op R+1, R


Рис. 9.9. 

где R - регистр, назначенный внутренней вершине, и операция Op, вообще говоря, не коммутативная (рис. 9.9, б);
  • если непосредственные потомки вершины не листья и метка правой вершины меньше метки левой вершины, то вершине соответствует код

    Код левого поддерева Код правого поддерева Op R, R+1 MOVE R+1, R



  • Последняя команда генерируется для того, чтобы получить результат в нужном регистре (в случае коммутативной операции ее операнды можно поменять местами и избежать дополнительной пересылки - рис. 9.9, а).

    Рассмотрим атрибутную схему, реализующую эти правила генерации кода (для большей наглядности входная грамматика соответствует обычной инфиксной записи, а не Лидер-представлению). В этой схеме генерация кода происходит не непосредственно в процессе обхода дерева, как раньше, а из-за необходимости переставлять поддеревья код строится в виде текста с помощью операции конкатенации. Практически, конечно, это нецелесообразно: разумнее управлять обходом дерева непосредственно, однако для простоты мы будем пользоваться конкатенацией.

    Листинг 9.1.

    (html, txt)

    Атрибутированное дерево для выражения A*B+C*(D+E) приведено на рис. 9.10. При этом будет сгенерирован следующий код:

    MOVE B, R1 MUL A, R1 MOVE E, R2 ADD D, R2 MUL C, R2 ADD R1, R2 MOVE R2, R1

    Приведенная атрибутная схема требует двух проходов по дереву выражения. Рассмотрим теперь другую атрибутную схему, в которой достаточно одного обхода для генерация


    Рис. 9.10. 

    программы для выражений с оптимальным распределением регистров [9].

    Пусть мы произвели разметку дерева разбора так же, как и в предыдущем алгоритме. Назначение регистров будем производить следующим образом.

    Левому потомку всегда назначается регистр, равный его метке, а правому - его метке, если она не равна метке его левого брата, и метке + 1, если метки равны. Поскольку более сложное поддерево всегда вычисляется раньше более простого, его регистр результата имеет больший номер, чем любой регистр, используемый при вычислении более простого поддерева, что гарантирует правильность использования регистров.

    Приведенные соображения реализуются следующей атрибутной схемой:

    Листинг 9.2.

    (html, txt)

    Команды пересылки требуются для согласования номеров регистров, в которых осуществляется выполнение операции, с регистрами, в которых должен быть выдан результат. Это имеет смысл, когда эти регистры разные. Получиться это может из-за того, что по приведенной схеме результат выполнения операции всегда находится в регистре с номером метки, а метки левого и правого поддеревьев могут совпадать.

    Для выражения A*B+C*(D+E) будет сгенерирован следующий код:

    MOVE E, R1

    ADD D, R1 MUL C, R1 MOVE R1, R2 MOVE B, R1 MUL A, R1 ADD R1, R2

    В приведенных атрибутных схемах предполагалось, что регистров достаточно для трансляции любого выражения. Если это не так, приходится усложнять схему трансляции и при необходимости сбрасывать содержимое регистров в память (или магазин).


    Содержание  Назад  Вперед







    Forekc.ru
    Рефераты, дипломы, курсовые, выпускные и квалификационные работы, диссертации, учебники, учебные пособия, лекции, методические пособия и рекомендации, программы и курсы обучения, публикации из профильных изданий