2.2.1 Notacion Polaca

La notación polaca, también conocida como notación prefija, es un tipo de notación que se aplica en lógica, aritmética y álgebra. Fue creada por Jan Łukasiewicz allá por los años 20 del siglo XX. Su principal característica, y por lo que se la conoce como notación prefija, es que los operadores preceden a los operandos, lo que significa, traducido al ámbito de la lógica, que las conectivas preceden a las variables.

El alcance de un operador queda perfectamente determinado por su posición en la fórmula, cuanto más a la izquierda se haye un operador mayor alcance tiene. Del mismo modo, la conectiva principal de una fórmula en notación polaca es la situada más a la izquierda.

Este tipo de notación evita por tanto el uso de símbolos auxiliares (paréntesis, corchetes…) para establecer el alcance de las conectivas, a diferencia de la notación estándar. Esta notación puede leerse sin ambigüedad sin recurrir a estos símbolos. Esta característica hace su escritura más compacta.

Por ejemplo, el axioma de no contradicción, que en notación estándar escribimos ¬(p ∧ ¬ p), en notación polaca lo expresaríamos así: NKpNp.

Conectivas en notación polaca

Tradicionalmente, la notación polaca usa letras mayúsculas para expresar conectivas, tomando normalmente la primera letra del nombre de la conectiva en polaco. Aquí tenemos una lista con los símbolos más comunes:

Conectiva	Notación estándar	Notación polaca
Negación	¬	N
Implicación	→	C
Conjunción	∧	K
Disyunción	∨	A
Bicondicional	↔	E
Posibilidad	⋄	M
Necesidad	◻	L
Cuantificador universal	∀	Π
Cuantificador existencial	∃	Σ

Definición de fórmula bien formada en notación polaca

Tomando la lista anterior de conectivas en notación polaca más un conjunto de variables proposicionales como alfabeto de un lenguaje, tenemos la siguiente definición recursiva de fórmula bien formada en dicho lenguaje:

·         Sea α una variable proposicional. α es una fórmula bien formada.

·         Sean α, β fórmulas bien formadas. Nα, Cαβ, Kαβ, Aαβ, Eαβ, Mα, Lα, Πα, Σα son fórmulas bien formadas.

Método para traducir una fórmula en notación estándar a notación polaca

(1) Buscamos la conectiva principal y escribimos la equivalente en notación polaca.

(2) Si la conectiva es unaria, tomamos su argumento como una subfórmula y aplicamos (1).

(3) Si la conectiva es binaria, (3a) tomamos el primer argumento y aplicamos (1), a continuación tomamos el segundo argumento y aplicamos (1).

(4) Si el símbolo es una variable proposicional, la escribimos a continuación.

El procedimiento acaba en un número finito de pasos dado que en sucesivas aplicaciones de (1) la complejidad de la fórmula disminuye. Si se trata de una fórmula bien formada, el procedimiento acabará por darnos otra fórmula bien formada en notación polaca. Baste esta descripción para mostrar el carácter formal del procedimiento.

En la práctica, resultaría tedioso aplicar este procedimiento paso por paso. Resulta más adecuado entender la mecánica por medio de ejemplos y aplicarla directamente; con cierto entrenamiento la traducción se hace de manera casi automática.

Como ejemplo de este procedimiento vamos a utilizar una instancia de la ley de De Morgan, que en notación estándar escribiríamos así: ¬(p ∧ q) → (¬p ∨ ¬q). En este ejemplo la conectiva principal es la implicación, una conectiva binaria, cuyos argumentos tienen como conectiva principal la negación y la disyunción respectivamente. Tendremos que traducir las sucesivas subfórmulas hasta las variables variables proposicionales.

Notación estándar	Notación polaca	Operación
¬(p ∧ q) → (¬p ∨ ¬q)	C	(1), (3)
¬(p ∧ q) → (¬p ∨ ¬q)	C_____ _____	(3a)
¬(p ∧ q)	CN	(1)
¬(p ∧ q)	CN____	(2)
p ∧ q	CNK_ _	(1), (3)
p ∧ q	CNKp	(3a), (4)
p ∧ q	CNKpq	(3b), (4)
¬(p ∧ q) → (¬p ∨ ¬q)	CNKpq_____	(3b)
¬p ∨ ¬q	CNKpqA__ __	(1), (3)
¬p ∨ ¬q	CNKpqA__ __	(3a)
¬p	CNKpqAN_	(1), (2)
¬p	CNKpqANp	(4)
¬p ∨ ¬q	CNKpqANp__	(3b)
¬q	CNKpqANpN_	(1), (2)
¬q	CNKpqANpNq	(4)

Algoritmo

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