В информатике алгоритм Сети–Ульмана — это алгоритм, названный в честь его создателей Рави Сети и Джеффри Д. Ульмана , для перевода абстрактных синтаксических деревьев в машинный код , использующий как можно меньше регистров .
При генерации кода для арифметических выражений компилятор должен решить, какой из способов лучше всего перевести выражение с точки зрения количества используемых инструкций, а также количества регистров, необходимых для оценки определенного поддерева. Особенно в случае, когда свободных регистров мало, порядок оценки может быть важен для длины сгенерированного кода, поскольку различные упорядочения могут привести к большему или меньшему количеству промежуточных значений, которые будут сброшены в память и затем восстановлены. Алгоритм Сети-Ульмана (также известный как нумерация Сети-Ульмана ) создает код, которому требуется как можно меньше инструкций, а также как можно меньше ссылок на хранилище (при условии, что в лучшем случае коммутативность и ассоциативность применяются к используемым операторам, но дистрибутивные законы ie не выполняются). Алгоритм также успешно выполняется, если ни коммутативность , ни ассоциативность не выполняются для используемых выражений, и, следовательно, арифметические преобразования не могут быть применены. Алгоритм также не использует преимущества общих подвыражений и не применяется напрямую к выражениям, представленным в виде общих направленных ациклических графов, а не деревьев.
Простой алгоритм Сети–Ульмана работает следующим образом (для архитектуры загрузки/сохранения ):
Для арифметического выражения абстрактное синтаксическое дерево выглядит следующим образом:
= / \ а * / \ / \ + + / \ / \ / \ д 3 + * / \ / \ бкфг
Чтобы продолжить работу с алгоритмом, нам нужно только проверить арифметическое выражение , т.е. нам нужно посмотреть только на правое поддерево присваивания '=':
* / \ / \ + + / \ / \ / \ д 3 + * / \ / \ бкфг
Теперь мы начинаем обход дерева (пока в прямом порядке), назначая количество регистров, необходимых для вычисления каждого поддерева (обратите внимание, что последнее слагаемое в выражении является константой):
* 2 / \ / \ + 2 + 1 / \ / \ / \ д 1 3 0 + 1 * 1 / \ / \ б 1 в 0 е 1 г 0
Из этого дерева видно, что нам нужно 2 регистра для вычисления левого поддерева '*', но только 1 регистр для вычисления правого поддерева. Узлы 'c' и 'g' не нуждаются в регистрах по следующим причинам: если T является листом дерева, то количество регистров для вычисления T равно 1 или 0 в зависимости от того, является ли T левым или правым поддеревом (поскольку такая операция, как add R1, A, может обрабатывать правый компонент A напрямую, не сохраняя его в регистре). Поэтому мы начнем сначала выдавать код для левого поддерева, потому что мы можем столкнуться с ситуацией, когда у нас останется только 2 регистра для вычисления всего выражения. Если бы мы теперь сначала вычислили правое поддерево (которому нужен только 1 регистр), то нам тогда понадобился бы регистр для хранения результата правого поддерева при вычислении левого поддерева (которому все еще нужны 2 регистра), поэтому нам одновременно понадобилось бы 3 регистра. Для вычисления левого поддерева сначала требуется 2 регистра, но результат можно сохранить в 1, а поскольку для вычисления правого поддерева требуется только 1 регистр, для оценки выражения можно обойтись всего 2 оставшимися регистрами.
В расширенной версии алгоритма Сети–Ульмана арифметические выражения сначала преобразуются с использованием алгебраических свойств используемых операторов.
