UNIDAD 6: TRADUCCIÓN DIRIGIDA POR SINTAXIS

 

TRADUCCIÓN DIRIGIDA POR SINTAXIS

Un compilador utiliza gramáticas independientes de contexto como guía para la traducción de lenguajes, si logra de alguna manera asociar información a las distintas construcciones del lenguaje de programación proporcionando atributos a los símbolos de la gramática, puede entonces calcular sus valores mediante reglas semánticas.

Aunque hay dos maneras de hacer la asociación entre reglas semánticas y producciones, que son mediante definiciones dirigidas por sintaxis y esquemas de traducción, nos interesa particularmente ésta última, pues con éstas se trabaja más pues se puede definir el orden en que se ejecutan las acciones y las evaluaciones de los atributos.

La idea es brindar al lector una pequeña reseña de lo que el compilador hace desde que toma una cadena de entrada hasta que la lleva a evaluar las reglas semánticas, que es una parte importante del proceso de compilación en un lenguaje de programación.

5.1 DEFINICIONES DIRIGIDAS POR LA SINTAXIS

Para traducir una construcción de un lenguaje de programación, un compilador puede necesitar tener en cuenta muchas características, además del código generado para la construcción. Una definición dirigida por sintaxis es un formalismo para especificar las traducciones para las construcciones en función de atributos asociados con sus componentes sintácticos.

Utiliza una gramática independiente de contexto para especificar la estructura sintáctica de la entrada, la idea es asociar con cada símbolo de la gramática un conjunto de atributos (que luego veremos que pueden ser sintetizados o heredados) y además a cada producción un conjunto de reglas semánticas para calcular los valores de los atributos asociados con los símbolos que aparecen en esa producción. La definición dirigida por sintaxis consiste en sí entonces de la gramática y el conjunto de reglas semánticas.

En una definición dirigida por sintaxis, para cada producción gramatical A􀃆α se asocia un conjunto de reglas semánticas de la forma b:=f(c1,c2,…,ck) donde f es una función y b es un atributo sintetizado de A o un atributo heredado de uno de los símbolos gramaticales de la parte derecha de la producción y c1,c2,…,ck son atributos que pertenecen a los símbolos gramaticales de la producción. Se dice que b depende de c1,c2,…,ck.

5.2 ANÁLISIS DE LAS DEFINICIONES DIRIGIDAS POR SINTAXIS

Las funciones para un no terminal mapen los valores de los atributos heredados de un nodo con atributos sintetizados. Mientras que para los terminales se debe realizar una función por aparte, es decir distinta de la de los no terminales, sin embargo los terminales se pueden considerar como un solo grupo y ser evaluados con una simple función [1], la agrupación de dichos atributos está determinada por las dependencias que se presentan con el conjunto de reglas semánticas especificadas en la definición orientada a la sintaxis.

La traducción dirigida a sintaxis es motivada por la sobrecarga de identificadores los cuales tiene un conjunto de posibles tipos y por lo tanto una expresión debe de elegir uno de esos tipos para cada subexpresión que involucre a dicho identificador [1]. Para solucionar dicho problema se debe de realizar un análisis ascendente para determinar los valores sintetizados y un análisis descendente para seleccionar el tipo adecuado para la expresión. Es decir, la principal implementación del análisis de las traducciones dirigidas a sintaxis es el chequeo de tipos.

Existen definiciones orientadas a sintaxis que se llaman circulares debido a que su grafo de dependencia posee ciclos y no existe ninguna forma para poder calcular los valores de los atributos en el ciclo.

5.3 EVALUACIÓN ASCENDENTE DE LAS DEFINICIONES S-ATRIBUIDAS

Los atributos se pueden evaluar con un analizador sintáctico ascendente conforme la entrada es analizada. El analizador sintáctico puede conservar en su pila los valores de los atributos sintetizados asociados con los símbolos gramaticales. Siempre que se haga una reducción se calculan los valores de los nuevos atributos sintetizados a partir de los atributos que están en la pila para los símbolos gramaticales del lado derecho de la producción con la que se reduce.

5.3.1 Atributos sintetizados en la pila del analizador sintáctico

A partir de una definición con atributos sintetizados, el generador de analizadores sintácticos puede construir un traductor que evalúe los atributos conforme analiza la entrada. Un analizador sintáctico ascendente utiliza una pila para guardar información acerca de los subárboles que ya han sido analizados. Se pueden utilizar campos adicionales en la pila del analizador para guardar los valores de los atributos sintetizados.

5.4 DEFINICIONES L-ATRIBUIDAS

Cuando la traducción tiene lugar durante el análisis sintáctico, el orden de evaluación de los atributos va unido al orden en que, por el método de análisis sintáctico, se crean los nodos del árbol de análisis sintáctico. Un orden natural que caracteriza es el orden de evaluación en profundidad. Aunque de hecho no se construye el árbol de análisis sintáctico, es útil estudiar la traducción durante el análisis sintáctico considerando la evaluación en profundidad de los atributos en los nodos de un árbol de análisis sintáctico.

Se les llama “por la izquierda” porque la información de los atributos parece fluir de izquierda a derecha. Las definiciones con atributos por la izquierda incluyen todas las definiciones dirigidas por sintaxis basadas en gramáticas LL(1). Toda definición con atributos sintetizados es una definición con atributos por la izquierda.

5.5 TRADUCCIÓN DURANTE EL ANÁLISIS DESCENDENTE

Se trabaja con esquemas de traducción en lugar de hacerlo con definiciones dirigidas por sintaxis, así que se puede ser explícito en cuanto al orden en que tienen que lugar las acciones y las evaluaciones de los atributos.

Eliminación de la recursividad izquierda de un esquema de traducción

Como la mayoría de los operadores aritméticos son asociativos por la izquierda, es natural utilizar gramáticas recursivas por la izquierda para las expresiones. La transformación se aplica a esquemas de traducción con atributos sintetizados.

Para el análisis sintáctico descendente, se supone que una acción se ejecuta en el mismo momento en que se expandiría un símbolo en la misma posición. Un atributo heredado de un símbolo debe ser calculado por una acción que aparezca antes que el símbolo, y un atributo sintetizado del no terminal de la izquierda se debe calcular después de que hayan sido calculados todos los atributos de los que depende.

Diseño de un traductor predictivo

Un analizador sintáctico predictivo es un tipo especial de analizador sintáctico descendente recursivo en el que el símbolo del preanálisis determina sin ambigüedad el procedimiento seleccionado para cada no terminal. La secuencia de procedimientos llamados en el procesamiento de la entrada define

implícitamente un árbol de análisis sintáctico para la entrada.

La idea es generalizar la construcción de analizadores sintácticos predictivos para implantar un esquema de traducción basado en una gramática adecuada para el análisis sintáctico descendente. Un atributo heredado de un símbolo debe ser calculado por una acción que aparezca antes que el símbolo, y un atributo sintetizado del no terminal de la izquierda se debe calcular después de que hayan sido calculados todos los atributos de los que depende.

5.6 EVALUACIÓN ASCENDENTE

Existe un método, con el cual se puede implementar cualquier definición de una sintaxis que se base en atributos L, es decir, heredados por la izquierda en gramáticas LL(1) y muchos (no todos) basados en LR(1). Este método consiste en primero tomar el esquema de traducción orientada a sintaxis que posee las acciones semánticas incrustadas y remover dichas acciones, luego se debe insertar en su lugar un no terminal distinto para cada una de las producciones, el cual funciona como marca. Finalmente se agrega una producción extra a partir del no terminal marcador, que derive a épsilon y la acción a ejecutar (la acción removida anteriormente) [1].

Un ejemplo de dicho cambio a realizar, se presenta en la figura siguiente en donde se muestra el esquema original a) y se indica la modificación que se debe realizar b) usando como marcador un no terminal M y N en donde ambos esquemas de traducción aceptan el mismo lenguaje.

El objetivo del análisis ascendente es realizar reducción, por ejemplo con una producción A 􀃆 XY, se pretende reemplazar su parte derecha por el no terminal que se encuentra a en la parte izquierda de la producción, esto se puede llevar a cabo, debido a que si el valor Y posee un valor heredado, este estaría determinado por el valor estático de X el cual se encuentra en la pila [1] Se puede determinar que el valor de X.s se encuentra en la pila debido a que se realiza un análisis de abajo hacia arriba y se analizará primero el valor de X el cual determina a valor heredado de Y ya que este último depende de X, como se mostraría en su grafico de dependencia.

El comportamiento de la gramática modificada es el siguiente: el marcador de cada producción toma el valor estático del no terminal que posee a la izquierda como su valor heredado y sintetizado, lo cual permite que el no terminal que se encuentra a la derecha del marcador tome como valor heredado el recién adquirido valor sintetizado del marcador como se muestra en las siguientes figuras.

Gracias al trabajo realizado por las marcas (no terminales) es posible evaluar atributos L durante el análisis sintáctico LR, debido a que solo existe una única producción para cada marcado la gramática continua siendo LL y por ende LR [1], al agregar los marcadores no se produce ningún conflicto. Sin embargo, no se puede decir lo mismo de todas las gramáticas LR porque algunas si podrían presentar problemas de conflictos. A continuación se presenta un ejemplo de una gramática LR que presenta problemas a la hora de realizar el análisis sintáctico debido a que en la última de sus producciones no existe un no terminal con el cual se pueda determinar cuál es el valor heredado de L.count a imprimir y con el cual se conoce el total de Ls generadas por S.

A veces es posible cambiar los valores heredados por valores sintetizados al hacer una pequeña modificación en la gramática, este cambio nos permite trabajar de manera más eficiente ya que los valores de un atributo para determinado terminal se pueden obtener de manera directa en vez de tener que heredarlo. Ejemplo de la característica anterior se presenta en el lenguaje de programación de Pascal [1], como se muestra en la figura siguiente donde se trata la producción D que permite definir una variable L con su respectivo tipo T.

La modificación anterior se realiza con el fin de que el tipo de una variable este en el subárbol que genera L, de manera que L posea un atributo de tipo sintetizado que almacena el tipo de la variable del identificador generado por L [1], en vez de tener que heredarlo.