En informática , el algoritmo Sethi-Ullman es un algoritmo que lleva el nombre de Ravi Sethi y Jeffrey D. Ullman , sus inventores, para traducir árboles de sintaxis abstracta en código máquina que utiliza la menor cantidad de registros posible.
Al generar código para expresiones aritméticas, el compilador tiene que 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 determinado subárbol. 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 derramen en 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 apliquen la conmutatividad y la asociatividad a los operadores utilizados, pero las leyes distributivas ie no se cumplan). El algoritmo también tiene éxito si ni la conmutatividad ni la asociatividad se cumplen para las expresiones utilizadas y, por lo tanto, no se pueden aplicar transformaciones aritméticas. El algoritmo tampoco aprovecha subexpresiones comunes ni se aplica directamente a expresiones representadas como gráficos acíclicos dirigidos generales en lugar de árboles.
El algoritmo simple de Sethi-Ullman funciona de la siguiente manera (para una arquitectura de carga/almacenamiento ):
Para una expresión aritmética , el árbol de sintaxis abstracta se ve así:
= / \ a * / \ / \ + + / \ / \ / \ d3 + * / \ / \ bcfg
Para continuar con el algoritmo, solo debemos examinar la expresión aritmética , es decir, solo debemos mirar el subárbol derecho de la asignación '=':
* / \ / \ + + / \ / \ / \ d3 + * / \ / \ bcfg
Ahora comenzamos a recorrer el árbol (en preorden por ahora), asignando la cantidad de registros necesarios para evaluar cada subárbol (tenga en cuenta que el último sumando en la expresión es una constante):
* 2 / \ / \ + 2 + 1 / \ / \ / \ d 1 3 0 + 1 * 1 / \ / \ b1c0f1g0
De este árbol se puede ver que necesitamos 2 registros para calcular el subárbol izquierdo del '*', pero sólo 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 emitir código para el subárbol izquierdo primero, porque podríamos encontrarnos con la situación de que sólo nos queden 2 registros para calcular toda la expresión. Si ahora calculamos primero el subárbol derecho (que necesita sólo 1 registro), entonces necesitaríamos un registro para almacenar el resultado del subárbol derecho mientras calculamos el subárbol izquierdo (que todavía necesitaría 2 registros), por lo tanto, necesitaríamos 3 registros simultáneamente. Para calcular el subárbol izquierdo primero 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.
En una versión avanzada del algoritmo Sethi-Ullman , primero se transforman las expresiones aritméticas, explotando las propiedades algebraicas de los operadores utilizados.
