Algoritmo de Sethi-Ullman

En informática , el algoritmo Sethi-Ullman es un algoritmo que recibe su nombre de Ravi Sethi y Jeffrey D. Ullman , sus inventores, para traducir árboles de sintaxis abstracta a código máquina utilizando la menor cantidad de registros posible.

Descripción general

Al generar código para expresiones aritméticas, el compilador debe decidir cuál es la mejor manera de traducir la expresión en términos de número de instrucciones utilizadas, así como el número de registros necesarios para evaluar un subárbol determinado. Especialmente en el caso de que los registros libres sean escasos, el orden de evaluación puede ser importante para la longitud del código generado, porque diferentes ordenaciones pueden llevar a que se viertan a la memoria y luego se restauren cantidades mayores o menores de valores intermedios. El algoritmo de Sethi-Ullman (también conocido como numeración de Sethi-Ullman ) produce código que necesita la menor cantidad posible de instrucciones, así como la menor cantidad de referencias de almacenamiento (bajo el supuesto de que como máximo se aplican la conmutatividad y la asociatividad a los operadores utilizados, pero las leyes distributivas, es decir, $a*b+a*c=a*(b+c)$ (no se cumplen). El algoritmo también funciona si no se cumplen ni la conmutatividad ni la asociatividad para las expresiones utilizadas, y por lo tanto no se pueden aplicar transformaciones aritméticas. El algoritmo tampoco aprovecha las subexpresiones comunes ni se aplica directamente a expresiones representadas como grafos acíclicos dirigidos generales en lugar de árboles.

Algoritmo simple de Sethi-Ullman

El sencillo algoritmo de Sethi-Ullman funciona de la siguiente manera (para una arquitectura de carga/almacenamiento ):

Recorra el árbol de sintaxis abstracta en preorden o postorden.
1. Para cada nodo hoja, si es un hijo izquierdo no constante, asígnele un 1 (es decir, se necesita 1 registro para almacenar la variable/campo/etc.), de lo contrario asígnele un 0 (es un hijo derecho no constante o un nodo hoja constante (lado derecho de una operación: literales, valores)).
2. Para cada nodo que no sea una hoja, si los subárboles izquierdo y derecho necesitan respectivamente diferentes números de registros l y r , entonces asigne max( l , r ), de lo contrario asigne r + 1.
Para generar código, si los subárboles necesitan un número diferente de registros, evalúe primero el subárbol que necesite más registros (ya que el registro necesario para guardar el resultado de un subárbol puede provocar que el otro se desborde ); de lo contrario, el orden es irrelevante.

Ejemplo

Para una expresión aritmética $a=(b+c+f*g)*(d+3)$ El árbol de sintaxis abstracta tiene este aspecto:

 = / \ a * / \ / \ + + / \ / \ / \ d 3 + * / \ / \ bcfg

Para continuar con el algoritmo, solo necesitamos examinar la expresión aritmética. $(b+c+f*g)*(d+3)$ , es decir, solo tenemos que mirar el subárbol derecho de la asignación '=':

 * / \ / \ + + / \ / \ / \ d 3 + * / \ / \ bcfg

Ahora comenzamos a recorrer el árbol (en preorden por ahora), asignando el número de registros necesarios para evaluar cada subárbol (tenga en cuenta que el último sumando en la expresión $(b+c+f*g)*(d+3)$ es una constante):

 * ₂ / \ / \ + ₂ + ₁ / \ / \ / \ d ₁ 3 ₀ + ₁ * ₁ / \ / \ b ₁ c ₀ f ₁ g ₀

De este árbol se puede ver que necesitamos 2 registros para calcular el subárbol izquierdo del '*', pero solo 1 registro para calcular el subárbol derecho. Los nodos 'c' y 'g' no necesitan registros por las siguientes razones: Si T es una hoja del árbol, entonces el número de registros para evaluar T es 1 o 0 dependiendo de si T es un subárbol izquierdo o derecho (ya que una operación como sumar R1, A puede manejar el componente derecho A directamente sin almacenarlo en un registro). Por lo tanto, comenzaremos a generar código para el subárbol izquierdo primero, porque podríamos encontrarnos con la situación de que solo nos queden 2 registros para calcular toda la expresión. Si ahora calculáramos primero el subárbol derecho (que solo necesita 1 registro), entonces necesitaríamos un registro para almacenar el resultado del subárbol derecho mientras calculamos el subárbol izquierdo (que aún necesitaría 2 registros), por lo tanto necesitaríamos 3 registros concurrentemente. Para calcular primero el subárbol izquierdo se necesitan 2 registros, pero el resultado se puede almacenar en 1, y como el subárbol derecho solo necesita 1 registro para calcularse, la evaluación de la expresión se puede realizar con solo 2 registros restantes.

Algoritmo avanzado de Sethi-Ullman

En una versión avanzada del algoritmo de Sethi-Ullman , las expresiones aritméticas se transforman primero, aprovechando las propiedades algebraicas de los operadores utilizados.

Véase también

Número de Strahler , el número mínimo de registros necesarios para evaluar una expresión sin ningún almacenamiento externo.
Número de Ershov , básicamente el mismo concepto que el número de Strahler.

Referencias

Sethi, Ravi ; Ullman, Jeffrey D. (1970), "La generación de código óptimo para expresiones aritméticas", Journal of the Association for Computing Machinery , 17 (4): 715–728 , doi : 10.1145/321607.321620 , hdl : 10338.dmlcz/101207.

Enlaces externos

Generación de código para árboles