Генерация кода. Триады. Тетрады. Префиксная и постфиксная записи. Три формы объектного кода.

Программы генерации кода предназначены для использования с грамматикой на рисунке 1.2. Ни один из методов грамматического разбора не распознает в точности те конструкции, которые описаны грамматикой. Метод операторного предшествования игнорирует некоторые нетерминальные символы,

а метод рекурсивного спуска вынужден использовать несколько модифицированную грамматику

Основная работа при грамматическом разборе предложения присваивания состоит в анализе нетерминального символа <exp> в правой части оператора присваивания. В процессе грамматического разбора идентификатор SUMSQ распознается сначала как <factor>, потом как <term>. Далее распознается целое

число 100 как <factor>, потом как <term>; затем фрагмент SUMSQ DIV 100 распознается как <term> и т.д. Порядок распознавания фрагментов этого предложения совпадает с порядком, в котором должны выполняться

соответствующие вычисления; сначала вычисляются подвыражения SUMSQ DIV 100 и MEAN*MEAN, а затем второй результат вычитается из первого. Как только очередной фрагмент предложения распознан, вызывается соответствующая программа генерации кода. Например, код, соответствующий правилу <term>1 := <term>2*<factor> будет генерироваться следующим образом. Программы генерации кода выполняют арифметические операции с использованием регистра АХ, и нужно заведомо сгенерировать в объектном коде операцию MUL. Результат этого умножения <term>1 после

операции MUL сохранится в регистре АХ. Если либо <term>2, либо <factor> уже находятся в

регистре АХ(AL) (после выполнения предыдущих

операций), нужно только сгенерировать

инструкцию MUL. Иначе необходимо

сгенерировать также инструкцию MOV,

предшествующую инструкции MUL. В этом случае также надо предв-но сохранить знач-е

регистра АХ(AL), если это необходимо. Очевидно,

что необходимо отслеживать значение, помещенное в регистр АХ(AL), после каждого фрагмента генерируемого объектного кода. Один из вариантов генерации объектного кода приведен на рисунке 4.1. Процесс генерации кода является машинно-зависимым, поскольку необходимо знать систему команд компьютера, для которого этот код генерируется. Существуют, однако, более сложные проблемы, вытекающие из машинной зависимости, которые возникают при распределении регистров и

перестановки машинных инструкций для повышения эффективности. Такого рода оптимизация кода обычно осуществляется с использованием промежуточной

формы представления компилируемой программы. В этой промежуточной форме синтаксис и семантика исходных предложений программы уже полностью

проанализированы, но трансляция в машинные коды еще не осуществлена.

Анализировать и модернизировать программу, представленную в такой промежуточной форме для оптимизации кода, существенно легче, чем для

исходной программы на языке высокого уровня или для этой программы, представленной в машинных кодах.

Промежуточные коды можно проектировать на различных уровнях. Иногда промежуточный код получают, просто разбивая сложные структуры исходного языка на более удобные для обращения элементы. Однако чаще в качестве промежуточного кода используют какой-либо обобщенный машинный код. Существует несколько видов таких обобщенных кодов. Тетрады представляют собой запись операций в форме из четырех составляющих: операция, два операнда и результат операции.

<операция> (<операнд1>,< операнд2>,<результат>)

Тетрады – это линейная последовательность команд, поэтому для них несложно написать алгоритм, который будет преобразовывать последовательность тетрад в

последовательность команд результирующей программы либо в последовательность команд Ассемблера. Тетрады не зависят от архитектуры вычислительной системы, на которую ориентированы результирующая программа. Поэтому они представляют собой машинно-независимую форму внутреннего представления программы. Такой код часто называют трехадресным, т.е. два адреса для операндов (кроме случая унарных операций) и один – для результата. Например, для выражения (-a+b)*(c+d) можно представить тетрады следующим образом:

-a = 1

1+b=2

c+d=3

2*3=4

Триады представляют собой запись операций в форме из трех составляющих: операция и два операнда.

<операция> (<операнд1>,< операнд2>) Особенностью триад является то, что один или оба операнда могут быть ссылками на другую триаду в том случае, если в качестве операнда данной триады выступает результат выполнения другой триады. Поэтому триады при записи последовательно нумеруют для удобства указания ссылок одних триад на другие. Так же, как и в случае с тетрадами, алгоритм преобразования последов-ти триад в команды достаточно прост, но здесь требуется также

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

этой цели не используются. Триады требуют меньше памяти для своего представления, чем тетрады,

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

Выражение

a+b+c*d

можно представить в виде тетрад:

a+b=1

c*d=2

1+2=3

Это же выражение можно представить в виде триад:

a+b

c*d

1+2

Видно, что запись в виде триад является более компактной, но, если

присутствует фаза оптимизации, их применение затруднительно. Наилучшее

решение этой проблемы – косвенные триады, т.е. операнд, ссылавшийся на ранее

вычисленную триаду, теперь ссылается на элемент таблицы указателей на триады,

а не на саму триаду.

Как триады, так и тетрады можно распространить не только на

арифметические выражения, но и на другие конструкции языка. Например,

языковую конструкцию if – then – else можно рассматривать как выражение с

тремя операндами, которому потребуются четыре адреса как тетраде и три – как

триаде.

 

⇐ Предыдущая6789101112131415Следующая ⇒

Поделиться: