Notación Polaca

Notación Polaca

notación polaca, también conocida como notación de prefijo o notación prefija, es una forma de notación para la lógica, la aritmética, el álgebra y la computación. Su característica distintiva es que coloca los operadores a la izquierda de sus operandos.

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:

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.

2.2.2 Código P 

El código P comenzó como un código ensamblador objetivo estándar producido por varios compiladores Pascal en la década de 1970 y principios de la de 1980. Fue diseñado para código real para una máquina de pila hipotética la idea era hacer que los compiladores de Pascal se transportaran fácilmente requiriendo solo que se volviera a escribir el intérprete de la maquina P para una plataforma, el código P también a probado ser útil como código intermedio y sean utilizado varias extensiones y modificaciones del mismo en diverso compiladores de código nativo, la mayor parte para lenguaje tipo Pascal. Como el código P fue diseñado para ser directamente ejecutable, contiene una descripción implícita de un ambiente de ejecución particular que incluye tamaños de datos, además de mucha información específica para la maquina P, que debe conocer si se desea que un programa de código P se comprensible. La máquina P está compuesta por una memoria de código, una memoria de datos no específica para variables nombre das y una pila para datos temporales, junto como cualquiera registro que sea necesario para mantener la pila y apoyar la ejecución. 

2.2.3 Triplos

• El resultado se asocia al número de tripleta Ejemplo:

 W * X + (Y + Z) 1. *, W, X 2. +, Y, Z 3. +, (1), (2) Control de flujo: 

IF X>Y THEN Z=X ELSE Z=Y+1 1. >, X, Y 

2. Saltar si falso, (1), 5 3. =, Z, X 

4. Saltar,, 7 5. +, Y, 1 6. =, Z, (5) Problema La optimización supone mover tripletas y hay que recalcular las referencias. 2.2.4 Cuádruplos 

• , , , Ejemplo: (A+B)*(C+D)-E +, A, B, T1 +, C, D, T2 *, T1, T2, T3 -, T3, E, T4 Las cuádruplas facilitan la aplicación de muchas optimizaciones, pero hay que tener un algoritmo para la reutilización de las variables temporales (reutilización de registros del procesador). 

2.3 Esquema de generación 

Los esquemas de generación son las estrategias o acciones que se deberán realizarse y tomarse en cuenta en el momento de generar código intermedio. Los esquemas de generación dependen de cada lenguaje. Tomaremos algunos esquemas de generación del lenguaje C. 

2.3.1 Variables y constantes

 Las variables y constantes deben separarse de tal manera que queden las expresiones una por una de manera simple. Por ejemplo int a,b,c; se descompone a int a; int b; intc; respectivamente. 

2.3.2 Expresiones 

En esta función recibe una cadena que representa una línea de código intermedio y toma las medidas oportunas para que ese código se utilice. Estas medidas pueden ser escribir la línea en un fichero adecuado, almacenar la instrucción en una lista que después se pasará a otros módulos, o cualquier otra que necesitemos en nuestro compilador. Expresiones aritméticas Son aquella donde los operadores que intervienen en ella son numéricos, el resultado es un número y los operadores son aritméticos. Los operadores aritméticos más comúnmente utilizados son: +, - , * , / y %. Comenzamos el estudio por las expresiones aritméticas. Lo que tendremos que hacer es crear por cada tipo de nodo un método que genere el código para calcular la expresión y lo emita. Ese código dejará el resultado en un registro, cuyo nombre devolverá el método como resultado. Para reservar estos registros temporales, utilizaremos una función, reserva. En principio bastar ‘a con que esta función devuelva un registro distinto cada vez que se la llame. Cada nodo generará el código de la siguiente manera:  Por cada uno de sus operandos, llamara al método correspondiente para que se evalúe la sub expresión. Si es necesario, reservara un registro para guardar su resultado.  Emitirá las instrucciones necesarias para realizar el cálculo a partir de los operandos. 

2.3.3 Instrucciones de asignación 

