Análisis Semántico

Análisis Semántico

Introducción

Los programas que se compilan no son solamente cadenas de símbolos sin significado alguno que pueden ser aceptadas como correctas o no por una máquina abstracta. El lenguaje no es más que el vehículo por el cual se intenta transmitir una serie de instrucciones a un procesador para que éste las ejecute produciendo unos resultados. Por ello, la tarea del compilador requiere la extracción del contenido semántico incluido en las distintas sentencias del programa.

Por esto, se hace necesario dotar al compilador de una serie de rutinas auxiliares que permitan captar todo aquello que no se ha expresado mediante la sintaxis del lenguaje y todo aquello que hace descender a nuestro lenguaje de programación de las alturas de una máquina abstracta hasta el nivel de un computador real. A todas estas rutinas auxiliares se les denomina genéricamente análisis semántico.

El Analizador semántico ejecuta sus funciones en conjunto al analizador sintáctico, ambos justo antes de la generación de código intermedio, es decir, es una etapa clave dentro del proceso de la compilación de código.

Análisis Semántico

Semántica: conjunto de reglas que especifican el significado de cualquier sentencia sintácticamente correcta y escrita en un determinado lenguaje.

La semántica corresponde al significado asociado a las estructuras formales (sintaxis) del lenguaje. Como las gramáticas (E)BNF, además normalmente limitadas a LR o LL, no pueden describir todos los elementos sintácticos del lenguaje, se hace preciso algún análisis adicional. Así, se denomina tradicionalmente “análisis semántico” a todo aquello que forma parte del front end más allá de lo que la gramática utilizada nos permite.

La fase de análisis semántico revisa el programa fuente para tratar de encontrar errores semánticos y reúne la información sobre los tipos para la fase posterior de generación de código. En ella se utiliza la estructura jerárquica determinada por la fase de análisis sintáctico para identificar los operadores y operandos de expresiones y proposiciones.

Un componente importante del análisis semántico es la verificación de tipos. Aquí, el compilador verifica si cada operador tiene operandos permitidos por la especificación del lenguaje fuente.

El análisis semántico, a diferencia de otras fases, no se realiza claramente diferenciado del resto de las tareas que lleva a cabo el compilador, más bien podría decirse que el análisis semántico completa las dos fases anteriores de análisis léxico y sintáctico incorporando ciertas comprobaciones que no pueden asimilarse al mero reconocimiento de una cadena dentro de un lenguaje.

Funciones Principales

·                  Identificar cada tipo de instrucción y sus componentes

·                  Completar la Tabla de Símbolos

·                  Realizar distintas comprobaciones y validaciones:

ü  Comprobaciones de tipos.

ü  Comprobaciones del flujo de control.

ü  Comprobaciones de unicidad.

ü  Comprobaciones de emparejamiento.

El Analizador Semántico finaliza la fase de Análisis del compilador y comienza la fase de Síntesis, en la cual se comienza a generar el código objeto. La especificación de la semántica puede realizarse de dos formas:

·                  Lenguaje natural

·                  Especificación formal: Semántica Operacional, semántica denotacional, semántica Axiomática, Gramáticas con Atributos.

Acciones Semánticas

Dependiendo del tipo de sentencias, las acciones semánticas pueden agruparse en:

·                  Sentencias de Declaración: Completar la sección de tipos de la Tabla de Símbolos.

·                  Sentencias “ejecutables”: Realizar comprobaciones de tipos entre los operandos implicados.

·                  Funciones y procedimientos: Comprobar el número, orden y tipo de los parámetros actuales en cada llamada a una función o procedimiento.

·                   Identificación de variables: Comprobar si un identificador ha sido declarado antes de utilizarlo.

·                  Etiquetas: Comprobar si hay etiquetas repetidas y validación.

·                  Constantes: Comprobar que no se utilicen en la parte izquierda de una asignación.

·                  Conversiones y equivalencias de tipo: Verificación.

·                  Sobrecarga de operadores y funciones: Detectar y solventar.

Errores semánticos

