Es una descripción de la fase de análisis semántico de la compilación. Es una fase intermedia que vincula la fase de análisis

inicial de un compilador con la fase de síntesis final

ANÁLISIS SEMÁNTICO

AUTÓMATAS Y COMPILADORES

CALDAS DOMINGUEZ, ROQUE

Contenido

1. INTRODUCCIÓN-------------------------------------------------------------------------------------2

2. ATRIBUTOS Y GRAMÁTICA CON ATRIBUTOS------------------------------------------------3

A. ATRIBUTOS:--------------------------------------------------------------------------------------------------3

B. GRAMATICA CON ATRIBUTOS--------------------------------------------------------------------------3FORMA DE UNA SEMANTICA DIRIGIDA POR SINTAXIS------------------------------------------------------------4

3. NOTACIONES PARA LA ESPECIFICACIÓN DE UN TRADUCTOR---------------------------5

A. Definición dirigida por sintaxis (DDS):----------------------------------------------------------------5

B. ESQUEMA DE TRADUCCIÓN (ETDS)--------------------------------------------------------------------6

4. TRADUCCIÓN A UNA REPRESENTACIÓN INTERMEDIA------------------------------------7

A. ÁRBOL SINTÁCTICO ABSTRACTO-----------------------------------------------------------------------7

B. NOTACIÓN POSFIJA----------------------------------------------------------------------------------------8

C. CÓDIGO DES TRES DIRECCIONES-----------------------------------------------------------------------8

1.INTRODUCCIÓN

En el análisis léxico y sintáctico se han desarrollado las técnicas adecuadas para comprobar que una serie de palabras y símbolos están bien construidos respecto a las reglas impuestas por un lenguaje concreto. Pero el hecho de que estén bien construidos u ordenados no quiere decir que su significado sea el deseado por el creador del compilador, por lo que hay que comprobar que lo que se quiere hacer tiene sentido.

Esta fase de análisis trata de verificar que los tipos que intervienen en las expresiones sean compatibles entre sí, que los parámetros que se le pasan a los subprogramas sean los adecuados tanto en número como en tipo, que las funciones devuelven valores adecuados en cuanto al tipo, etc.

El análisis semántico involucra tanto la descripción de los análisis a realizar como la implementación de los análisis utilizando algoritmos apropiados. En este sentido, es semejante al análisis léxico y sintáctico. En el análisis sintáctico, por ejemplo, utilizamos gramáticas libres de contexto en la forma BNF para describir la sintaxis y diversos algoritmos de análisis sintáctico descendiente y ascendiente para implementar la sintaxis. En el análisis semántico la situación no es tan clara, en parte porque no hay un método estándar (como el BNF) que permita especificar la semántica estática de un lenguaje, y en parte porque la cantidad y categoría del análisis semántico varía demasiado de un lenguaje a otro. Un método para describir el análisis semántico que los escritores de compiladores usan muy a menudo con buenos efectos es la identificación de atributos, o propiedades, de entidades del lenguaje que deben calcularse y escribir ecuaciones de atributos o reglas semánticas, que expresan cómo el cálculo de tales atributos está relacionado con las reglas gramaticales del lenguaje. Un conjunto así de atributos y ecuaciones se denomina gramática con atributos. Las gramáticas con atributos son más útiles para los lenguajes que obedecen el principio de la semántica dirigida por sintaxis, la cual asegura que el contenido semántico de un programa se encuentra estrechamente relacionado con su sintaxis.

2.ATRIBUTOS Y GRAMÁTICA CON ATRIBUTOS

A. ATRIBUTOS:

Los atributos son información personalizada (semántica) de los símbolos (terminales y no terminales). Por lo que cada tipo de símbolo (terminales y no terminales) puede tener atributos diferentes. Esta información viaja a través del árbol de análisis sintáctico adjunta a cada símbolo (terminales y no terminales). Las acciones semánticas se encargan de manipular el contenido de los atributos para verificar que existe un significado correcto en la relación de los símbolos entre sí. Ejemplos típicos de atributos son:

El tipo de dato de una variable.

E l valor de una expresión.

La ubicación de una variable en la memoria.

E l código objeto de un procedimiento.

El número de dígitos significativos en un número.

Los atributos se pueden establecer antes del proceso de compilación (o incluso en la construcción de un compilador). Por ejemplo, el número de dígitos significativos en un número se puede establecer (o por lo menos dar un valor mínimo) mediante la definición de un Lenguaje. Además, los atributos solo se pueden determinar durante la ejecución del programa como el valor de una expresión (no constante). o la ubicación de una estructura de datos dinámicamente asignada. El proceso de calcular un atributo y asociar su valor calculado con la construcción del lenguaje en cuestión se define corno fijación del atributo. Los atributos que pueden fijarse antes de la ejecución se denominan estáticos mientras que los atributos que sólo se pueden fijar durante la ejecución son dinámicos.