La sintaxis general de la instrucción de asignación es: nombre_de_la_variable = valor El valor a la derecha del signo igual puede ser una constante, otra variable o una expresión que combine constantes y variables, pero siempre la variable y su valor deben ser del mismo tipo de dato. Ejemplos: edad% = 5 area! = 12.3 nombre$ = “Pedro”  Instrucciones de asignación compuesta Las instrucciones de asignación compuesta realizan primero una operación en una expresión antes de asignarla a un elemento de programación. En el siguiente ejemplo se muestra uno de estos operadores, +=, que incrementa el valor de la variable del lado izquierdo del operador con el valor de la expresión de la derecha. Una instrucción de asignación asigna el valor de una expresión a una variable. En general, si la variable que se va a asignar es una propiedad, la propiedad debe ser de lectura y escritura o de sólo escritura; en caso contrario, se produce un error de compilación. Si la variable es una variable de sólo lectura, la asignación debe producirse en un constructor Shared o un constructor de instancia apropiado para el tipo de la variable; en caso contrario, se producirá un error de compilación.

2.3.4 Instrucciones de control 

Esta forma de programación sólo permite resolver problemas sencillos. Para resolver problemas más complejos, nos puede interesar que dependiendo de los valores de los datos, se ejecuten unas instrucciones u otras. Las instrucciones condicionales nos van a permitir representar éste tipo de comportamiento. Sentencias IF y SWITCH. En otros casos, nos encontraremos con la necesidad de repetir una instrucción o instrucciones un número determinado de veces. En éstos casos utilizaremos instrucciones de control iterativas o repetitivas (ciclos). Sentencias WHILE, DO-WHILE y FOR. 

2.3.5 Funciones

 Las funciones pueden reducir a en línea, lo que se hace que expandir el código original de la función. Las funciones se descomponen simplificando los parámetros de manera individual al igual que el valor de retorno.

EXPRESIONES EN NOTACIONES

Expresiones en notaciones infija, prefija y sufija.

Cuando usted escribe una expresión aritmética como B * C, la forma de la expresión le proporciona información para que pueda interpretarla correctamente. En este caso sabemos que la variable B está siendo multiplicada por la variable C, ya que el operador de multiplicación * aparece entre ellos en la expresión. Este tipo de notación se conoce como infija ya que el operador está entre los dos operandos sobre los que está actuando.

Considere otro ejemplo de notación infija, A + B * C. Los operadores + y * siguen apareciendo entre los operandos, pero hay un problema. ¿Sobre qué operandos actúan? ¿Opera el + sobre A y B o el * opera sobre B y C? La expresión parece ambigua.

De hecho, usted ha estado leyendo y escribiendo estos tipos de expresiones durante mucho tiempo y no le causan ningún problema. La razón de esto es que usted sabe algo sobre los operadores + y *. Cada operador tiene un nivel de precedencia. Los operadores de mayor precedencia se utilizan antes que los operadores de menor precedencia. Lo único que puede cambiar ese orden es la presencia de paréntesis. El orden de precedencia para los operadores aritméticos ubica la multiplicación y la división por encima de la suma y la resta. Si aparecen dos operadores de igual precedencia, se utiliza un ordenamiento o asociatividad de izquierda a derecha.

Interpretemos la expresión problemática A + B * C usando la precedencia de los operadores. B y C se multiplican primero y A se añade a ese resultado. (A + B) * C forzaría la suma de A y B antes de la multiplicación. En la expresión A + B + C, por precedencia (vía asociatividad), el + que está más a la izquierda operaría primero.

Aunque todo esto puede ser obvio para usted, recuerde que las computadoras necesitan saber exactamente qué operadores deben ejecutarse y en qué orden. Una forma de escribir una expresión que garantice que no habrá confusión con respecto al orden de las operaciones es crear lo que se denomina expresión completamente agrupada. Este tipo de expresión utiliza una pareja de paréntesis para cada operador. Los paréntesis dictan el orden de las operaciones; no hay ambigüedad. Tampoco es necesario recordar las reglas de precedencia.

La expresión A + B * C + D se puede reescribir como ((A + (B * C)) + D) para mostrar que la multiplicación ocurre primero, seguida por la adición que está más a la izquierda. A + B + C + D se puede escribir como ((A + B) + C) + D) ya que las operaciones de adición se asocian de izquierda a derecha.

Hay otros dos formatos de expresión muy importantes que, al principio, pueden no parecer obvios. Considere la expresión infija A + B. ¿Qué pasaría si moviéramos el operador antes de los dos operandos? La expresión resultante sería + A B. Del mismo modo, podríamos mover el operador al final. Obtendríamos A B +. Estas expresiones se ven un poco extrañas.

