Число Ершова - Ershov Number

Эта статья не цитировать любой источники. Пожалуйста помоги улучшить эту статью к добавление цитат в надежные источники. Материал, не полученный от источника, может быть оспорен и удаленный. Найдите источники: "Число Ершова"  – Новости  · газеты  · книги  · ученый  · JSTOR (Апрель 2011 г.) (Узнайте, как и когда удалить этот шаблон сообщения)

Числа Ершова используются в оптимизация кода минимизировать количество регистрировать распределения. Числа Ершова можно использовать в методах для оптимального выбора регистров, когда в кодовом блоке есть только одно выражение. Учитывая выражение E = E₁ op E₂ цель состоит в том, чтобы сгенерировать код таким образом, чтобы либо минимизировать количество используемых регистров, либо, если доступно недостаточное количество регистров, минимизировать количество требуемых временных нерегистров.

Число Ершова п узла в данном дерево выражений определяется следующим образом:

1. Каждый лист имеет п = 1.
2. Для узла с одним потомком п такой же, как у ребенка.
3. Для узла с двумя дочерними элементами п определяется как:

${ displaystyle n = { begin {case} max (child_ {1}, child_ {2}) & child_ {1} neq child_ {2} child_ {1} + 1 & child_ {1} = child_ {2} конец {case}}}$

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

Пример

Предположим, у нас есть дерево выражений с операцией '+' в корне, а также слева и справа. поддеревья имеют числа Ершова 3 и 4 соответственно. Число Ершова этого узла равно 4, поэтому мы должны иметь возможность сгенерировать код для выражения, используя 4 регистра.

1. Сгенерируйте код для оценки правильного дочернего элемента, используя регистры r1, r2, r3 и r4. Поместите результат в r1.
2. Сгенерируйте код для оценки левого потомка, используя регистры r2, r3 и r4. Поместите результат в r2.
3. Выполните команду «ADD r1, r2, r1».

Если не хватает регистров?

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

1. сгенерировать код для ребенка с большим числом Ершова
2. дать указание сохранить результат во временном
3. сгенерировать код для ребенка с меньшим числом Ершова
4. дать команду на загрузку временного в регистр
5. выдать инструкцию на выполнение операции в корне

Смотрите также

• Номер Strahler, минимальное количество регистров, необходимое для оценки выражения без внешнего хранилища
• Алгоритм Сетхи – Уллмана, в основном та же концепция

внешняя ссылка

• Страница Карлтонского университета об оптимальной генерации кода и использовании чисел Ершова