B. GRAMATICA CON ATRIBUTOS Una gramática con atributos es una gramática de contexto libre cuyos terminales y no terminales pueden tener asociados atributos y las producciones pueden tener asociadas reglas de evaluación de los atributos. Cada símbolo puede tener asociado un número finito de atributos.

En la semántica dirigida por sintaxis los atributos están directamente asociados con los símbolos gramaticales del lenguaje (los terminales y no terminales). El valor de un atributo en un nodo de un árbol de análisis sintáctico (terminales y no terminales) se define mediante una regla semántica asociada a la producción utilizada en dicho nodo. El valor de un atributo sintetizado en un nodo se calcula a partir de los valores de los atributos de los hijos de dicho nodo en el árbol de análisis sintáctico; el valor de un atributo heredado se calcula a partir de los valores de los atributos en los hermanos y el padre de dicho nodo.

Un árbol de análisis sintáctico que muestre los valores de los atributos en cada nodo se denomina un árbol de análisis sintáctico con anotaciones. El proceso de calcular los valores de los atributos en los nodos se denomina anotar o decorar el árbol de análisis sintáctico.

FORMA DE UNA SEMANTICA DIRIGIDA POR SINTAXISCada producción puede tener asociada un número finito de reglas de evaluación de los atributos. Los valores de los atributos deberán estar asociados con un dominio de valores.

Sea G = (T, N, P, S) una gramática de contexto libre y C={c1 , c2 ,…,cn } el conjunto de atributos asociados con los símbolos (terminales y no terminales) de la gramática G.

Dada una regla de evaluación b→f (c1 ,…,ck ) asociado con la producción.

b depende de los atributos c 1,…,ck Una gramática con atributos es una semántica dirigida por la sintaxis en la que las funciones en las reglas semánticas no pueden tener efectos colaterales.

EJEMPLO: La definición dirigida por la sintaxis de la figura 2.1 es para un programa para una calculadora de escritorio. Esta definición asocia un atributo sintetizado con un valor entero llamado val a cada uno de los no terminales E, T y F. Para cada producción de E, T y E, la regla semántica calcula el valor del atributo val para el no terminal del lado izquierdo a partir de los valores de val de los no terminales del lado derecho.

PRODUCCIÓN REGLA SEMÁNTICAL→E print (E .val)

E→E+T E .val→E .val+T .val

E→T E .val→T . val

T→T∗F T . val→T .val∗F .val

T→F T . val→F .val

F→(E) F .val→(E .val)

F→digito F . val→digito . val

Figura 2.1|DEFINICIÓN DIRIGIDA POR SINTAXIS DE UNA CALCULADORA SENCILLA

3.NOTACIONES PARA LA ESPECIFICACIÓN DE UN TRADUCTOR

Existen dos formas de asociar acciones semánticas con reglas de producción.

Las más significativas tenemos:

A. Definición dirigida por sintaxis (DDS):

Consiste en asociar una acción semántica a una regla de producción, pero sin indicar cuando se debe ejecutar dicha acción.

En una DDS se hace lo mismo que en las gramáticas con atributos, pero además se puede manipular información externa a la gramática (esta manipulación es necesaria para implementar compiladores reales). De todas formas, no se indicará el orden de ejecución de las acciones semánticas.

Definido también como un formalismo para especificar las traducciones para las construcciones en función de atributos asociados con sus componentes sintácticos.

Se suele representar en una tabla con dos columnas y tantas fialas como reglas de la gramática. En la primera columna se pone la regla de la gramática y en la segunda las acciones semánticas asociadas a dicha regla.

Ejemplo

REGLASSEMANTICA

L→E“¿” print (E .val)

E→E1+T E . val=E1.val+T .val

E→T E . val=T .val

T→T 1∗FT .val=T 1. val∗F . val

T→F T .val=F .val

F→(E ) . val=E .val

F→cte F . val=cte . val

Ingresando la cadena 3+5*4

Su árbol sintáctico correspondiente sería:

Figura 3.2|ARBOL SEMANTICO PARA EL EJEMPLO

En una DDS especifica el valor de los atributos, pero no especifica la forma de evaluación.

Existen 2 tipos o métodos para la evaluación:

Evaluación mediante Grafos:

Es independiente del reconocimiento sintáctico. Durante el proceso de parsing se genera el grafo de dependencia de atributos.

Posteriormente se computan los valores de los atributos respetando el orden impuesto por el grafo de dependencias.

Evaluación durante el Parsing:

La evaluación se produce durante el reconocimiento sintáctico.

B. ESQUEMA DE TRADUCCIÓN (ETDS)Es una gramática atribuida en la que hay intercalados en el lado derecho de las reglas de producción, fragmentos de código de lenguaje de programación, que implementan acciones semánticas.

Un ETDS es un DDS en que se da un orden de ejecución de acciones semánticas. Las acciones semánticas se situarán a la derecha de los símbolos a los que se refieren y entre llaves. Esta regla de situar las acciones semánticas después de los símbolos que utilizan da un orden de ejecución.

La traducción en las ETDS solo puede realizarse de una sola pasada. Por lo tanto, no permitirá la herencia de atributos desde la derecha hacia la izquierda.

Los ETDS se utilizan a menudo para convertir un formato de un lenguaje en el formato de otro lenguaje.

4.TRADUCCIÓN A UNA REPRESENTACIÓN INTERMEDIA

Una estructura de datos que representa el programa fuente durante la traducción se denomina representación intermedia, o IR (por las siglas del término en inglés) para abreviar. A fin de realizar optimizaciones sobre un programa y para generar código, es conveniente producir una representación intermedia más adecuada para estas tareas que la representación del árbol de análisis sintáctico.

A. ÁRBOL SINTÁCTICO ABSTRACTOAunque un árbol sintáctico abstracto es una representación adecuada del código fuente, incluso para la generación de código, no se parecen ni remotamente al código objetivo, en particular en su representación de construcciones de flujo de control, donde el código objetivo, como el código de máquina o código ensamblador, emplean saltos más que construcciones de alto nivel, como las sentencias if y while. Por lo tanto, un escritor de compiladores puede desear generar una nueva forma de representación intermedia del árbol sintáctico que se parezca más al código objetivo o reemplace del todo al árbol sintáctico mediante una representación intermedia de esa clase, y entonces genere código objetivo de esta nueva representación. Una representación intermedia de esta naturaleza que se parece al código objetivo se denomina código intermedio.

Un árbol abstracto de sintaxis es un árbol de análisis sintáctico de información innecesaria, tal como las producciones únicas. Cada no hoja representa un operador y cada hoja representa un operando.

Así A+B podría tener los siguientes árboles: de análisis sintáctico y abstracto de sintaxis

Figura 4.3|ARBOL ABSTRACTO SINTACTICO

B. NOTACIÓN POSFIJA

La notación polaca posfija es una línea de código lineal que es más útil para la generación de código que para la fase de optimización, puesto que es difícil hacer las clasificaciones de las transformaciones en ella que se realizan durante la fase de optimización. En esencia, la notación polaca posfija coloca primero los operandos seguidos por su operador.

De este modo,

A+B

Se convierte en

AB+¿

Y

A+B∗C

Se transforma

ABC∗+¿

C. CÓDIGO DES TRES DIRECCIONES

El código de tres direcciones es un lenguaje intermedio usado por compiladores optimizadores para ayudar en las transformaciones de mejora de código. La instrucción básica del código de tres direcciones está diseñada para representar la evaluación de expresiones aritméticas y tiene la siguiente forma general:

X=Y opZ

Cada instrucción de código de tres direcciones tiene a lo sumo tres operandos y es típicamente una combinación de asignación y operador binario por ejemplo t 1=t 2+t 3 .

Ya que el código de tres direcciones es usado como un lenguaje intermedio en los compiladores, los operando normalmente no contendrán direcciones de memoria o registros concretos, sino que direcciones simbólicas que serán convertidas en direcciones reales durante la asignación de registros.

El nombre "código de tres direcciones" viene de esta forma de instrucción, ya que por lo general cada uno de los nombres X, Y y Z representan una dirección de la memoria. Sin embargo, observe que el uso de la dirección de x difiere del uso de las direcciones de Y y Z, y que tanto Y como Z (pero no x) pueden representar constantes o valores de literales sin direcciones de ejecución.

Obsérvese que no se permite ninguna expresión aritmética compuesta, pues solo hay un operador en el lado derecho de una proposición. Para ver cómo las secuencias de código de tres direcciones de esta forma pueden representar el cálculo de una expresión, considere la expresión aritmética:

2∗a+(b−3)

Como árbol sintáctico

Figura 4.4| ÁRBOL SINTÁCTICO

El código de tres direcciones correspondiente es:

t 1=2∗a

t 2=b−3

t 3=t 1+t 2

Esta descomposición de expresiones aritméticas complejas y de preposiciones de flujo del control anidadas hace el código de tres direcciones deseable para la generación de código objeto y para la optimización. El uso de nombres para los valores intermedios calculados por un programa permite que el código de tres direcciones se reorganice fácilmente.