2.2 Representacion de código Intermedio

En el proceso de traducir un programa fuente a código destino, un compilador puede construir una o más representaciones intermedias, las cuales pueden tener una variedad de formas. Los árboles sintácticos son una forma de representación intermedia; por lo general, se utilizan durante el análisis sintáctico y semántico.

Después del análisis sintáctico y semántico del programa fuente, muchos compiladores generan un nivel bajo explícito, o una representación intermedia similar al código máquina, que podemos considerar como un programa para una máquina abstracta. Esta representación intermedia debe tener dos propiedades importantes: debe ser fácil de producir y fácil de traducir en la máquina destino.

Existe una forma intermedia llamada código de tres direcciones, que consiste en una secuencia de instrucciones similares a ensamblador, con tres operandos por instrucción. Cada operando puede actuar como un registro. La salida del generador de código intermedio en la figura 2.7 consiste en la secuencia de código de tres direcciones.

 

t1 = inttofloat(60)

t2 = id3 * t1                                (2.3)

t3 = id2 + t2

id1 = t3

 

Hay varios puntos que vale la pena mencionar sobre las instrucciones de tres direcciones. En primer lugar, cada instrucción de asignación de tres direcciones tiene, por lo menos, un operador del lado derecho. Por ende, estas instrucciones corrigen el orden en el que se van a realizar las operaciones; la multiplicación va antes que la suma en el programa fuente (2.1). En segundo lugar, el compilador debe generar un nombre temporal para guardar el valor calculado por una instrucción de tres direcciones. En tercer lugar, algunas "instrucciones de tres direcciones" como la primera y la última en la secuencia (2.3) anterior, tienen menos de tres operandos.

Notaciones

Las notaciones son una forma especial en la que se pueden expresar una expresión matemática y puedan ser de 3 formas: infija, prefija y posfija. Los prefijos, Pre -Pos -In se refieren a la posición relativa del operador con respecto a los dos operando.

Notación Polaca

La notación polaca es la originada por un Autómata con pila, en la que los operadores siempre preceden a los operando sobre los que actúan, y que tiene la ventaja de no necesitar paréntesis: 

• Se utiliza principalmente para la representación de expresiones aritméticas.
• Expresión a notación polaca inversa. 

Algoritmo

1. Representa la expresión en forma de árbol sintáctico. 
2. Recorrer el árbol en postorden 

Ejemplo: a + b * c-d 

 

Código a b c * + d-

 Ventajas y desventajas de la notación polaca

 Generación de código:simple, no utiliza registros.

•  Optimización:es difícil de reordenar ya que hay que considerar el contenido de la pila. 
• Interpretación rápida:es muy fácil de interpretar ya que solo necesita una pila. 
• Transportable:si, ya que todos los procesadores implementan una pila. 

Prefija 

La expresión o notación prefija nos indica que el operador va antes de los Operando sus características principales son: 

• Los operadores conservan el mismo orden que la notación infija equivalente.
•  No requiere de paréntesis para indicar el orden de precedencia de operadores ya que él es una operación.
• Se evalúa de izquierda a derecha hasta que encuentra el primer operador seguido inmediatamente de un par de operando.
• Se evalúa la expresión binaria y el resultado se cambia como un nuevo operando. Se repite hasta que nos quede un solo resultado.
• El orden es operador, primer operando, segundo operando. 

 

 

Infija

La expresión o notación infija es la forma más común que utilizamos para escribir expresiones matemáticas, estas notaciones se refiere a que el operador esta entre los operadores. La notación infija puede estar completamente parentizada o puede basarse en un esquema de precedencia de operadores así como el uso de paréntesis para invalidar los arreglos al expresar el orden de evaluación de una expresión.

 

3*4 = 12

3*4+ = 14

3*(4+2) = 18

 

La notación infija tiene el problema de que en expresiones con más de un operador existe ambigüedad sobre cuál es el orden de evaluación. Por ejemplo, la expresión 8/4/2 se puede interpretar como (8/4)/2 o bien8/(4/2). Las otras notaciones no sufren este problema.

 La notación habitual. El orden es primer operando, operador, segundo operando.

 

Postfija

• Como su nombre lo indica se refiere a que el operador ocupa la posición después de los operandos sus características principales son: 
• El orden de los operandos se conserva igual que la expresión infija equivalente no utiliza paréntesis ya que no es una operación ambigua. 
• La operación posfija no es exactamente lo inverso a la operación prefija equivalente.
• El orden es primer operando, segundo operando, operando.

(A+B)*C AB+C*

 

Ejemplo: 

Si deseamos representar las expresiones (2+(3*4)) = xy ((2+3)*4) = x en las tres notaciones mencionadas, el resultado sería: 

 

(2+(3*4)) = 

 

x((2+3)*4) = x

 

Notación postfija 

 

23 4 * + x = 

 

23 + 4 * x = 

 

 

Codigo Nodo de Arbol

package NodoArbol;

import javax.swing.JOptionPane;