Como ya se ha mencionado anteriormente, la función del análisis semántico es analizar el código y detectar errores de tipo semánticos de existir. Un error semántico es aquel que necesita información sensitiva al contexto para ser identificado. Algunos de estos errores reconocidos pueden ser:

• No coinciden los tipos
• Variable no declarada
• Identificador reservado uso indebido.
• Declaración de variables múltiples en un ámbito.
• Acceder a una variable fuera de alcance.
• Parámetro formal y real no coincide.

Compatibilidad de Tipos

Un compilador debe comprobar si el programa fuente sigue tanto las convenciones sintácticas como las semánticas del lenguaje fuente. Esta comprobación, llamada comprobación estática (para distinguirla de la comprobación dinámica que se realiza durante la ejecución del programa objeto), garantiza la detección y comunicación de algunas clases de errores de programación. Los ejemplos de comprobación estática incluyen: 

·         Comprobaciones de tipos. Un compilador debe informar de un error si se aplica un operador a un operando incompatible, por ejemplo, si se suman una variable tipo matriz y una variable de función. 

·         Comprobaciones del flujo de control. Las proposiciones que hacen que el flujo del control abandone una construcción deben tener algún lugar a dónde transferir el flujo de control Por ejemplo, una proposición break en C hace que el control abandone la proposición que la engloba, while, for o switch más cercana si dicha proposición englobadora no existe, ocurre un error. 

·         Comprobaciones relacionadas con nombres. En ocasiones, el mismo nombre debe aparecer dos o más veces en un mismo bloque de instrucciones, el compilador debe comprobar que se utilice el mismo nombre en ambos sitios.

Un comprobador de tipos se asegura de que el tipo de una construcción coincida con el previsto en su contexto.

Puede necesitarse la información sobre los tipos reunida por un comprobador de tipos cuando se genera el código.

Sistemas de Tipos

El diseño de un comprobador de tipos para un lenguaje se basa en información acerca de las construcciones sintácticas del lenguaje, la noción de tipos y las reglas para asignar tipos a las construcciones de lenguaje. En Pascal y en C, los tipos son básicos o construidos. Los tipos básicos son los tipos atómicos sin estructura interna por lo que concierne al programador (bolean, carácter, integer, real). Los tipos de subrango como 1.10, y los tipos enumerados, como (violeta, índigo, azul, verde, amarillo, naranja) se pueden considerar como tipos básicos. Además, los apuntadores y las funciones también pueden considerarse como tipos construidos.

·         Expresiones de tipos 

El tipo de una construcción de un lenguaje se denotará mediante una “expresión de tipo”. De manera informal, una expresión de tipo es, o bien un tipo básico o se forma aplicando un operador llamado constructor de tipos a otras expresiones de tipos. Los conjuntos de tipos y constructores básicos dependen del lenguaje que deba comprobarse. Cada lenguaje de programación requerirá unas expresiones de tipos adecuadas a sus características. A continuación, a modo de ejemplo, se definen las expresiones de tipos más comunes:

•      Tipos simples: Son expresiones de tipos los tipos simples del lenguaje, y algunos tipos especiales:
•       Integer 
•       Real 
•       Char 
•       Boolean 
•       Void 
•       Error

Los cuatro primeros son los tipos de datos simples más comunes en los lenguajes de programación, los dos últimos son tipos simples especiales que usaremos para su atribución a diversas partes de un programa, a fin de homogeneizar el tratamiento de todo el conjunto mediante el método de las expresiones de tipos.

·         Constructores de tipos: Permiten formar tipos complejos a partir de otros más simples. La semántica de cada lenguaje tiene asociada unos constructores de tipos propios. En general, en los lenguajes de programación se definen los siguientes constructores:

ü  Matrices: Si T es una expresión de tipos, entonces array(R,T)es también una expresión de tipos que representa a una matriz de rango R de elementos de tipo T.  Ejemplo: Sea el segmento de código C:  char a[10].

ü  Productos: Sea T1 y T2 expresiones de tipos, T1 x T2 es una expresión de tipos que representa al producto cartesiano de los tipos T1 y T2. A fin de simplificar consideraremos que el constructor u operador de tipos x es asociativo por la izquierda. 

ü  Registros: Sea un registro formado por los campos u1, u2 ... uN, siendo cada uno de ellos de los tipos T1,T2 ... TN, entonces, la expresión de tipos asociada al conjunto es: record ( (u1:T1) x (u2:T2) x ... x (uN:TN)).

ü  Punteros: Si T es una expresión de tipos, entonces pointer(T) es una expresión de tipos que representa a un puntero a una posición de memoria ocupada por un dato de tipo T. 

ü  Funciones: Sean T1,T2 ... TN, las expresiones de tipos asociadas a los segmentos de código correspondientes a los argumentos de una función, y sea T el tipo devuelto por la función. Entonces, la expresión de tipos asociada a la función es: ((T1xT2 x... xTN) -> T).

Las expresiones de tipo pueden contener variables cuyos valores son expresiones de tipos.

Estructura de la tabla de símbolos

·         Su estructura lógica viene determinada por:

ü  El tipo de ámbito (estático o dinámico)

ü  Los mecanismos de ámbito del lenguaje: procedimientos, bloques, herencia, módulos, espacios de nombres, registros, with.

ü  Si se da más de una pasada.

ü  Compilación separada: ficheros con tablas.

·         Su implementación física más eficiente suele ser la de una tabla hash, asociada a pila de ámbitos activos.

·         Las ristras (identificadores, constantes) pueden ir en lista(s) aparte.

Chequeos de tipos (y otros)

Un compilador debe realizar una serie de chequeos estáticos, como chequeos de tipos:

·         Consistencia: unicidad, existencia, no-ciclicidad,etc.

·         Equivalencia y compatibilidad de tipos Conversión explícita [cast] o forzada [coercion].

·         Inferencia de tipos (en valores).

·         Sobrecarga de funciones y operadores.

·         Funciones polimórficas, u otros (consistencia de instrucciones de control).

En otros casos, debe generar código para realizar chequeos dinámicos (p.e., valor dentro de rango).

Especificación de un Comprobador de Tipos Básico

Básicamente se deberán realizar dos tareas:

1. Asignación de tipos: En las declaraciones.

2. Evaluación y comprobación de tipos: En las expresiones y en las funciones, así como en las sentencias.

Sea la gramática:

P -> D ; S

D -> D ; D | id: T

T -> char | entero | real | booleano | array[num] of T | ^T | T à T

S -> id := E | if E then S | while E do S | S;S

E -> literal | num | id | id[E] | id^ | E op_lógico E | E op_arit E | E mod E | id(E)

Primer paso: Asignación de tipo

P à D ; S

D à D ; D

D à id : T {Añadir_TS(id.entrada, T.tipo}

T à char {T.tipo = char}

T à entero {T.tipo = entero}

T à real {T.tipo = real}

T à booleano {T.tipo = booleano}

T à array[num] of T1 {T.tipo = array(num.val, T1.tipo)}

T à ^T1 {T.tipo = puntero(T1.tipo)}

T à T1 à T2 {T.tipo = T1.tipo à T2.tipo}

Segundo paso: Comprobación de tipo en expresiones

E à literal {E.tipo = char}

E à num {E.tipo = entero}

E à id {E.tipo = Consultar_TS(id.entrada)}

E à id[E1]

{id.tipo = Consultar_TS(id.entrada)}

              {E.tipo =si (id.tipo=array(s,t) y E2.tipo=entero)

entonces t sino error_tipo}

E à E1 op_lógico E2

{E.tipo = si (E1.tipo=booleano y E2.tipo=booleano) entonces booleano sino error_tipo}

E à id^

{id.tipo = Consultar_TS(id.entrada)}

{E.tipo = si (id.tipo = puntero(t))entonces t sino error_tipo}

E à E1 mod E2

{E.tipo = si (E1.tipo=entero y E2.tipo=entero) entonces entero sino error_tipo}

E à id (E2)

{id.tipo = Consultar_TS(id.entrada)}

{E.tipo = si id.tipo = s y E1.tipo= s à t)entonces t sino error_tipo}

