Методические указания (1114907), страница 12

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 12)

Рис. 5.1. Синтаксическое дерево для инструкции a := b * -c + b * -c.

Рис. 5.2. Даг для инструкции a := b * -c + b * -c.

Опишем примерные семантические правила, которые необходимы для построения промежуточного кода в виде синтаксического дерева для грамматики арифметических выражений.

Поле нетерминального символа nptr обозначает указатель на узел некоторый дерева.

Операция mknode(name, ptr1, ptr2) позволяет создать узел дерева, который имеет название name и ссылается на узлы, обозначаемые указателями ptr1 и ptr2 соответственно.

Операция mkunode(name, ptr) позволяет создать узел дерева, который имеет название name и ссылается только на узел, обозначаемый указателем ptr.

Операция mkleaf(name, value) позволяет создать лист дерева, который имеет название name и значение value.

Построение дага будет осуществлено в том случае, если модифицировать правила, описанные выше, таким образом, что операции mknode(name, ptr1, ptr2) и mkunode(name, ptr) будут не сразу создавать новый узел дерева, а проверять, существует ли такой узел, и если существует, то возвращать указатель на него.

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

Первый вариант реализации в виде записей с указателями:

Второй вариант реализации в виде массива:

0	id	b
1	id	c
2	uminus	1
3	*	0	2
4	id	b
5	id	c
6	uminus	5
7	*	4	6
8	+	3	7
9	id	a
10	assign	9	8

Приведем так же аналогичные варианты хранения дага.

Первый вариант:

Второй вариант :

0	id	b
1	id	c
2	uminus	1
3	*	0	2
4	+	3	3
5	id	a
6	assign	5	4

Как видно из размера структур данных, даг занимает меньше памяти, чем синтаксическое дерево.

Трехадресный код

Трехадресный код представляет собой последовательность инструкций вида x := y op z, где x, y, z – имена, константы, временные переменные, генерируемые компилятором; op означает некоторый оператор, например, арифметический оператор для работы с логическими значениями. Заметим, что не разрешены никакие встроенные арифметические выражения, и в правой части инструкции имеется только один оператор. Следовательно, выражение исходного языка наподобие x + y * z может быть транслировано в следующую последовательность.

t₁ := y * z

t₂ := x + t₁

Здесь t₁ и t₂ – сгенерированные компилятором временные имена. Такое разложение сложных арифметических выражений и вложенных инструкций потока управления делает трехадресный код подходящим для генерации целевого кода и оптимизации.

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

Код для синтаксического дерева:

t₁ := - с

t₂ := b * t₁

t₃ := - c

t₄ := b * t₃

a := t₂ + t₄

Код для дага:

t₁ := - c

t₂ := b * t

t₃ := t₂ + t₂

a := t₃

Типы трехадресных инструкций

Трехадресные инструкции похожи на ассемблерный код.

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

1. Инструкция присваивания вида x := y op z, где op – бинарная арифметическая операция или логическая операция.

2. Инструкция присваивания вида x := op y, где op – унарная операция. Основные унарные операции включают унарный минус, логическое отрицание, операторы сдвига и операторы преобразования, например, преобразуют число с фиксированной точкой в число с плавающей точкой.

3. Инструкции копирования вида x := y, в которых значение y присваивается x.

4. Безусловный переход goto L. После этой инструкции будет выполнена трехадресная инструкция с меткой L.

5. Условный переход типа if x relop y goto L. Эта инструкция применяет оператор отношения relop (<, >, = и т.п.) к x и y, и следующей выполняется инструкция с меткой L, если соотношение x relop y верно. В противном случае выполняется следующая за условным переходом инструкция.

6. Инструкции param x и call p, n для вызова процедур и return y для возврата из них, где y обозначает необязательное возвращаемое значение. Обычно они используются в виду следующей последовательности трехадресных инструкций.

param x₁,

param x₂,

param x₃,

…,

param x_n

call p, n

Данная последовательность генерируется в качестве части вызова процедуры p(x₁, x₂, …, x_n). В инструкции call p, n целое число n, указывающее количество действительных параметров, не является излишним в силу того, что вызовы могут быть вложенными.

1. Индексированные присвоения типа x := y[i] и x[i] := y. Первая инструкция присваивает x значение, находящееся в i-й ячейке памяти по отношению к y. Инструкция x[i] := y заносит в i-ю ячейку памяти по отношению к x значение y. В обеих инструкциях x, y и i ссылаются на объекты данных.

2. Присваивание адресов и указателей вида x := &y, x := *y и *x := y. Первая инструкция устанавливает значение x равным положению y в памяти. Предположительно, y представляет собой имя, возможно временное, обозначающее выражение с l-значением типа A[i,j], а x – имя указателя или временное имя. Таким образом, r-значение x становится равным содержимому этой ячейки. И наконец, инструкция, *x := y устанавливает r-значение объекта, указываемого x, равным r-значению y.

Опишем примерные семантические правила, которые необходимы для построения промежуточного кода в виде трехадресного кода для грамматики арифметических выражений.

Поле нетерминального символа place обозначает имя, которое хранит нетерминал.

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

Операция newtemp последовательно возвращает имена временных переменных t_1­, t₂, …, .

Операция || позволяет добавить к последовательности трехадресных инструкций новые, сгенерированные при срабатывании данного правила.

Операция gen(instruction) позволяет генерировать трехадресную инструкцию, которая является конкатенацией строк, записанных в параметрах.

Реализация трехадресных инструкций

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

Четверки.

Четверка (quadruple) представляет собой запись с четырьмя полями, которые назовем op, arg1, arg2, result. Поле op содержит внутренний код оператора. Трехадресная инструкция x := y op z представляется размещением y в arg1, z – в arg2 и x – в result. Инструкции с унарным оператором наподобие x := -y или x := y не используют arg2. Операторы типа param не используют ни arg2, ни result. Условные и безусловные переходы помещают в result целевую метку.

Покажем представление в виде четверок операции присваивания a := b * -c + b * -c.

Тройки.

Для того, чтобы избежать вставки временных имен в таблицу символов, мы можем ссылаться на временные значения по номеру инструкции, которая вычисляет значение, соответствующее этому имени. Если мы поступим таким образом, трехадресные инструкции можно будет представить записями только с тремя полями: op, arg1 и arg2. Поля arg1 и arg2 для аргументов op представляют собой либо указатели в таблицу символов, либо указатели на тройки. Поскольку здесь используется три поля, этот вид промежуточного кода известен как тройки (triple). За исключением представления имен, определенных в программе, тройки соответствуют представлению синтаксического дерева или графа в виде массива вершин.

Покажем представление в виде троек операции присваивания a := b * -c + b * -c.

	op	arg1	arg2
(0)	uminus	c
(1)	*	b	(0)
(2)	uminus	c
(3)	*	b	(2)
(4)	+	(1)	(3)
(5)	assign	а	(4)

Косвенные тройки.

Характеристики

Список файлов книги