Traducción dirigida por la Sintaxis

Teoría de Autómatas y Lenguajes FormalesAlma María Pisabarro, 2007

TRADUCCIÓN DIRIGIDA POR LA SINTAXIS

Para traducir una construcción de un lenguaje de programación un compilador necesita el código generado para la construcción, y además:

• Tipo de la construcción• Posición de la primera instrucción del código

objeto• Número de instrucciones generadas ...Los atributos se mencionan de forma abstracta.

Un atributo puede representar cualquier cantidad un tipo, una cadena, una posición de memoria o cualquier otra cosa)

TRADUCCIÓN DIRIGIDA POR LA SINTAXIS

• Una definición dirigida por la sintaxis es una generalización de una gramática independiente de contexto en la que cada símbolo gramatical tiene asociado un conjunto de atributos– Especifica la traducción de una construcción en función de los

atributos asociados con sus componentes sintácticos• Un esquema de traducción es una gramática

independiente de contexto en la que se asocian atributos con los símbolos gramaticales y se insertan acciones semánticas encerradas entre llaves dentro de los lados derechos de las reglas de producción – Es una notación orientada a procedimientos que se utiliza para

especificar traducciones

DEFINICIONES DIRIGIDAS POR LA SINTAXIS

• Utilizan una gramática independiente de contexto para especificar la estructura sintáctica de la entrada

• A cada símbolo de la gramática se le asocia un conjunto de atributos

• A cada regla de la gramática se le asocia un conjunto de reglas semánticas para calcular los valores de los atributos asociados con los símbolos de esa regla

• La gramática y el conjunto de reglas semánticas constituyen la definición dirigida por la sintaxis

DEFINICIONES DIRIGIDAS POR LA SINTAXIS

Una traducción es una transformación de una entrada en una salida. La salida para cada entrada W se especifica como sigue:

• Se construye un árbol sintáctico para W• Suponiendo que un nodo n del árbol está etiquetado con

el símbolo X de la gramática se escribe X.a para indicar el valor del atributo a de X en ese nodo

• El valor de X.a en n se calcula por la regla semántica para el atributo a asociado a la regla X utilizada en el nodo n

El árbol de análisis sintáctico que muestra los valores de los atributos en cada nodo se denomina árbol de análisis sintáctico con anotaciones

ATRIBUTOS• El conjunto de atributos asociado a cada

símbolo gramatical se divide en dos subconjuntos– Atributos sintetizados. Se pueden calcular durante

un solo recorrido ascendente del árbol de análisis sintáctico

– Atributos heredados. Sirven para expresar la dependencia de una construcción en de un lenguaje en el contexto en el que aparece

• Si se considera un nodo de un símbolo gramatical de un árbol sintáctico como un registro para guardar información entonces un atributo se corresponde con el nombre de un campo

• Un atributo puede representar cualquier cosa (una cadena, un número, un tipo, una posición de memoria...)

• El proceso de calcular los valores de los atributos en los nodos se denomina anotar o decorar el árbol de análisis sintáctico

• El valor de un atributo se define mediante la regla semántica asociada a la regla de producción utilizada en ese nodo– El valor de un atributo sintetizado se calcula a partir de los

valores de los atributos de los hijos de ese 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 de los hermanos y el padre de ese nodo

• En una definición dirigida por la sintaxis, se asume que los terminales sólo tienen atributos sintetizados (la definición no proporciona ninguna regla semántica para los terminales)

• Los valores para los atributos de los terminales son proporcionados generalmente por el analizador léxico

REGLAS SEMÁNTICAS• Las reglas semánticas establecen las

dependencias entre los atributos que serán representadas mediante un grafo

• El grafo de dependencias proporciona el orden de evaluación de las reglas semánticas

• La evaluación de las reglas semánticas define los valores de los atributos de los nodos del árbol

• Una regla semántica puede tener también efectos colaterales (imprimir un valor, actualizar una variable global...)

• Una gramática con atributos es una definición dirigida por la sintaxis en la que las funciones de las reglas semánticas no pueden tener efectos colaterales

EJEMPLODefinición Dirigida por la Sintaxis

de una calculadora de escritorio sencilla

Producción Reglas Semánticas

L → E n print (E.val)

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

E → T E.val := T.val

T → T1 * F T.val := T1.val x F.val

T → F T.val := F.val

F → ( E ) F.val := E.val

F → digito F.val := digito.valex

ESQUEMAS DE TRADUCCIÓN• Un esquema de traducción es una gramática

independiente de contexto en la que se encuentran intercalados, en los lados derechos de las reglas de producción, fragmentos de programa llamados acciones semánticas

• Es como una definición dirigida por la sintaxis con la diferencia de que el orden de evaluación de las reglas semánticas se muestra explícitamente

• Los esquemas de traducción pueden tener tanto atributos sintetizados como heredados

EJEMPLOEsquema de Traducción simple que transforma

expresiones infijas con suma y resta en las posfijas correspondientes

E → T RR → opsuma T { print (opsuma.lexema) } R1 | ε

T → num { print (num.val) }

RESUMEN: Traducción Dirigida por la Sintaxis• Se asocia información a una construcción del

lenguaje proporcionando atributos a los símbolos de la gramática que representan la construcción

• Los valores de los atributos se calculan mediante reglas semánticas asociadas a las reglas gramaticales

• Hay dos notaciones para asociar las reglas semánticas con las reglas de producción:– Las definiciones dirigidas por la sintaxis

• Ocultan muchos detalles de la implantación• No es necesario que el usuario especifique explícitamente el

orden en el que tiene lugar la traducción– Los esquemas de traducción

• Indican el orden en el que tiene lugar la traducción• Así, algunos detalles de la implantación quedan visibles

Conceptualmente, sea cual sea la notación utilizada:• Se analiza sintácticamente la cadena de

componentes léxicos de entrada• Se construye el árbol de análisis sintáctico• Se recorre el árbol para evaluar las reglas

semánticas en sus nodos– La evaluación de las reglas semánticas puede generar

código, guardar información en un atable de símbolos, emitir mensajes de error o realizar otras actividades

• La traducción de la cadena de componentes léxicos es el resultado obtenido al evaluar las reglas semánticas

cadena de entrada

árbol de análisis

sintáctico

grafo de dependencias

orden de evaluación de las reglas semánticas