Estos cambios en la posición del operador con respecto a los operandos crean dos nuevos formatos de expresión, la notación prefija y la notación sufija (o postfija). La notación prefija requiere que todos los operadores precedan a los dos operandos sobre los que actúan. La notación sufija, por otro lado, requiere que sus operadores aparezcan después de los operandos correspondientes. Algunos ejemplos más deberían ayudar a hacer esto un poco más claro (ver la Tabla 2).

A + B * C se escribiría como + A * B C en la notación prefija. El operador de multiplicación aparece inmediatamente antes de los operandos B y C, denotando que el * tiene precedencia sobre el +. El operador de adición aparece entonces antes de la A y del resultado de la multiplicación.

En notación sufija, la expresión sería A B C * +. Una vez más, el orden de las operaciones se conserva ya que el * aparece inmediatamente después de la B y la C, denotando que el * tiene precedencia, con el + apareciendo después. Aunque los operadores se movieron y ahora aparecen antes o después de sus respectivos operandos, el orden de cada operando se mantuvo exactamente igual en relación con los demás.

Ahora considere la expresión infija (A + B) * C. Recuerde que en este caso, la notación infija requiere los paréntesis para forzar que se lleve a cabo la adición antes de la multiplicación. Sin embargo, cuando A + B fue escrito en notación prefija, el operador de adición fue movido simplemente antes de los operandos, + A B. El resultado de esta operación se convierte en el primer operando para la multiplicación. El operador de multiplicación se mueve delante de toda la expresión, dándonos * + A B C. Igualmente, en notación sufija A B + obliga a que la adición ocurra primero. La multiplicación se puede hacer sobre ese resultado y el operando restante C. La expresión sufija correcta es entonces A B + C *.

Considere nuevamente estas tres expresiones (ver la Tabla 3). Ha ocurrido algo muy importante. ¿A dónde se fueron los paréntesis? ¿Por qué no los necesitamos en las notaciones prefija y sufija? La respuesta es que los operadores ya no son ambiguos con respecto a los operandos sobre los que actúan. Solamente la notación infija requiere los símbolos adicionales. El orden de las operaciones dentro de las expresiones prefijas y sufijas está completamente determinado por la posición del operador y nada más. De muchas maneras, esto hace que la notación infija sea la notación menos deseable de usar.

La Tabla 4 muestra algunos ejemplos adicionales de expresiones infijas y las expresiones equivalentes en notaciones prefija y sufija. Asegúrese de entender cómo son equivalentes en términos del orden de las operaciones que se están realizando.

Conversión de expresiones infijas a notaciones prefija y sufija

Hasta el momento, hemos utilizado métodos ad hoc para convertir entre expresiones infijas y las expresiones equivalentes en notaciones prefija y sufija. Como es de esperar, hay formas algorítmicas para realizar la conversión que permiten transformar correctamente cualquier expresión de cualquier complejidad.

La primera técnica que vamos a considerar utiliza la noción de una expresión completamente agrupada que se discutió anteriormente. Recordemos que A + B * C se puede escribir como (A + (B * C)) para mostrar explícitamente que la multiplicación tiene precedencia sobre la adición. Sin embargo, al observar más de cerca, puede verse que cada pareja de paréntesis también indica el comienzo y el final de un par de operandos con el operador correspondiente en la mitad.

Observe el paréntesis derecho en la subexpresión (B * C) anterior. Si tuviéramos que mover el símbolo de multiplicación a esa posición y quitar el paréntesis izquierdo correspondiente, nos daría B C *, de hecho habríamos convertido la subexpresión a notación sufija. Si el operador de adición también es movido a la posición de su paréntesis derecho correspondiente y se elimina el paréntesis izquierdo que le corresponde, se produciría la expresión sufija completa (ver la Figura 6).

Figura 6: Traslado de operadores a la derecha para producir la notación sufija

Figura 6: Traslado de operadores a la derecha para producir la notación sufija

Si hacemos lo mismo pero en lugar de mover el símbolo a la posición del paréntesis derecho, lo movemos a la izquierda, obtenemos la notación prefija (ver la Figura 7). La posición de la pareja de paréntesis es en realidad una pista sobre la posición final del operador encerrado entre ellos.

Figura 7: Traslado de operadores a la izquierda para producir la notación prefija

Figura 7: Traslado de operadores a la izquierda para producir la notación prefija

Así que, para convertir una expresión, independientemente de su complejidad, ya sea a notación prefija o a notación sufija, agrúpela completamente utilizando el orden de las operaciones. A continuación, mueva cada operador a la posición correspondiente de los paréntesis izquierdo o derecho dependiendo de si desea obtener la expresión en notación prefija o en notación sufija.

La siguiente es una expresión más compleja: (A + B) * C - (D - E) * (F + G). La Figura 8 muestra la conversión a las notaciones sufija y prefija.

Conversión general de notación infija a notación sufija

Necesitamos desarrollar un algoritmo para convertir cualquier expresión infija a una expresión sufija. Para hacer esto vamos a examinar más de cerca el proceso de conversión.

Consideremos una vez más la expresión A + B * C. Como se muestra arriba, A B C * + es la equivalencia en notación sufija. Ya hemos observado que los operandos A, B y C permanecen en sus posiciones relativas. Sólo los operadores cambian de posición. Veamos de nuevo los operadores en la expresión infija. El primer operador que aparece de izquierda a derecha es el +. Sin embargo, en la expresión sufija, el + está al final dado que el siguiente operador, *, tiene precedencia sobre la adición. El orden de los operadores en la expresión original se invierte en la expresión sufija resultante.

A medida que procesamos la expresión, los operadores tienen que ser guardados en alguna parte, ya que sus operandos derechos correspondientes no aparecen todavía. También, el orden de estos operadores guardados puede necesitar ser invertido debido a su precedencia. Ése es el caso con la adición y la multiplicación en este ejemplo. Dado que el operador de adición aparece antes del operador de multiplicación y tiene menor precedencia, necesita aparecer después de que se use el operador de multiplicación. Debido a esta inversión del orden, tiene sentido considerar el uso de una pila para almacenar a los operadores hasta que se necesiten.

Y ¿qué ocurrirá con (A + B) * C? Recuerde que A B + C * es la equivalencia en notación sufija. De nuevo, procesando esta expresión infija de izquierda a derecha, vemos primero el +. En este caso, cuando vemos el *, el + ya se ha transcrito en la expresión de resultado porque tiene precedencia sobre el * en virtud de los paréntesis. Ahora podemos empezar a ver cómo funcionará el algoritmo de conversión. Cuando veamos un paréntesis izquierdo, lo guardaremos para indicar que habrá otro operador de alta precedencia. Ese operador tendrá que esperar hasta que aparezca el paréntesis derecho correspondiente para indicar su posición (recuerde la técnica de agrupar completamente). Cuando aparezca ese paréntesis derecho, el operador puede ser extraído de la pila.

Al recorrer la expresión infija de izquierda a derecha, usaremos una pila para almacenar los operadores. Esto proporcionará la inversión que hemos observado en el primer ejemplo. El tope de la pila siempre será el operador guardado más recientemente. Siempre que leamos a un operador nuevo, tendremos que comparar la precedencia de ese operador con la de los operadores que ya estén en la pila, si los hay.

Suponga que la expresión infija es una cadena de símbolos delimitados por espacios. Los símbolos de operaciones son *, /, + y -, junto con los paréntesis izquierdo y derecho, ( y ). Los símbolos de operandos son los identificadores de un solo carácter A, B, C, y así sucesivamente. Los siguientes pasos producirán una cadena de símbolos en el orden sufijo.

1. Crear una pila vacía llamada pilaOperadores para almacenar los operadores. Crear una lista vacía para almacenar la salida.
2. Corvertir la cadena de entrada de notación infija a una lista, usando el método split.
3. Recorrer la lista de símbolos de izquierda a derecha:
   • Si el símbolo es un operando, agregarlo al final de la lista de salida.
   • Si el símbolo es un paréntesis izquierdo, enviarlo a pilaOperadores.
   • Si el símbolo es un paréntesis derecho, extraer de pilaOperadores hasta que el correspondiente paréntesis izquierdo se haya extraído. Agregar cada operador al final de la lista de salida.
   • Si el símbolo es un operador *, /, +, ó -, incluirlo en pilaOperadores. No obstante, extraer previamente de la pila los operadores que tengan mayor o igual precedencia y agregarlos a la lista de salida.
4. Cuando la expresión de entrada ha sido procesada completamente, verificar pilaOperadores. Todos los operadores que aún estén almacenados en ella se deben enviar a la lista de salida.

La Figura 9 muestra el algoritmo de conversión trabajando sobre la expresión A * B + C * D. Observe que el primer operador * se elimina al verse el operador +. Además, el + permanece en la pila cuando aparece el segundo *, ya que la multiplicación tiene precedencia sobre la adición. Al final de la expresión infija, se extrae dos veces de la pila, eliminando ambos operadores y colocando el + como el último operador en la expresión sufija.

 Figura 9: Conversión de A * B + C * D a notación sufija

Figura 9: Conversión de A * B + C * D a notación sufija

Para codificar el algoritmo en Python, usaremos un diccionario llamado precedencia para almacenar los valores de precedencia para los operadores. Este diccionario mapeará cada operador a un entero que se pueda comparar con los niveles de precedencia de otros operadores (hemos utilizado arbitrariamente los números enteros 3, 2 y 1). El paréntesis izquierdo recibirá el valor más bajo posible. De esta manera cualquier operador que se compara con él tendrá mayor precedencia y se colocará encima de él. La línea 15 define los operandos como cualquier carácter en mayúsculas o dígito. La función de conversión completa se muestra en el ActiveCode 1.

Evaluación de expresiones en notación sufija

Como ejemplo final sobre las pilas, consideraremos la evaluación de una expresión que ya está en notación sufija. En este caso, una pila será de nuevo la estructura de datos elegida. Sin embargo, al recorrer la expresión sufija, son los operandos los que deben esperar, no los operadores como en el algoritmo de conversión anterior. Otra forma de pensar en la solución es que siempre que se vea un operador en la entrada, se usarán en la evaluación los dos operandos más recientes.

Para ver esto con más detalle, considere la expresión sufija 4 5 6 * +. Al recorrer la expresión de izquierda a derecha, usted encuentra primero los operandos 4 y 5. En este punto, usted todavía no está seguro respecto a qué hacer con ellos hasta que vea el siguiente símbolo. Ubicando cada uno en la pila asegura que estén disponibles si un operador viene a continuación.

En este caso, el símbolo siguiente es otro operando. Así pues, como antes, inclúyalo en la pila y examine el símbolo siguiente. Ahora vemos un operador, *. Esto significa que los dos operandos más recientes necesitan ser utilizados en una operación de multiplicación. Al extraer dos veces de la pila, podemos obtener los operandos adecuados y luego realizar la multiplicación (en este caso obtenemos 30 como resultado).

Ahora podemos manejar este resultado colocándolo de nuevo en la pila para que pueda ser utilizado como un operando para los operadores posteriores en la expresión. Cuando se procesa el operador final, sólo quedará un valor en la pila. Se extrae y se devuelve como el resultado de la expresión. La Figura 10 muestra el contenido de la pila a medida que se procesa toda la expresión de ejemplo.

Figura 10: Contenido de la pila durante la evaluación

Figura 10: Contenido de la pila durante la evaluación

La Figura 11 muestra un ejemplo un poco más complejo, 7 8 + 3 2 + /. Hay dos cosas a tener en cuenta en este ejemplo. En primer lugar, el tamaño de la pila crece, disminuye y, a continuación, crece de nuevo a medida que las subexpresiones se evalúan. En segundo lugar, la operación de división necesita ser manejada cuidadosamente. Recuerde que los operandos en la expresión sufija están en su orden original ya que la notación sufija cambia sólo la ubicación de los operadores. Cuando los operandos para la división se extraen de la pila, estos se invierten. Dado que la división no es un operador conmutativo, en otras palabras 

15/5

$15/5$ no es lo mismo que 5/15

$5/15$, debemos estar seguros de que el orden de los operandos no esté intercambiado.

Pila Semántica En un Analizador Sintáctico

Las pilas y colas son estructuras de datos que se utilizan generalmente para simplificar ciertas operaciones de programación. Estas estructuras pueden implementarse mediante arrays o listas enlazadas. 

Pila: colección de datos a los cuales se les puede acceder mediante un extremo, que se conoce generalmente como tope. Las pilas tienen dos operaciones básicas:

• Push (para introducir un elemento)
• Pop (para extraer un elemento)
  

Sus características fundamentales es que al extraer se obtiene siempre el último elemento que acabe de insertarse. Por esta razón también se conoce como estructuras de datos LIFO, una posible implementación mediante listas enlazadas seria insertando y extrayendo siempre por el principio de la lista. Las pilas se utilizan en muchas aplicaciones que utilizamos con frecuencia. Las pilas y colas son estructuras de datos que se utilizan generalmente para simplificar ciertas operaciones de programación. Estas estructuras pueden implementarse mediante arrays o listas enlazadas. Un analizador sintáctico es un autómata de pila que reconoce la estructura de una cadena de componentes léxicos. En general, el analizador sintáctico inicializa el compilador y para cada símbolo de entrada llama al analizador morfológico y proporciona el siguiente símbolo de entrada. Al decir pila semántica no se refiere a que hay varios tipos de pila, hace referencia a que se debe programar única y exclusivamente en un solo lenguaje, es decir, no podemos mezclar código de C++ con Visual Basic.
Ventajas 

• Los problemas de integración entre los subsistemas 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 para poder hacer la comparación. 

Objetivo teórico :

Es construir un árbol de análisis sintáctico, este raramente se construye como tal, sino que las rutinas semánticas integradas van generando el árbol de Sintaxis abstracta. Se especifica mediante una gramática libre de contexto. 

El análisis semántico detecta la validez semántica de las sentencias aceptadas por el analizador sintáctico. El analizador semántico suele trabajar simultáneamente al analizador sintáctico y en estrecha cooperación. Se entiende por semántica como el conjunto de reglas que especifican el significado de cualquier sentencia sintácticamente correcta y escrita en un determinado lenguaje. 

Las rutinas semánticas deben realizar la evaluación de los atributos de las gramáticas siguiendo las reglas semánticas asociadas a cada producción de la gramática. El análisis sintáctico es la fase en la que se trata de determinar el tipo de los resultados intermedios, comprobar que los argumentos que tiene un operador pertenecen al conjunto de los operadores posibles, y si son compatibles entre sí, etc. 

En definitiva, comprobará que el significado de la que se va leyendo es válido. La salida teórica de la fase de análisis semántico sería un árbol semántico. Consiste en un árbol sintáctico en el que cada una de sus ramas ha adquirido el significado que debe tener.

Se compone de un conjunto de rutinas independientes, llamadas por los analizadores morfológico y sintáctico. El análisis semántico utiliza como entrada el árbol sintáctico detectado por el análisis sintáctico para comprobar restricciones de tipo y otras limitaciones semánticas y preparar la generación de código.

Las rutinas semánticas:

suelen hacer uso de una pila que contiene la información semántica asociada a los operadores en forma de registros semánticos.
Reglas semánticas Son el conjunto de normas y especificaciones que definen al lenguaje de programación y están dadas por la sintaxis del lenguaje, las reglas semánticas asignan un significado lógico a ciertas expresiones definidas en la sintaxis del lenguaje. 

La evaluación de las reglas semánticas define los valores de los atributos en los nodos del árbol de análisis sintáctico para la cadena de entrada. Una regla semántica también puede tener efectos colaterales, por ejemplo, imprimir un valor o actualizar una variable global.

Compatibilidad de tipos:

Durante la fase de análisis semántico, el compilador debe verificar que los tipos y valores asociados a los objetos de un programa se utilizan de acuerdo con la especificación del lenguaje. Además debe detectar conversiones implícitas de tipos para efectuarlas o insertar el código apropiado para efectuarlas así como almacenar información relativa a los tipos de los objetos y aplicar las reglas de verificación de tipos. 

Analizadores descendentes: 

Parten del axioma inicial de la gramática, se va descendiendo utilizando las derivaciones izquierdas, hasta llegar a construir la cadena analizada.

Se va construyendo el árbol desde sus nodos terminales. Es decir, se construye desde los símbolos de cadena hasta llegar al axioma de la gramática.

 Bottom up Es un principio de muchos años del estilo de programación que los elementos funcionales de un programa no deben ser demasiado grandes. Si un cierto componente de un programa crece más allá de la etapa donde está fácilmente comprensible, se convierte en una masa de la complejidad que encubre errores tan fácilmente como una ciudad grande encubre a fugitivos. 

Top-down Este método consiste en dividir los problemas en subproblemas más sencillos para conseguir una solución más rápida. El diseño descendente es un método para resolver el problema que posteriormente se traducirá a un lenguaje compresible por la computadora. 
Un parser ascendente utiliza durante el análisis una pila. En esta va guardando datos que le permiten ir haciendo las operaciones de reducción que necesita. Para incorporar acciones semánticas como lo es construir el árbol sintáctico, es necesario incorporar a la pila del parser otra columna que guarde los atributos de los símbolos que se van analizando. Estos atributos estarían ligados a la correspondiente producción en la tabla de parsing.

 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.

Mapa Mental de Pilas Semántica en un Analizador Sintáctico