/**
 *
 * @author Andrew
 */
public class NodoArbol {

    //miembros de acceso
    NodoArbol nodoizquierdo;
    int datos;
    NodoArbol nododerecho;

    //iniciar dato y hacer de este nodo un nodo hoja
    public NodoArbol(int datosNodo) {
        datos = datosNodo;
        nodoizquierdo = nododerecho = null; //el nodo no tiene hijos
    }

    //buscar punto de insercion e inserter nodo nuevo
    public synchronized void insertar(int valorInsertar) {
        //insertar en subarbol izquierdo
        if (valorInsertar < datos) {
            //insertar en subarbol izquierdo
            if (nodoizquierdo == null) {
                nodoizquierdo = new NodoArbol(valorInsertar);
            } else //continua recorriendo subarbol izquierdo
            {
                nodoizquierdo.insertar(valorInsertar);
            }
        } //insertar nodo derecho
        else if (valorInsertar > datos) {
            //insertar nuevo nodoArbol
            if (nododerecho == null) {
                nododerecho = new NodoArbol(valorInsertar);
            } else {
                nododerecho.insertar(valorInsertar);
            }
        }
    } // fin del metodo insertar
}

class Arbol {

    private NodoArbol raiz;

    //construir un arbol vacio
    public Arbol() {
        raiz = null;
    }

    //insertar un nuevo ndo en el arbol de busqueda binaria
    public synchronized void insertarNodo(int valorInsertar) {
        if (raiz == null) {
            raiz = new NodoArbol(valorInsertar); //crea nodo raiz
        } else {
            raiz.insertar(valorInsertar); //llama al metodo insertar       
        }
    }

    // EMPIEZA EL RECORRIDO EN PREORDEN
    public synchronized void recorridoPreorden() {
        ayudantePreorden(raiz);
    }
    //meoto recursivo para recorrido en preorden

    private void ayudantePreorden(NodoArbol nodo) {
        if (nodo == null) {
            return;
        }

        System.out.print(nodo.datos + " ");     //mostrar datos del nodo
        ayudantePreorden(nodo.nodoizquierdo);   //recorre subarbol izquierdo
        ayudantePreorden(nodo.nododerecho);     //recorre subarbol derecho
    }

    //EMPEZAR RECORRIDO INORDEN
    public synchronized void recorridoInorden() {
        ayudanteInorden(raiz);
    }

    //meoto recursivo para recorrido inorden
    private void ayudanteInorden(NodoArbol nodo) {
        if (nodo == null) {
            return;
        }

        ayudanteInorden(nodo.nodoizquierdo);
        System.out.print(nodo.datos + " ");
        ayudanteInorden(nodo.nododerecho);
    }

    //EMPEZAR RECORRIDO PORORDEN
    public synchronized void recorridoPosorden() {
        ayudantePosorden(raiz);
    }

    //meotod recursivo para recorrido posorden
    private void ayudantePosorden(NodoArbol nodo) {
        if (nodo == null) {
            return;
        }

        ayudantePosorden(nodo.nodoizquierdo);
        ayudantePosorden(nodo.nododerecho);
        System.out.print(nodo.datos + " ");
    }

    /**
     * @param args the command line arguments
     */
    public static void main(String[] args) {
        Arbol arbol = new Arbol();
        int valor;
        String Dato;

        System.out.println("Insertando los siguientes valores: ");

        Dato = JOptionPane.showInputDialog("Inserta el numero de nodos que desea ingresar");
        int n = Integer.parseInt(Dato);

        for (int i = 1; i <= n; i++) {
            Dato = JOptionPane.showInputDialog("Dame el " + i + " valor para colocar en el Arbol");
            valor = Integer.parseInt(Dato);
            System.out.print(valor + " ");
            arbol.insertarNodo(valor);
        }

        System.out.println("\n\nRecorrido Preorden");
        arbol.recorridoPreorden();

        System.out.println("\n\nRecorrido Inorden");
        arbol.recorridoInorden();

        System.out.println("\n\nRecorrido Postorden");
        arbol.recorridoPosorden();
        System.out.println("\n");
    }

}

Mapa de Pila y Analizador Sintaxico

Pila Semántica De Una Analizador Sintáctico

Pila semántica en analizador sintáctico 

La pila juega un papel fundamental en el desarrollo de cualquier analizador semántico. Dentro de cada elemento de la pila se guardan los valores que pueden tener una expresión. 

Un analizador sintáctico ascendente utiliza una pila para guardar información acerca de los sub-árboles que ya han sido analizados. 

Se pueden utilizar campos adicionales en la pila del analizador para guardar los valores de los atributos sintetizados. Tómese en cuenta un ejemplo de la pila de un analizador sintáctico con espacio para un valor de atributo. Sup-óngase que, la pila implanta mediante un par de matrices de estado y val. Cada entrada de estado es un apuntado (o índice) a una tabla de análisis sintáctico.

El tope en curso de la pila se indica con el apuntador tope. Se supone que los atributos sintetizados se evalúan justo antes de cada reducción. 

