Captulo 5: Evaluacin de Gramticas Atribuidas

En una gramtica atribuida (o definicin dirigida por sintaxis) no se especifica el modo en el que se han de calcular los atributos, sino los valores que stos deben tomar en funcin de otros. La evaluacin de los mismos se llevar a cabo posteriormente mediante una herramienta evaluadora de gramticas atribuidas, un determinado recorrido del AST o empleando un mecanismo ms dirigido hacia la sintaxis del lenguaje, conocido como esquema de traduccin.

5.1. Grafo de DependenciasDada una gramtica atribuida, cada produccin tendr asociada un grafo de dependencias locales en el que se establecen, mediante un grafo dirigido, las dependencias existentes entre todos los atributos que aparecen en la produccin.Dicho grafo tendr un nodo por cada uno de los atributos que aparezcan en las reglas semnticas asociadas a la produccin.

En la representacin de un grafo de dependencias locales de una produccin, cada nodo que representa un atributo de un smbolo gramatical X estar agrupado con el resto de atributos (nodos) asociados al mismo smbolo gramatical. As, el grafo estar estructurado en base al rbol sintctico y, por tanto, se suele representar superpuesto al subrbol sintctico correspondiente a la produccin.

Ejemplo: En el Ejemplo 15 presentamos una gramtica atribuida que comprobaba la validez semntica de las expresiones de un pequeo lenguaje de programacin.

Para la ltima produccin tenamos las siguientes reglas semnticas asociadas:

Ntese como las dependencias de los atributos, explicitadas en las reglas semnticas, estn representadas mediante aristas dirigidas. Adems, cada atributo de un smbolo gramatical est ubicado al lado de ste, superponiendo el grafo de dependencias al subrbol sintctico (en tono gris) correspondiente a la produccin asociada.

Ejemplo: Empleando la misma gramtica atribuida del Ejemplo 15, el siguiente programa:

Satisface las restricciones sintcticas y semnticas del lenguaje definido por dicha gramtica atribuida. Para ello, se definieron unos atributos y un conjunto de reglas semnticas que defina la dependencia entre ellos. Haciendo uso de la gramtica libre de contexto y de las reglas semnticas definidas sobre sta, podremos obtener el siguiente grafo de dependencias:

Sobre el rbol sintctico se ha ubicado todo atributo asociado a los smbolos gramaticales.En cada una de las derivaciones del rbol (agrupacin de un nodo y sus hijos) generada por la correspondiente produccin de la gramtica, se representa el grafo de dependencias locales.El grafo resultante es el grafo de dependencias obtenido para el programa de entrada.

Ordenamiento topolgico del grafo de dependenciasUn ordenamiento topolgico de un grafo de dependencias es todo ordenamientom ,m ,...,mk 1 2 de los nodos del grafo tal que las aristas vayan desde los nodos que aparecen primero en el orden a los que parecen ms tarde; es decir, si i j m m es una arista desdei m a j m , entonces i m aparece antes que j m en el orden topolgico.

Ejemplo A raz del grafo de dependencias del Ejemplo 25, podemos establecer un ordenamiento topolgico de los nodos del mismo. Para ello, numeramos los atributos conforme a la dependencia que puedan tener entre s:

Los nmeros iniciales son asignados a los nodos que no poseen ninguna dependencia de otro nodo. Una vez hecho esto, se numeran los nodos consecutivamente conforme dependan de otros nodos que posean un valor menor. Pueden existir distintas numeraciones.

Un ordenamiento topolgico de los nodos del grafo establece un orden vlido en el que se pueden evaluar las reglas semnticas asociadas a los nodos del rbol. De este modo, el orden de ejecucin de las reglas semnticas ser el indicado por los nodos del grafo. Si un nodo del grafo corresponde a un smbolo terminal, no habr que calcular su atributo puesto que ste ya fue sintetizado por el analizador lxico.

Evaluacin de una gramtica atribuida

