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

Аналогично, если q - ассоциативная операция (т. е. aq(bqg) = (aq b)qg), то, применяя соответствующие преобразования деревьев, можно перевести в друг друга два дерева вида, изображенные на рис. 11.8.

Рис. 11.8. Ассоциативное преобразование синтаксических деревьев.

Ассоциативное преобразование в этом случае имеет вид

X BqС	Û	X¢ AqB
Y AqY	Y X¢qС

После проведения преобразования слева направо оператор XBqC сохранился. Однако, после преобразования этот оператор становится бесполезным, так что его можно удалить, не меняя значение блока.

Определение. Если дано множество A алгебраических законов, то два синтаксических дерева T1 и T2 будут называться эквивалентными относительно A (T1 ºA T2), если существует последовательность преобразований, выводимая из этих законов, переводящих T1 в T2. Через [T]A будем обозначать класс эквивалентности деревьев {T ¢ | T ºA T ¢}.

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

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

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

По данному синтаксическому дереву и множеству A алгебраических законов приведенный ниже алгоритм будем строить синтаксическое дерево Т Î [T]A с минимальной оценкой при условии , что A содержит только ассоциативные законы, применяемые к определенным операциям. Затем к Т ¢ можно будет применить алгоритм построения кода на языке ассемблера для выражений. и найти оптимальную программу для исходного дерева.

Алгоритм построение дерева с минимальной оценкой, некоторые операции которого коммутативны.

Вход. Синтаксическое дерево Т (с тремя и более вершинами) и множество коммутативных законов.

Выход. Синтаксическое дерево [T]A с минимальной оценкой.

Метод. Ядро алгоритма составляет рекурсивная процедура commute(n), аргументом которой служит вершина n синтаксического дерева, а результатом – модифицированное поддерево с вершиной n в качестве корня. В начале вызывается commute(n0), где n0-корень данного дерева Т.

Процедура commute(n).

1)  Если n-лист, полагаем commute(n)=n

2)  Если n-внутренняя вершина, рассмотрим два случая.

(а)Пусть вершина n имеет два прямых потомка n1 и n2 (в указанном порядке) и операция связанная n коммутативна. Если n1- лист, а n2 нет, то выход commute(n) - дерево типа а).

а

Во всех остальных случаях выход commute(n) - дерево типа б).

б

Пример. Рассмотрим рис. 11.7. и предположим, что коммутативно только умножение. Результат применения алгоритма к этому дереву показан на рис. 11.9.

Рис. 11.9. Преобразованное арифметическое выражение.

Отметим, что корень дерева помечен 2 и здесь лишь две младшие вершины. Таким образом, если у нас два сумматора, то на вычисление этого дерева требуется только 7 команд (а для исходного 10).

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

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

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

Определение. Пусть Т - синтаксическое дерево. Множество S из двух или более его вершин называется кистью, если

1)  все вершины в S внутренние и представляют одну и ту же ассоциативную и коммутативную операцию,

2)  вершины из S вместе с соединяющими дугами образуют дерево,

3)  ни одно из собственных подмножеств множества S не обладает свойствами 1) и 2).

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

Прямыми потомками кисти S называются те вершины из Т, которые не принадлежат S, но являются прямыми потомками вершин из S.

Пример. Рассмотрим синтаксическое дерево на рис. 11.10 в котором, слоение и умножение коммутативны, а никакие другие операции не применимы.

Рис. 11.10. Синтаксическое дерево.

Кисти синтаксического дерева Т определяются однозначно и не пересекаются. Для нахождения [T]A дерева минимальной оценкой, когда A содержит законы, отражающие тот факт, что одни операции коммутативны и ассоциативны, а другие только коммутативны, вводится понятие ассоциативного дерева, в котором кисти представляются одной вершиной.

Определение. Пусть Т – синтаксическое дерево. Ассоциативным деревом Т ¢ для Т назовем дерево, полученное заменой каждой кисти S в Т на единственную вершину n с той же ассоциативной и коммутативной операцией, что и у вершин кисти S. Прямые потомки кисти в Т становятся прямыми потомками вершины n в Т ¢.

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

Рис. 11.11. Синтаксическое дерево с кистями.

Ассоциативное дерево для дерева Т изображено на рис.11.12.

Рис. 11.12. Помеченное ассоциативное дерево.

Отметим, что ассоциативное дерево не обязательно должно быть двоичным.

Вершины ассоциативного дерева можно пометить целыми, начиная снизу следующим образом:

1)  Лист, являющийся самым левым прямым потомком своего предка, помечен 1. Все остальные листья помечаются 0.

2)  Пусть n - внутренняя вершина, прямые потомки которой n1, n2,.., nm, помечаем l1, l2,.., lm при m>=2.

a)  Если одно из чисел l1, l2,.., lm превосходит остальные, берем его в качестве метки вершины n.

b)  Если вершина n имеет коммутативную операцию и ni внутренняя вершина с li=1, а остальные вершины n1, n2,.., ni -1, ni+1,.., nm-листья, то в качестве метки вершины n берем 1.

c)  Если условие b) не выполняется, li=lj для некоторых i¹j и li меньше остальных lk, в качестве метки вершины n берем li+1.

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

Вход. Синтаксическое дерево Т и множество А коммутативных и коммутативно-ассоциативных законов.

Выход. Синтаксическое дерево [T]А с минимальной оценкой.

Метод. Строим сначала помеченное ассоциативное дерево Т ¢ для Т. Затем вычисляем acommute(n0), где acommute - процедура, определяемая ниже, а n0 - корень дерева Т ¢. Выходом acommute(n0) служит синтаксическое дерево [T]A с минимальной оценкой.

Процедура acommute(n).

Аргументом n-служит вершина помеченного ассоциативного дерева. Если n - лист, полагаем acommute(n)=n. Если n - внутренняя вершина, то рассмотрим три случая:

1)  Пусть вершина имеет два прямых потомка n1 и n2 и операция связанная с n коммутативна (и, возможно ассоциативна)

а) Если n1 - лист, а n2 нет, то выход acommute(n)-дерево

б) в противном случае acommute(n) дерево

2)  Предположим, что операция q, связанная с n коммутативна и ассоциативна и вершина n имеет прямых потомков n1, n2,.., nm, m>=3 (в порядке слева направо)

Пусть nmax – вершина из n1, .., nm с наибольшей меткой. Если одной и той же наибольшей меткой помечается две или более вершин, то вершину nmax выбираем так, чтобы она была внутренней. Обозначим через p1, p2,.., pm-1 вершины в {n1, .., nm}-{nmax} в любом порядке.