El diseño ascendente se refiere a la identificación de aquellos procesos que necesitan computarizarse con forme vayan apareciendo, su análisis como sistema y su codificación, o bien, la adquisición de paquetes de software para satisfacer el problema inmediato.

Pila semántica 

• Los problemas de integración entre los sub-sistemas son sumamente costosos y muchos de ellos no se solucionan hasta que la programación alcanza la fecha límite para la integración total del sistema.

 

• Se necesita una memoria auxiliar que nos permita guardar los datos intermedios para poder hacer la comparación. 

Análisis Sintáctico

Analiza el símbolo, la pila y el estado del autómata, produce las estructuras necesarias para la siguiente etapa y en el caso de compilación dirigida por la sintaxis invoca llamadas directas al analizador semántico y al generador de código. Escribe mensajes de errores y trata de limitar el efecto de estos errores.

            "Reconoce la estructura de una cadena de componentes léxicos"

VENTAJAS
· Es posible el uso de la recursividad. La variable que llama al mismo procedimiento en el que está, habrá que guardarla así como el resto de variables de la nueva llamada, para a la vuelta de la recursividad ir sacándolas, esto es posible a la implementación de pilas.

· Simplifican ciertas operaciones de programación. Se pueden implementar mediante arrays o listas enlazadas.

DESVENTAJAS
· Se tiene la limitación de que se debe reservar el espacio en memoria con anticipación. Una vez dado un máximo de capacidad a la pila no es posible insertar un número de elementos mayor que el máximo establecido.

· Si esto ocurre, en otras palabras si la pila está llena y se intenta insertar un nuevo elemento, se producirá un error conocido como desbordamiento-overflow.

· Se deben definir pilas de gran tamaño, pero esto resultará ineficiente y costoso.

· No siempre es viable saber con exactitud el número de elementos a tratar, y siempre existe la posibilidad de que ocurra el error de desbordamiento.

EJEMPLOS DE CÓMO TRABAJA LA PILA SEMÁNTICA CON LAS EXPRESIONES REGULARES

Este ejemplo tendrá que aceptar cualquier fecha del año 2011, esta fecha tendrá que ser válida (que lleve relación el mes con el día)

Recorrido de un árbol: Preorden, Inorden, Postorden

Recorrido de un árbol: Preorden, Inorden, Postorden

• Pre orden: (raíz, izquierdo, derecho). Para recorrer un árbol binario no vacío en preorden, hay que realizar las siguientes operaciones recursivamente en cada nodo, comenzando con el nodo de raíz: 1. Visite la raíz 2. Atraviese el sub-árbol izquierdo 3. Atraviese el sub-árbol derecho • Inorden: (izquierdo, raíz, derecho). Para recorrer un árbol binario no vacío en inorden (simétrico), hay que realizar las siguientes operaciones recursivamente en cada nodo: 1. Atraviese el sub-árbol izquierdo 2. Visite la raíz 3. Atraviese el sub-árbol derecho • Postorden: (izquierdo, derecho, raíz). Para recorrer un árbol binario no vacío en postorden, hay que realizar las siguientes operaciones recursivamente en cada nodo: 1. Atraviese el sub-árbol izquierdo 2. Atraviese el sub-árbol derecho 3. Visite la raíz En general, la diferencia entre pre orden, inorden y postorden es cuándo se recorre la raíz. En los tres, se recorre primero el sub-árbol izquierdo y luego el derecho. • En pre orden, la raíz se recorre antes que los recorridos de los subárboles izquierdo y derecho • En inorden, la raíz se recorre entre los recorridos de los árboles izquierdo y derecho, y • En postorden, la raíz se recorre después de los recorridos por el subárbol izquierdo y el derecho

ARBOLES DE EXPRESIONES

Árbol de Expresión

Dado un grafo conexo, no dirigido G. Un árbol de expansión es un árbol compuesto por todos los vértices y algunas (posiblemente todas) de las aristas de G. Al ser creado un árbol no existirán ciclos, además debe existir una ruta entre cada par de vértices.

Un grafo puede tener muchos arboles de expansión, veamos un ejemplo con  el siguiente grafo:

En la imagen anterior se puede observar que el grafo dado posee 3 arboles de expansión, dichos arboles cumplen con las propiedades antes mencionadas como son unir todos los vértices usando algunas aristas.

Árbol de Expansión Mínima

Dado un grafo conexo, no dirigido y con pesos en las aristas, un árbol de expansión mínima es un árbol compuesto por todos los vértices y cuya suma de sus aristas es la de menor peso. Al ejemplo anterior le agregamos pesos a sus aristas y obtenemos los arboles de expansiones siguientes:

De la imagen anterior el árbol de expansión mínima seria el primer árbol de expansión cuyo peso total es 6.

El problema de hallar el Árbol de Expansión Mínima (MST) puede ser resuelto con varios algoritmos, los mas conocidos con Prim y Kruskal ambos usan técnicas voraces (greedy).