Para llevar a cabo el proceso de evaluacin de una gramtica atribuida existen principalmente dos mtodos:Mtodos de rbol sintctico: En el momento de procesamiento del lenguaje, estos mtodos obtienen un orden de evaluacin a partir de un ordenamiento topolgico del grafo de dependencias, construido para cada entrada. Para poder llevarlo a cabo, se tiene que comprobar la no-circularidad de la gramtica atribuida, cuya ejecucin es de complejidad exponencial. Adicionalmente, la creacin del grafo de dependencias y la obtencin de un ordenamiento topolgico cada vez que se procesa un programa, supone una complejidad adicional. Existen herramientas que implementan este mtodo generando, tras escribir la gramtica con una sintaxis determinada, un evaluador de la misma si sta no es circular; ejemplos de estas herramientas son FNC-2 [FNC2], Ox [Bischoff92], Elegant [Jansen93] o lrc [LRC].

Mtodos basados en reglas: La alternativa al mtodo anterior, adoptado por prcticamente la totalidad de los desarrollos, se basa en analizan las reglas de la gramtica atribuida en el momento de la construccin del compilador, fijando a priori el orden de evaluacin de las mismas.

5.2. Evaluacin de Atributos en una PasadaCuando el procesador de lenguaje es de una pasada, la evaluacin de los atributos de una gramtica atribuida (y por tanto la ejecucin de cada una de sus reglas semnticas) es llevada a cabo al mismo tiempo que se produce el anlisis sintctico.Histricamente, la posibilidad de que un compilador pudiese llevar a cabo todas sus fases durante el anlisis sintctico en una nica pasada era de especial inters por el ahorro computacional y de memoria que representaba. En la actualidad, al existir mayor capacidad de cmputo y memoria de los computadores, dicho caracterstica no cobra tanta importancia. Al mismo tiempo, la complejidad de los lenguajes actuales hace que sea obligatorio su procesamiento en varias pasadas.

Un factor importante es que la mayora de los algoritmos de anlisis sintctico procesan el programa de entrada de izquierda a derecha (por esta razn los analizadores sintcticos ascendentes o LR, y descendentes o LL, comienzan con una L). Este orden implica una restriccin en la evaluacin, puesto que la utilizacin de los atributos de los elementos terminales de la gramtica debe seguir este mismo orden.Evaluacin ascendente de gramticas S-atribuidasToda gramtica S-atribuida se puede evaluar ascendentemente, calculando los atributostodos ellos sintetizados conforme el programa de entrada es analizado [Aho90]. El analizador sintctico deber almacenar en su pila los valores de los atributos sintetizados asociados a cada uno de los smbolos gramaticales. En el momento en el que se lleve a cabo una reduccin, se calcularn los valores de los nuevos atributos sintetizados (del no terminal de la izquierda de la produccin) en funcin de los atributos que estn en la pila (de los no terminales de la parte derecha, entre otros). Este mecanismo es el llevado a cabo por la herramienta yacc/bison.

El poder clasificar una gramtica atribuida como S-atribuida ofrece, por tanto, dos beneficios frente al concepto general de gramtica atribuida:1. Sin necesidad de calcular el grafo de dependencias, se conoce a priori el orden de ejecucin de las reglas semnticas. No es necesario ordenar topolgicamente el grafo (ni siquiera crearlo) para conocer su orden de evaluacin.2. Slo es necesario visitar una vez cada nodo del rbol sintctico creado ante la entrada de un programa36. Una vez ejecutada la regla semntica asociada al nodo del rbol, no necesitar volver a procesar ste. Esta propiedad conlleva una clara mejora de eficiencia en tiempo de compilacin.

