Número de Ershov

Los números de Ershov se utilizan en la optimización de código para minimizar el número de registros utilizados por la expresión . Se pueden usar en métodos de registro óptimo cuando solo hay una expresión en un bloque de código. Dada la expresión E = E 1 operación E 2 , entonces el objetivo es generar código de tal manera que minimice el número total de registros utilizados y, en el caso de un número insuficiente de registros disponibles, minimizar el número de registros temporales. variables (es decir, palabras de memoria).

El número de Ershov n de un nodo de un árbol de expresión dado se define de la siguiente manera [1] :

Todas las hojas tienen un valor de 1.
El número de Ershov de un nodo interno con un nodo secundario es igual al número de un nodo secundario.
El número de un nodo de Ershov con dos hijos es: a) el mayor de los números de nodos secundarios, si los números de Ershov de los nodos secundarios son diferentes; b) el número del nodo secundario aumentado en 1 si los números de Ershov de los nodos secundarios son iguales.

El número de nodo de Ershov representa el número mínimo de registros necesarios para ejecutar una subexpresión cuya raíz es este nodo. La idea es ejecutar primero la expresión secundaria con un número de Ershov mayor, luego la segunda expresión secundaria y luego la operación en la raíz.

Ejemplo

Consideremos la expresión . Identifiquemos los nodos del árbol (ver la figura de la derecha) de esta expresión con etiquetas iguales a los números de Ershov. Tenemos una operación '+' en la raíz, las etiquetas de los subárboles izquierdo y derecho son 2, de modo que la etiqueta de la raíz es 3, por lo que se requieren 3 registros para implementar la expresión. ${\ estilo de visualización (ab) + e \ veces (c + d)}$

Cada una de las cinco hojas está etiquetada como "1" (según la primera regla). Según la regla 3, los nodos t1 y t2 del elemento "b" reciben etiquetas iguales a 2. Ahora el nodo t3 tiene nodos secundarios con etiquetas diferentes, por lo que para él la etiqueta también será 2 (por la regla 3, elemento "a"). El nodo t4 nuevamente tiene hijos con etiquetas iguales, por lo que la etiqueta será igual a 3 (regla 3, elemento "b").

Generación de código

A continuación se muestra un algoritmo recursivo para generar código de máquina [2] . El algoritmo tiene una “base” para los registros, es decir , se utilizarán registros para un nodo con un número de Ershov k : ${\displaystyle R_{b},R_{b+1},\puntos,R_{b+k-1))$

Para generar el código máquina de un nodo interno (no hoja) con el número de Ershov k y dos nodos hijos con números iguales (igual a k-1 ), ejecutamos:
- Creamos código para el nodo secundario derecho con base , el resultado se colocará en el registro ; ${\ estilo de visualización b+1}$ $R_{b+k-1}$
- Creamos código para el nodo secundario izquierdo con base , el resultado se colocará en el registro ; $b$ ${\ Displaystyle R_ {b + k-2}}$
- Crear un equipo "Operación" ; ${\displaystyle R_{b+k-1},R_{b+k-2},R_{b+k-1))$
Considere un nodo con la etiqueta k y los nodos secundarios tengan etiquetas diferentes. En este caso, uno de los nodos secundarios tiene la etiqueta k y el otro tiene alguna etiqueta inferior m . Para tal nodo, haga lo siguiente:
- Creamos un código para un nodo secundario con un número de Ershov mayor, usamos la base b , el resultado se colocará en el registro ; $R_{b+k-1}$
- Creamos código para otro nodo secundario, usamos base b , el resultado se colocará en register ; $R_{b+m-1}$
- Creamos el comando "Operación" u "Operación" (dependiendo de dónde se encuentre el nodo con una mayor cantidad de Ershov); ${\displaystyle R_{b+k-1},R_{b+m-2},R_{b+k-1))$ ${\displaystyle R_{b+k-1},R_{b+k-1},R_{b+m-1))$
Para un nodo hoja con un operando x , creamos un comando Cargar . ${\ estilo de visualización R_ {b}, x}$

Evaluación de expresiones con número insuficiente de registros

Si el número de Ershov del nodo raíz de la expresión es mayor que el número de registros disponibles, entonces el número de Ershov se puede usar para generar código con un número mínimo de operaciones de carga y guardado de la siguiente manera [3]

Para la raíz hacer

Creamos un código para un nodo secundario con un número de Ershov mayor;
Creamos un comando para guardar el resultado en memoria;
Creamos un código para un nodo secundario con un número de Ershov más pequeño;
Creamos una instrucción para cargar el valor almacenado en el registro;
Creamos un comando que realiza la operación en la raíz.

Véase también

Número de Strahler-Philosophov , el número mínimo de registros necesarios para ejecutar una expresión sin memoria externa
Algoritmo Network-Ullman , esencialmente el mismo concepto

Notas

↑ Aho, Lam, Seti, Ullman, 2008 , pág. 689-692.
↑ Aho, Lam, Seti, Ullman, 2008 , pág. 690.
↑ Aho, Lam, Seti, Ullman, 2008 , pág. 692-693.

Literatura

Alfred W. Aho, Monica S. Lam, Ravi Seti, Jeffrey D. Ullman. 8.10.1 Números de Ershov // Compiladores (principios, tecnologías y herramientas). - Moscú, San Petersburgo, Kiev: "Williams", 2008. - ISBN 978-5-8459-1349-4 .

Enlaces

Página de la Universidad de Carleton sobre la generación de código óptimo y el uso de números de Ershov .