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.