Evaluacin descendente de gramticas L-atribuidasDada una gramtica atribuida que cumpla las condiciones de gramtica Latribuida37, podr ser evaluada mediante un analizador sintctico descendente recursivo: La gramtica libre de contexto deber ser LL Cada smbolo no terminal ser traducido a una funcin (mtodo) que reciba sus atributos heredados como parmetros y devuelva sus atributos sintetizados en cada invocacin. Cada mtodo asociado a un no terminal ha de realizar, adems del anlisis sintctico, la evaluacin de sus reglas semnticas asociadas. Los atributos heredados de un no terminal A debern ser calculados antes de la invocacin a su mtodo asociado, y stos debern ser pasados como parmetros a la misma. Los atributos sintetizados de un no terminal A debern ser calculados en la implementacin de su funcin (mtodo) y devueltos tras su invocacin.

5.3. Evaluacin de Atributos en Varias Pasadas

Por elemplo identifica que las dos tareas principales a llevar a cabo por un lenguaje de programacin tpico (con tipos y mbitos estticos) son la comprobacin de mbitos y tipos. Para ello, el analizador semntico puede desarrollarse en dos pasadas: Identificacin: Aplicando las reglas de mbitos que define el lenguaje, cada utilizacin de un identificador en una expresin ser resuelta conociendo su entidad concreta dentro del programa de entrada. El resultado de este recorrido delAST es que cada nodo de tipo identificador tendr asociado una referencia a su smbolo y tipo apropiados.Comprobacin de tipos: Posteriormente a la pasada de identificacin, se va recorriendo en AST para, aplicando las reglas semnticas de inferencia de tipos del lenguaje, poder asignar un tipo a las distintas construcciones del programa. Conforme se van infiriendo los tipos, se realizarn las comprobaciones de que las operaciones llevadas a cabo con los mismos sean las correctas.5.4. Rutinas Semnticas y Esquemas de TraduccinUna gramtica libre de contexto en la que se asocian atributos con los smbolos gramaticales y se insertan rutinas semnticas dentro de las partes derecha de las producciones [Aho90]. Lasrutinas semnticas son, a su vez, fragmentos de cdigo que el desarrollador del compilador escribe normalmente entre llaves {} dejando explcito el momento en el que la herramienta ha de ejecutar la misma, durante su proceso de anlisis.La principal diferencia entre las herramientas que emplean gramticas atribuidas y aqullas que ofrecen esquemas de traduccin es que en las segundas el desarrollador especifica el momento en el que se ha de ejecutar el cdigo. Sin embargo, en las gramticas atribuidas y definiciones dirigidas por sintaxis, el proceso de evaluacin de los atributos debe ser resuelto por la propia herramienta. La evaluacin de una gramtica atribuida, conlleva procesos como la creacin y ordenamiento topolgico de un grafo de dependencias, o la limitacin a priori de las caractersticas de la gramtica.

Captulo 6: Comprobacin de TiposEs la parte del anlisis semntico encargada de asegurar que el tipo de toda construccin del lenguaje coincida con el previsto en su contexto, dentro de las reglas semnticas del lenguaje. Si dichas reglas no se cumplen, se produce un conflicto u error de tipo

Ejempl: La siguiente sentencia en el lenguaje ANSI C:

Es sintcticamente correcta, pero el comprobador de tipos de la fase de anlisis semntico deber comprobar un conjunto de restricciones que se han de cumplir en el contexto de laexpresin: Las variables i y j han de estar declaradas, tener definas en su tipo la operacin suma, y calcular (inferir) el tipo de dicha operacin. Respecto al tipo calculado, deber ser entero o convertible implcitamente (promocionable) a entero, puesto que en C los ndices de un array han de ser enteros. La variable v deber estar declarada y poseer como tipo un array o puntero (en C el operador [] se puede aplicar a punteros) de punteros a otro tipo T. De este modo, se podrn aplicar los dos operadores [] y * a dicho identificador. Finalmente, la funcin (o procedimiento) f tendr que haber sido declarada previamente y poseer un nico parmetro de tipo T o promocionable a un tipo T.Todas estas tareas debern ser llevadas a cabo por una parte del analizador semntico: el comprobador de tipos.

