5.1 ANALIZADOR SEMANTICO.
La semántica corresponde al significado asociado a las estructuras formales (sintaxis) del lenguaje.
La fase de análisis semántico de un procesador de lenguaje es aquélla que computa la información adicional necesaria para el procesamiento de un lenguaje, una vez que la estructura sintáctica de un programa haya sido obtenida. Es por tanto la fase posterior a la de análisis sintáctico y la última dentro del proceso de síntesis de un lenguaje de programación.
El objetivo principal del analizador semántico de un procesador de lenguaje es asegurarse de que el programa analizado satisfaga las reglas requeridas por la especificación del lenguaje, para garantizar su correcta ejecución. El tipo y dimensión de análisis semántico requerido varía enormemente de un lenguaje a otro.
Existen dos formas de describir la semántica de un lenguaje de programación: mediante especificación informal o natural y formal.
La descripción informal de un lenguaje de programación es llevada a cabo mediante el lenguaje natural. Esto hace que la especificación sea inteligible (en principio) para cualquier persona. La experiencia nos dice que es una tarea muy compleja, si no imposible, el describir todas las características de un lenguaje de programación de un modo preciso.
La descripción formal de la semántica de lenguajes de programación es la descripción rigurosa del significado o comportamiento de programas, lenguajes de programación, máquinas abstractas o incluso cualquier dispositivo hardware.
− Revelar posibles ambigüedades existentes implementaciones de procesadores de lenguajes o en documentos descriptivos de lenguajes de programación.
− Ser utilizados como base para la implementación de procesadores de lenguaje.
− Verificar propiedades de programas en relación con pruebas de corrección o información relacionada con su ejecución.
− Diseñar nuevos lenguajes de programación, permitiendo registrar decisiones sobre construcciones particulares del lenguaje, así como permitir descubrir posibles irregularidades u omisiones.
− Facilitar la comprensión de los lenguajes por parte del programador y como mecanismo de comunicación entre diseñador del lenguaje, implementador y programador. La especificación semántica de un lenguaje, como documento de referencia, aclara el comportamiento del lenguaje y sus diversas construcciones.
− Estandarizar lenguajes mediante la publicación de su semántica de un modo no ambiguo. Los programas deben poder procesarse en otra implementación de procesador del mismo lenguaje exhibiendo el mismo comportamiento.
5.2 VERIFICACIÓN DE TIPOS EN EXPRESIONES
Sistema de Tipos
Reglas de un lenguaje que permiten asignar tipos a las distintas partes de un programa y verificar su corrección.
- Formado por las definiciones y reglas que permiten comprobar el dominio de un identificador, y en qué contextos puede ser usado.
- Cada lenguaje tiene un sistema de tipos propio, aunque puede variar de una a otra implementación.
- La comprobación de tipos es parte del análisis semántico.
Funciones Principales:
Reglas de un lenguaje que permiten asignar tipos a las distintas partes de un programa y verificar su corrección.
- Inferencia de tipos: calcular y mantener la información sobre los tipos de datos.
- Verificación de tipo: asegurar que las partes de un programa tienen sentido según las reglas de tipo del lenguaje.
La información de tipos puede ser estática o dinámica:
- LISP, CAML o Smalltalk utilizan información de tipos dinámica.
- En ADA, Pascal o C la información de tipos es estática.
- También puede ser una combinación de ambas formas.
Cuantas más comprobaciones puedan realizarse en la fase de compilación, menos tendrán que realizarse durante la ejecución.
- Mayor eficiencia del programa objeto.
Es parte de la comprobación de tipos:
- Conversión de tipos explícita: transformación del tipo de una expresión con un propósito determinado.
- Coerción: conversión de tipos que realiza de forma implícita el compilador.
Conversión de tipos explícita: el programador indica el tipo destino:
- Funciona como una llamada a función: recibe un tipo y devuelve otro.
Conversión de tipos implícita: el compilador convierte automáticamente elementos de un tipo en elementos de otro:
- La conversión se lleva a cabo en la acción semántica de la regla donde se realiza.
Comprobador de tipos seguro: Durante la compilación (comprobación estática) detecta todos los posibles errores de tipo.
Lenguaje fuertemente tipado: Si un fragmento de código compila es que no se van a producir errores de tipo.
En la práctica, ningún lenguaje es tan fuertemente tipado que permita una completa comprobación estática.
Información de tipos dinámica: El compilador debe generar código que realice la inferencia y verificación de tipos durante la ejecución del programa que se está compilando.
Información de tipos estática:
- Se utiliza para verificar la exactitud del programa antes de la ejecución.
- Permite determinar la asignación de memoria necesaria para cada variable.
Tipo de datos = conjunto de valores + operaciones aplicables
En el ámbito de los compiladores, un tipo se define mediante una expresión de tipo (información de tipos explícita):
- Nombre de tipo: float.
- Expresión estructurada explícita: set of integer.
- Estas expresiones se utilizan en la construcción de otros tipos o para declarar variables.
También es posible incluir información de tipos implícita:
La información de tipos, implícita o explícita, se mantiene en la tabla de símbolos:
- Esta información se recupera de la tabla de símbolos mediante el verificador de tipo cuando se hace referencia al nombre asociado.
Ejemplo:
Un lenguaje de programación contiene un conjunto de tipos predefinido denominados tipos simples:
- Algunos lenguajes permiten definir nuevos tipos simples: enumerado, subrango.
Todos los lenguajes permiten crear nuevos tipos complejos a partir de otros más simples mediante constructores de tipos:
- Matrices, productos, registros, punteros, funciones, …
- En Pascal: array, set, record, ...
- En C++: struct, class, union, ....
Para analizar los diferentes tipos que intervienen dentro de un programa, el compilador debe contar con una estructura interna que le permita manejar cómodamente las expresiones de tipos.
Esta estructura interna:
- Debe ser fácilmente manipulable, pues su creación se realizará conforme se hace la lectura del programa fuente.
- Debe permitir comparar fácilmente las expresiones asignadas a distintos trozos de código, especialmente a los identificadores de variables..
La forma más habitual de representación son los grafos acíclicos dirigidos (GADs).
- La ventaja de estas representaciones es que ocupan poca memoria y por tanto la comprobación de equivalencia se efectúa con rapidez.
Ejemplos:
5.3 GRAMATICA DE ATRIBUTOS
Una Gramática con Atributos es una generalización de las Gramáticas Libres de Contexto, denominada
Definición Dirigida por la Sintaxis:
• Cada símbolo gramatical puede tener asociado un conjunto finito de atributos, que pueden ser de los siguientes tipos:
• Sintetizados: su valor se calcula en función de los atributos de los nodos hijos.
• Heredados: su valor se calcula en función de los atributos de los nodos hermanos y/o del nodo padre.
• Cada atributo tomará valores en un dominio.
• Cada producción llevará asociadas un conjunto de reglas semánticas.
• Las relaciones de dependencia entre atributos, establecidas por las reglas semánticas, se representarán mediante el Grafo de Dependencias.
A partir de estas gramáticas se llevan a cabo las denominadas “Traducciones dirigidas por sintaxis”.
2. Atributos Sintetizados
En el caso de los símbolos terminales de la gramática, su atributo no es mas que el lexema asociado al token reconocido por el analizador léxico.
Una gramática con atributos se denomina Gramática
S-Atribuida si todos los atributos son sintetizados. Siempre es posible transformar una Gramática con Atributos en
Gramática S-Atribuida.
Ejemplo: Analizar la forma sentencial 12+3*6, a partir de la siguiente definición dirigida por la sintaxis:
Producción Regla semántica
E1 �� E2 + T E1.val = E2.val + T.val
E �� T E.val = T.val
T1 �� T2 * F T1.val = T2.val * F.val
T �� F T.val = F.val
F �� (E) F.val = E.val
F �� num F.val = valor (num)
3. Atributos Heredados
Una gramática con atributos se denomina Gramática
L-Atribuida si cada atributo que se evalúa cumple una de las siguientes condiciones:
• Es un atributo sintetizado.
• Dada una producción A �� X1X2..Xj..Xn, el atributo heredado asociado a Xj depende únicamente de los atributos de X1,..., Xj-1 y/o de atributos heredados asociados al símbolo A.
4. Grafo de dependencias
Para calcular el valor de un atributo es necesario calcular en primer lugar los valores de los atributos de los que depende, para lo cual se deberá establecer una dependencia entre atributos mediante un Grafo de Dependencias.
Ejemplo: Analizar la forma sentencial real id1, id2, id3 a partir de la siguiente definición dirigida por la sintaxis:
Producción Reglas semánticas
D �� T L L.her = T.tipo
T �� int T.tipo = integer
T �� real T.tipo = real
L �� L1, id L1.her = L.her
AñadeTipoTS(id.entrada, L.her)
L �� id AñadeTipoTS(id.entrada, L.her)
Ejemplo: Dada la gramática G = ({L, A}, {a}, {L��AL | A,
A��a}, L), obtener una gramática con atributos que al analizar una cadena calcule el número de a’s que la componen.
Ejemplo: Dada la gramática G = ({L, E, R}, {“,”, id, [, ]}, {L��id | id[E], E �� R| E,R , R ��id}, L), definir un atributo denominado num_dimensiones y las reglas semánticas asociadas a cada producción, de forma que al analizar una sentencia obtengamos el número de dimensiones que tiene el array referenciado.
Ejemplo: Dada la gramática G = ({S, L, B}, {0, 1, …}, {S��L.L |
L, L��LB | B, B��0 | 1}, S), obtener una gramática con atributos que al analizar un número en binario calcule su equivalente en decimal.
5. Evaluación de atributos con analizadores sintácticos descendentes LL(1)
Las Gramáticas L-Atribuidas engloban a la mayoría de las gramáticas con atributos basadas en gramáticas LL(1).
Se define Esquema de Traducción como una gramática con atributos cuyas acciones semánticas se expresan entre llaves, y se encuentran intercaladas entre los símbolos de la parte derecha de las producciones asociadas a la gramática, o bien al final de las mismas.
Para realizar el Análisis Sintáctico Descendente de atributos con una gramática LL(1) será necesario transformar dicha gramática a un Esquema de Traducción en el que se insertarán las acciones semánticas necesarias, teniendo en cuenta que un valor de un atributo debe estar calculado antes de poder ser utilizado.
El Analizador es similar, pero ahora trabajará con producciones compuestas de los símbolos más las acciones semánticas:
a) Al aplicar una producción introduciremos en la pila los símbolos y las acciones semánticas.
b) Cuando en el tope de la pila se encuentre una acción semántica, pasaremos a ejecutarla, eliminándola a continuación del tope.
Ejemplo: Dada la gramática G = {{E, T}, {+, -, (, ), num},
{E��E+T | E-T | T, T��(E) | num}, E}:
a) Obtener un Esquema de Traducción que permita conocer el resultado de una operación válida para dicha gramática.
b) Aplicar un Análisis Sintáctico Descendente de atributos sobre el Esquema de Traducción obtenido para analizar la evaluación de la expresión 6-3+4.
Ejemplo: Dada la gramática G = {{E, T, R}, {+, -, (, ), num},
{E��TR, R��+TR | -TR | ξ, T��(E) | num}, E}:
a) Obtener un Esquema de Traducción que permita conocer el resultado de una operación válida para dicha gramática.
b) Aplicar un Análisis Sintáctico Descendente de atributos sobre el Esquema de Traducción obtenido para analizar la evaluación de la expresión 6-3+4.
6. Evaluación de atributos con analizadores sintácticos ascendentes LR(1)
En los analizadores LR no se conoce la producción aplicada hasta que no se ha analizado la parte derecha, por lo que las acciones semánticas deberán aplicarse al final de la producción.
En las Gramáticas S-Atribuidas las producciones con sus correspondientes acciones semánticas presentan la siguiente forma:
A �� A1A2...An {acciones semánticas}
En las Gramáticas L-Atribuidas pueden presentarse de esta otra forma:
A �� {0} A1 {1} A2 {2} ... An {n} donde {0}, {1}, ... , {n} son acciones semánticas.
Para poder trabajar con ellas se han de transformar de la siguiente manera:
A �� S0 A1 S1 A2 S2 … An {n}
S0 �� ξ {0}
S1 �� ξ {1}
….
Sn-1 �� ξ {n-1} donde S0, S1, …, Sn son nuevos símbolos no terminales.
Para la realización del análisis, los atributos pueden almacenarse en una pila adicional, o bien en la misma pila.
Para la gramática G = ({E, T}, {+, -, (, ), num},
{E��E+T | E-T | T, T��(E) | num}, E), podríamos realizar una implementación de las acciones semánticas asociadas de la siguiente manera, para un analizador LR:
Producción Fragmento de código
L �� E (amp. LR) Print(val[tope])
E1 �� E2 + T val[nuevoTope] = val[tope-2]+val[tope]
E �� T
T1 �� T2 * F val[nuevoTope] = val[tope-2]*val[tope]
T �� F
F �� (E) val[nuevoTope] = val[tope-1]
F �� num
Los fragmentos de código se ejecutarán justo antes de que tenga lugar una reducción por la regla asociada.
5.4 MANEJO DE ERRORES
Es una de las misiones más importantes del compilador. Se utiliza más en el análisis pero los errores pueden darse en cualquier fase. El manejo de errores es una tarea difícil por dos motivos:
1.A veces algunos errores ocultan otros
2.Un error puede provocar una avalancha de errores que se solucionan con el primero
Criterios a seguir a la hora de manejar errores
1.Pararse al detectar el primer error (conveniente para un compilador interactivo)
2.Detectar todos los errores de una pasada (conveniente para un compilador de línea)
