Генерация промежуточного кода. СУ-перевод

МИНИСТЕРСТВО  ОБРАЗОВАНИЯ РОССИЙСКОЙ ФЕДЕРАЦИИ

ПЕНЗЕНСКИЙ  ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ

кафедра «Вычислительной техники»

 

 

 

 

 

 

 

 

 

 

 

Отчет

о выполнении лабораторных работ №12 по курсу

«Теория компиляции»

 

 

 

 

 

 

 

 

 

 

 

Выполнил:

.

 

Проверил:.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Пенза 2009

Тема: «Генерация промежуточного кода. СУ-перевод»

Цель работы: изучение методов генерации промежуточного платформонезависимого кода программы.

Лабораторное  задание для варианта 8:  преобразовать дерево операций, полученное в результате выполнения лабораторной работы №11 к последовательности триад, предварительно добавив к дереву операцию присвоения результата := в переменную a. Результатом выполнения лабораторной работы должна явиться последовательность триад, полученная вследствие выполнения алгоритма.

 

Рисунок 1 - Дерево операций

 

Выполнение работы

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

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

При переводе часто используется метод, называемый синтаксически управляемым  переводом или СУ-переводом. В  качестве входных данных для СУ-перевода может выступать дерево операций. Принцип СУ-перевода: с каждой вершиной дерева синтаксического разбора N связывается цепочка некоторого промежуточного кода C(N). Код для вершины N строится путём сцепления (конкатенации) в фиксированном порядке последовательности кода C(N) и последовательностей кодов, связанных со всеми вершинами, являющихся прямыми потомками N. Код прямых потомков в свою очередь строится с учётом потомков второго уровня – и т. д.

В процессе СУ-перевода не только вырабатываются цепочки текста выходного языка, но и совершаются некоторые дополнительные действия:

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

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

В процессе СУ-перевода синтаксическое дерево может быть преобразовано  в следующие представления:

• многоадресный код с явно именуемым результатом, называемый тетрадами (a = b + c);
• многоадресный код с неявно именуемым результатом, называемый триадами (a += b);
• ассемблерный код или напрямую машинные команды.

Представление программы  в виде последовательности тетрад или  триад принято называть промежуточной  генерацией кода. Такое представление программы имеет следующие преимущества:

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

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

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

Для дерева операций в  общем случае возможны четыре вида узлов дерева в зависимости от нижележащих узлов:

1. оба нижележащих узла дерева – листья, помеченные операндами;
2. только левый нижележащий узел является листом дерева;
3. только правый нижележащий узел является листом дерева;
4. оба нижележащих узла не являются листьями дерева.

В процессе СУ-перевода для  каждого узла дерева операций производится функция преобразования, которая  выполняет различные действия в  зависимости от вида узла. Данная функция различна в зависимости от результирующего представления программы.

 

Рассмотрим реализацию преобразования программы, представленной в виде дерева операций в последовательность триад. Пусть функция, выполняющая  преобразование узла будет называться Gen(). Входными данными для функции являются текущий узел и текущий номер триады. Выходными данными является последовательность созданных триад, и их количество. Функция будет вызываться рекурсивно. Результирующий код для каждого вида узла дерева приведён ниже в таблице 1. Операция присваивания представляется в триадах в виде обычного узла дерева.

 

Таблица 1. Преобразование узла дерева операций в последовательность триад

Вид узла дерева	Результирующий код	Примечание
	i) операция(лист1, лист2)	i – текущий номер триады
	i) Gen(узел1, i)   i+j) операция(лист1, ^(i+j-1))	j – количество триад, созданных вызовом Gen для узла1. ^(i+j-1) – результат предыдущей триады
	i) Gen(узел1, i)   i+j) операция(  ^(i+j-1), лист1)	j – количество триад, созданных вызовом Gen для узла1. ^(i+j-1) – результат предыдущей триады
	i) Gen(узел1, i)   i+j) Gen(узел2, i+j)   i+j+k) операция(  ^(i+j-1), ^(i+j+k-1))	j – количество триад, созданных вызовом Gen для узла1. k – количество триад, созданных вызовом Gen для узла2. ^(i+j-1) – результат последней триады, сгенерированной вызовом Gen(узел1, i) ^(i+j+k-1) – результат последней триады, сгенерированной вызовом Gen(узел2, i+j)

 

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

a:=c-(a+b)*c-b,

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

Рисунок 2 - Дерево операций с операцией присвоения

Преобразуем дерево операций в последовательность триад. Шаги алгоритма  представлены ниже.

Шаг 1.

1) Gen(узел1, 1)

i+1) := (a,^(i+j-1))

Шаг 2.

1) Gen(узел2, 1)

i+1) - (b,^(i+j-1))

i+2) := (a,^(i+j-1))

Шаг 3.

1) Gen(узел3, 1)

i+1) - (c,^(i+j-1))

i+2) - (b,^(i+j-1))

i+3) := (a,^(i+j-1))

Шаг 4.

1) Gen(узел4, 1)

i+1) * (c,^(i+j-1))

i+2) - (c,^(i+j-1))

i+3) - (b,^(i+j-1))

i+4) := (a,^(i+j-1))

Шаг 5.

1) + (a,b)

2) * (c,^1)

3) - (c,^2)

4) - (b,^3)

5) := (a,^4)

 

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

 

Вывод: при выполнении данной лабораторной работы мы изучили методы генерации промежуточного платформонезависимого кода программы. Преобразовали дерево операций, полученное в результате выполнения лабораторной работы №11 к последовательности триад, предварительно добавив к дереву операцию присвоения результата := в переменную a. Результатом выполнения лабораторной работы явилась последовательность триад, полученная вследствие выполнения алгоритма.