6.1. Beneficios del Empleo de Tipos

Tenemos:Fiabilidad. La comprobacin esttica de tipos reduce el nmero de errores que un programa puede generar en tiempo de ejecucin. ste es el beneficio ms obvio ya que, gracias a la deteccin temprana de los errores, el programador podr reparar stos de un modo casi inmediato y no cuando se est ejecutando la aplicacin, pudiendo incluso haber sido implantada.Abstraccin: Otra ventaja de emplear tipos en los lenguajes de programacin es que su uso fuerza al programador a dividir el problema en diversos tipos de mdulos, de un modo disciplinado.Los tipos identifican la interfaz de los mdulos (funciones, clases, paquetes o componentes) proporcionando una simplificacin de los servicios que ofrece cada mdulo; un tipo de contrato parcial entre los desarrolladores del mdulo y sus clientes.El estructurar sistemas complejos en distintos mdulos con interfaces claras hace que los diseos puedan poseer una mayor abstraccin, de modo que las interfaces puedan ser diseados y debatidos de un modo independiente a su posterior implementacin.Legibilidad: Un tipo de una entidad (variable, objeto o funcin) transmite informacin acerca de lo que se intenta hacer con ella, constituyendo as un modo de documentacin del cdigo.Eficiencia: Como hemos comentado en la propiedad anterior, una entidad de un programa declarada con un tipo especfico indica informacin relativa a lo que se intenta hacer con ella. De este modo, al conocer el tipo de las construcciones del lenguaje, se podr generar cdigo de carcter ms especfico y eficiente que si no tuvisemos esa informacin. En el caso de no poseer tipos en tiempo de compilacin, debera descubrirse la ejecucin especfica dinmicamente con la consecuente prdida de eficiencia.

6.2. Definicin de Tipo

Existen tres modos de definir el concepto de tipo, en funcin de distintos puntos de vista, todos ellos compatibles entre s:

Denotacional:Este concepto de tipo est enfocado a la representacin de sus posibles valores, es decir, a su significado o valor. De este modo, la definicin denotacional de tipo est muy ligada a la fase de generacin de cdigo, ya que en esta fase se genera un programa de salida con igual semntica que el programa de entrada, pero expresada en otro lenguaje de programacin.Basado en la abstraccin: Desde este punto de vista, un tipo es una interfaz consistente en un conjunto de operaciones que se pueden realizar sobre ste.Constructivo: Un tipo es definido como un conjunto de tipos simples53 (tambin llamados predefinidos, bsicos o primitivos), o bien un tipo compuesto o construido formado a partir de otros tipos.Este modo de ver los tipos posee principalmente un carcter interno al compilador, indicando un modo de representarlos para implementar las distintas fases del procesador de lenguaje.

6.3. Expresin de TipoUna expresin de tipo es un modo de expresar el tipo de cualquier construccin de un lenguaje, es decir, es la forma en el que un procesador de lenguaje representa cada tipo del lenguaje que procesa. Las expresiones de tipo se centran en la definicin constructiva de un tipo. As, una expresin de tipo es, o bien un tipo bsico, o el resultado de aplicar un constructor de tipos a otras expresiones de tipos.

Ejemplo. En el lenguaje Pascal, un tipo subrango de valores enteros comprendidos entre 0 y 9 puede definirse del siguiente modo:

Del mismo modo, un tipo enumerado de tres enteros distintos puede definirse, en el lenguajeC, del siguiente modo:

Tanto los valores enumerados como los subrangos son un subconjunto del tipo entero.Expresiones de tipo de los dos ejemplos pueden ser 0..9 y [rojo,verde,azul].

6.4. Sistema de Tipos

