Теория языков программирования методов трансляции (стр. 26 )

Формально определим синтаксическое дерево как помеченное двоичное дерево T, имеющих одну или более таких вершин, что

1)  каждая внутренняя вершина помечена бинарной операцией qÎQ,

2)  все листья помечены различными именами переменных XÎS.

Будем предполагать, что множества Q и S не пересекаются. Вершинам дерева, начиная снизу, можно следующим образом приписать значения:

1)  если n – лист, помеченный X, то n имеет значение X,

2)  если n – внутренняя вершина, помеченная q, и ее прямыми потомками являются n1 и n2 со значениями v1 и v2, то n имеет значение q v1 v2.

Значением дерева будем считать значение его корня.

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

6.2.2.  Разметка дерева

Алгоритм разметки синтаксического дерева.

Вход. Синтаксическое дерево T.

Выход. Помеченное синтаксическое дерево.

Метод. Вершинам дерева T рекурсивно, начиная снизу, назначаем целочисленные метки:

1)  Если вершина есть лист, являющимся левым прямым потомком своего прямого предка, или корень, помечаем вершину 1; если вершина есть лист, являющимся правым потомком, помечаем ее 0.

2)  Если вершина n имеет прямых потомков n1 и n2, помеченных l1, l2. Если l1,= l2. берем в качестве метки число l1 +1.

Пример. Арифметическое выражение

A*(B-C)/D*(E-F)

изображенное в виде дерева на рис. 11.7, на котором представлены целочисленные метки.

Рис. 11.7. Помеченное синтаксическое дерево.

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

Алгоритм построения кода на языке ассемблера для выражений.

Вход. Помеченное синтаксическое дерево T и N сумматоров A1, A2, …, AN, где N ³ 1.

Выход. Программа P на языке ассемблера, после последней команды которой значением v(A1) становится v(T); т. е. P вычисляет выражение, представленное деревом T, и помещает результат на сумматор A1.

Метод. Предполагается, что дерево T помечено в соответствии с алгоритмом разметки синтаксического дерева. Затем рекурсивно выполняется процедура code(n, i). Входом для code служит вершина n дерева T и целое число i от 1 до N. Число i означает, что в данный момент для вычисления выражения доступны сумматоры Ai, Ai+1, …, AN. Выходом code(n, i) служит последнее значение v(n) и помешает результат на сумматор Ai.

Сначала выполняется code(n0, 1), где n0 – корень дерева T. Последовательность команд, генерированных этим вызовом процедуры code, и будет нужной программой на языке ассемблера.

Процедура code(n, i). Предполагается, что n - вершина дерева T, а i - целое число между 1 и N.

1)  Если n – лист, выполняем шаг 2). В противном случае выполняем шаг 3).

2)  Если вызвана процедура code(n, i), а n – лист, то n всегда будет левым прямым потомком (или корнем, если n – единственная вершина дерева). Если с листом n связано имя переменной X, то

code(n, i) = ‘LOAD X, Ai’

(это означает, что выходом процедуры code(n, i) служит команда LOAD X, Ai).

3)  В это место мы приходим, только если n – внутренняя вершина. Пусть с вершиной n операция q и ее прямыми потомками являются n1 и n2 с метками l1 и l2.

Следующий шаг определяется значением меток l1 и l2:

(а) если l2 = 0 (n2 – правый лист), выполняем шаг 4),

(б) если 1 £ l1 < l2 и l1 < N, выполняем шаг 5),

(в) если 1 £ l2 £ l1 и l2 < N, выполняем шаг 6),

(г) если N £ l1 и N < l2, выполняем шаг 7).

4)  code(n, i) = code(n1, i)

‘OP q Ai, X, Ai’

Здесь X – переменная, связанная с листом n2, а OP q - код операции q. Выходом для code(n, i) служит выход для code(n1, i), сопровождаемый командой OP q Ai, X, Ai.

5)  code(n, i) = code(n2, i)

code(n1, i+1)

‘OP q Ai+1, Ai, Ai’

6)  code(n, i) = code(n1, i)

code(n2, i+1)

‘OP q Ai, Ai+1, Ai’

7)  code(n, i) = code(n2, i)

T newtemp

‘STORE Ai, T ’

code(n1, i)

‘OP q Ai, T, Ai’

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

Пример. Применим алгоритм при N =2 к синтаксическому дереву на рис. 11.6. Последовательность вызовов code(n, i) приведена в табл. 11.4.

Таблица 11.4.

Вызов	Шаг
code(/, 1) code(*R, 1) code(D, 1) code(-R, 2) code(E, 2) code(*L, 1) code(A, 1) code(-L, 2) code(B, 2)	(3г) (3в) (2) (3а) (2) (3в) (2) (3а) (2)

Здесь *L – ссылка на левый потомок вершины /, *R – на правый потомок вершины *L, а –R – на правый потомок вершины *R.

Процедура code(/, 1) генерирует программу

LOAD D, A1

LOAD E, A2

SUBTR A2, F, A2

MULT A1, A2, A1

STORE A1, TEMP1

LOAD A1, A1

LOAD B, A2

SUBTR A2, C, A2

MULT A1, A2, A1

DIV A1, TEMP1, A1

Рассмотренные нами алгоритмы позволяют сформулировать две базовые теоремы для построения оптимального кода.

Теорема 1. Программа, выработанная процедурой code(n, i) правильно вычисляет значение вершины n, помещая его на i-й сумматор.

Теорема 2. Пусть Т - синтаксическое дерево, l – метка его корня, N - число доступных сумматоров. Программа, вычисляющая T без использования команд STORE, существует тогда и только тогда, когда L£ N.

Выясним теперь, сколько команд LOAD и STORE требуется для вычисления синтаксического дерева, если использовать N сумматоров, когда корень помечен числом превышающим N.

6.2.3.  Программы с командами STORE

Определение. Пусть Т - синтаксическое дерево, а N - число доступных сумматоров. Вершина из Т называется старшей, если каждый прямой ее потомок помечен числом не меньше чем N. Вершина называется младшей, если она является листом и левым потомком своего прямого предка (т. е. лист с меткой 1).

На рис. 11.7. при N=2 – одна старшая вершина – корень и четыре младших – листья со значениями A, B, D и E.

Лемма 1. Пусть Т - синтаксическое дерево. Программа Р, вычисляющая Т и использующая m команд LOAD, существует тогда и только тогда, когда Т имеет не более m младших вершин.

Лемма 2. Пусть Т - синтаксическое дерево. Программа P, вычисляющая Т и использующая M команд STORE, существует тогда и только тогда, когда Т имеет не более M старших вершин.

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

Доказательство. В соответствии с введенными леммами 1 и 2 алгоритм вырабатывает программу с минимальным числом команд LOAD и STORE. Поскольку ясно, что минимальное количество команд операций равно числу внутренних вершин дерева, а алгоритм дает по одной такой команде для каждой внутренней вершине дерева, то утверждение теоремы очевидно.

Для нашего примера имеется одна старшая и четыре младших вершины (N=2). Арифметическое выражение имеет пять внутренних вершин. Таким образом, для вычисления требуется не менее 10 операторов.

6.2.4.  Влияние некоторых алгебраических законов

Определим оценку синтаксического дерева как сумму

1)  числа внутренних вершин,

2)  числа старших вершин,

3)  числа младших вершин.

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

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