Conversiones de Tipos

Considérense expresiones como x + i donde x es de tipo real e i es de tipo entero. Como pa representación de enteros y reales es distinta dentro de un computador, y se utilizan instrucciones de máquina distintas para las operaciones sobre enteros y reales, puede que el compilador tenga que convertir primero uno de los operandos de + para garantizar que ambos operandos sean del mismo tipo cuando tenga lugar la suma.

La definición del lenguaje especifica las conversiones necesarias. Cuando un entero se asigna a un real, o viceversa, la conversión es al tipo del lado izquierdo de la asignación. En expresiones, la transformación más común es la de convertir el entero en un número real y después realizar una operación real con el par de operandos reales obtenidos. Se puede utilizar el comprobador de tipos en un compilador para insertar estas operaciones de conversión en la representación intermedia del programa fuente.

Coerciones
Se dice que la conversión de un tipo a otro es implícita si el compilador la va a realizar automáticamente. Las conversiones de tipo implícitas, también llamadas coerciones, se limitan en muchos lenguajes a situaciones donde en principio no se pierde ninguna información; por ejemplo, un entero se puede transformar en un real pero no al contrario. 

Se dice que la conversión es explícita si el programador debe escribir algo para motivar la conversión. Para un comprobador de tipos, las conversiones explícitas parecen iguales que las aplicaciones de función, así que no presentan problemas nuevos.
La conversión implícita de constantes se puede realizar generalmente en el momento de la compilación, mejorando a menudo el tiempo de ejecución del programa objeto.

Sobrecarga de funciones y operadores

Un símbolo sobrecargado es el que tiene distintos significados dependiendo de su contexto. La sobrecarga se resuelve cuando se determina un significado único para un caso de un símbolo sobrecargado. La resolución de la sobrecarga a menudo aparece referida como identificación de operadores porque determina la operación que denota un símbolo de operador.

Funciones polimórficas

Un procedimiento normal permite que las proposiciones de su cuerpo se ejecuten con argumentos de tipos fijos; cada vez que se llama un procedimiento polimórfico, las proposiciones de su cuerpo pueden ejecutarse con argumentos de tipos distintos. El término “polimórfico” también se aplica a cualquier parte de código que pueda ejecutarse con argumentos de tipos distintos, de modo que se puede hablar de funciones, así como de operadores polimórficos.

Gramáticas con 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”.

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.

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 à E {0}

S1 à E {1}….Sn-1 E {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:

Conclusión

El Analizador Semántico, como se ha podido notar durante el desarrollo de este articulo investigativo, tiene una gran importancia dentro del proceso de la compilación de códigos en cualquier lenguaje, ya que dé él depende la revisión del código en busca de errores semánticos en dicho código y de esta manera se asegura una coherencia y un sentido valido en el código según el lenguaje que esté escrito.

Además de esto, forma parte de un conjunto complejo de piezas que conforman el sistema de un intérprete de códigos o compilador, donde las tareas de cada pieza son de suma importancia, como también lo es la gramática correcta del lenguaje utilizado a interpretar, es por esto que un análisis semántico debe ser acertado.

Referencias Bibliográficas.

·         Aho, Alfred V.; Ravi Sethi, Jeffrey D. Ullman (2008). «Introducción a la Compilación».

·         Analisis  sematico   2001; Jose Fortes Galvez – p.2. (2001).

·         Análisis Semántico José M. Castaño Teoría de Lenguajes 2011 Departamento de Computación FCEyN, UBA. (2011).

·         Universidad Nacional del Santa Curso: Teoría de Compiladores Docente: Ing. Mirko Manrique Ronceros – (2008).

·         Compiladores: principios, técnicas y herramientas. A.V. Aho, R. Sethi, J.D. Ullman. Addison-Wesley Iberoamerica. (1990).

·         Construcción de compiladores. Principios y práctica. Kenneth C. Louden. Thomson-Paraninfo. (2004).