Un sistema de tipos es un conjunto de reglas para asignar expresiones de tipos a las distintas construcciones de un lenguaje [Aho90]. Para ello, un sistema de tipos deber definir sus expresiones de tipos, asignar stas a las distintas construcciones sintcticas del lenguaje, y comprobar que las reglas semnticas de los tipos del lenguaje se cumplan ante cualquier programa de entrada.Un comprobador de tipos de un lenguaje de programacin deber implementar un sistema de tipos. En las reglas definidas por un sistema de tipos se deber tener en cuenta conceptos como equivalencia, compatibilidad, conversin e inferencia de tipos.

6.5. Comprobacin Esttica y Dinmica de Tipos

Las comprobaciones de tipos son estticas si stas son llevadas a cabo antes de que el programa se ejecute, es decir, en tiempo de compilacin. Para poder implementar un comprobador de tipos esttico, es necesario que toda construccin del lenguaje tenga asociada un tipo mediante el sistema de tipos.

El siguiente programa en Pascal:

Posee un error de tipo puesto que no es posible asignar un nmero real a un nmero entero.La parte derecha de la asignacin posee un tipo real. El sistema de tipos del lenguajePascal identifica en una de sus reglas que el producto de un entero y un real devuelve un tipo real. No es necesario ejecutar la aplicacin para que el comprobador de tipos (esttico) d un mensaje de error en la sentencia de asignacin.Aquellas comprobaciones de tipos que sean llevadas a cabo en tiempo de ejecucin se definen como dinmicas. Cualquier verificacin relativa a los tipos puede llevarse a cabo dinmicamente, ya que es en tiempo de ejecucin cuando se puede conocer el valor exacto que toma una expresin. Sin embargo, aunque estas comprobaciones son ms efectivas, poseen dos inconvenientes: Las comprobaciones estticas detectan los errores antes de que se ejecute la aplicacin y, por ello, el programador podr reparar stos de un modo casi inmediato y no cuando se est ejecutando la aplicacin. Las comprobaciones dinmicas ralentizan la ejecucin de la aplicacin.

Vemos como el intrprete evaluado posee un sistema y comprobador de tipos dinmico, ya que el tipo inferido y las comprobaciones de tipo varan en funcin del valor dinmico de cada una de las expresiones.

6.6. Equivalencia de Expresiones de Tipo

6.7. Conversin y Coercin de TiposConsidrese la expresin x+i donde x es una variable de tipo real e i es de tipo entero.Como un ordenador representa los reales y los enteros de forma distinta, la operacin de suma es distinta en funcin de si sta es de nmeros reales o enteros. En el ejemplo expuesto, deber convertirse el valor de i a su correspondiente valor real, previamente a llevar a cabo la operacin suma.La conversin de tipos entre valores puede ser llevada a cabo implcitamente si el compilador la realiza de un modo automtico. Este tipo de conversin implcita recibe el nombre de coercin. La mayora de los lenguajes ofrecen coercin de tipos en aquellos contextos donde la conversin no supone prdida alguna de informacin.

La coercin de tipos suele requerir que el generador de cdigo produzca rutinas de conversin (e incluso de validacin semntica) que sern ejecutadas por el programa en tiempo de ejecucin. Esto har que la ejecucin del programa se vea ralentizada por la con versin dinmica de tipos.

6.8. Sobrecarga Un smbolo est sobrecargado cuando tiene distintos significados dependiendo de su contexto. Esta definicin suele aplicarse a operadores y funciones. Un ejemplo comn es el operador +, ya que puede representar suma de enteros, de reales o incluso de cadena de caracteres. Aunque para un humano la suma de enteros y reales puede tener el mismo significado, para una mquina no es as, ya que ejecuta operaciones distintas en cada caso. En los lenguajes Ada y Basic, el operador parntesis est sobrecargado; A(i) puede significar tanto el acceso al elemento i-simo de un array, como la invocacin a la funcin A con el parmetro i.Ejemplo. La siguiente gramtica libre de contexto representa un subconjunto de expresiones en la que el operador suma representa la adicin de nmeros enteros y reales: