Capitulo 4 - Apuntes 4 PDF

Preview

Summary

Escuela Técnica Superior de Ingeniería de Sistemas Informáticos
Asignatura: Traductores de Lenguajes de Programación...

Description

Tema 4 GRAMÁTICAS DE ATRIBUTOS. SEMÁNTICA 4.1 4.2

4.3

Gramáticas de atributos. La semántica de los lenguajes de programación. 4.2.1 Semántica estática. 4.2.2 Semántica dinámica. Especificación de la semántica.

El presente tema pretende introducir en primer lugar la utilización de atributos en las gramáticas de contexto libre, confiriéndoles de esta manera mayores posibilidades. En este sentido, va a ser posible obtener información adicional de la palabra generada, como puede ser su longitud o el número de símbolos que tiene. Incluso, es posible la definición de lenguajes que no son de Tipo Dos mediante gramáticas de contexto libre con atributos. Otro objetivo destacable de este tema consiste en introducir las características semánticas de un lenguaje de programación. Con ello, se tienen ya tres niveles de definición en un lenguaje de programación: léxico, sintáctico y semántico. Dichas características semánticas pueden clasificarse en dos: estáticas y dinámicas, como ya se ha comentado en los preliminares del libro. Así mismo, se pretende utilizar las gramáticas de atributos estudiadas al comienzo del tema para definir ciertas características semánticas de una manera formal.

4.1 GRAMÁTICAS DE ATRIBUTOS. Se trata de gramáticas de contexto libre a las que se añaden unas propiedades o atributos en los símbolos terminales y no terminales. Estos atributos se irán propagando por el árbol de derivación según se indique en las funciones de evaluación que llevan asociadas las reglas de producción de la gramática. De manera que cuando se aplica una regla de producción, no sólo se aplica dicha regla sino que también deben realizarse las funciones de evaluación de atributos que lleva asociada. La utilidad de una gramática de atributos consiste en la posibilidad de calcular el valor de determinados atributos en unos puntos concretos del árbol.  Ejemplo 4.1 Atributos en una gramática. Sea la gramática: S ──> aS | a que genera el lenguaje L = { an | n > 0 }. Se pretende calcular el número de símbolos a que

198

GRAMÁTICAS DE ATRIBUTOS. SEMÁNTICA

tiene la palabra generada. Lógicamente, el atributo a considerar será precisamente el número de símbolos a que se ha generado en cada momento. Representándose dicho atributo mediante num. La producción S ──> a indica que se ha generado una única a, por tanto, la regla de evaluación asociada será: Atributo num de S aS indica que se genere una a y después se dé opción a generar más símbolos a con el no terminal S de la derecha, por tanto la regla de evaluación asociada será: Atributo num de S izquierda aS. Pero, como no se conoce el atributo num del no terminal S de la derecha, no es posible aplicar la regla de evaluación. 2 Se vuelve a aplicar la regla de producción S ──> aS. Pero, por la misma razón de antes, no es posible realizar la regla de evaluación. 3 Se aplica la producción S ──> a. En este caso como la regla de evaluación no depende de ningún atributo (Atributo num de S aS es posible realizar la evaluación de atributos, ya que se conoce el valor del atributo num para el símbolo S de la derecha. Por tanto, se obtiene que el valor de num del no terminal S de la izquierda es 2. 5 Finalmente, es posible aplicar la regla de evaluación para la primera regla S ──> aS, obteniéndose en la raíz del árbol un valor de num = 3. Definición formal de gramáticas de atributos.

199

GRAMÁTICAS DE ATRIBUTOS. SEMÁNTICA

Una gramática de atributos consta de tres componentes. G.A. = { G, A, FE } donde cada componente tiene el siguiente significado:  G = Gramática de contexto libre  A = Atributos asociados a terminales y no terminales. La notación utilizada para denominar el atributo a del símbolo X es: X.a  FE = Funciones de evaluación: establecen la forma en que se calcula un atributo en función de otros atributos de la misma regla de producción. Así por ejemplo, para la regla de producción: A ──> X1 X2 X3 , donde A  N y Xi    N son válidas, por ejemplo, las siguientes funciones de evaluación: A.a = f (X1.a, X3.b) Xi.a = f (A.b, X1.b, X3.c) pero no sería válida la siguiente: A . a = f ( Y 1. a ) No sería tampoco válida una regla de evaluación en la que un atributo dependiera de sí mismo, ya que no podría aplicarse nunca. Como notación, las funciones de evaluación se expresarán utilizando el lenguaje de programación Pascal. Además, las funciones de evaluación asociadas a una producción irán delimitadas entre los símbolos ‘{‘ y ‘}’. Es posible que en una regla de producción existan dos símbolos con el mismo nombre, por ejemplo, en la regla S ──> aS existen dos símbolos con el nombre S. Para distinguir un símbolo de otro en la regla de evaluación se les asocia un número diferente a cada uno. Así, el no terminal S de la izquierda sería S1, mientras que el de la derecha sería S2.  Ejemplo 4.2 Gramática de atributos. La gramática de atributos utilizada en el Ejemplo 4.1 se especifica de la siguiente manera: S ──> a { S.num:= 1 } S ──> aS { S1.num:= 1 + S2.num }



Árbol decorado. Se trata de la representación del árbol de derivación junto con los valores de los atributos

200

GRAMÁTICAS DE ATRIBUTOS. SEMÁNTICA

evaluados. Así, el árbol mostrado en el Ejemplo 4.1 es un árbol decorado. Clasificación de los atributos. Existen dos tipos de atributos según se propaguen en el árbol de derivación hacia arriba o hacia abajo. Los primeros se llaman atributos sintetizados, mientras que los segundos reciben el nombre de heredados. Atributos sintetizados. En el ejemplo utilizado hasta ahora de gramática de atributos, el atributo num se propagaba desde las hojas del árbol (en donde tomaba el valor 1) hasta la raíz del mismo (en donde alcanzaba el valor 3 para la palabra aaa). Es decir, se propaga hacia arriba, por lo que se dice que dicho atributo es sintetizado. Una regla de producción X ──>  tiene un atributo sintetizado en el no terminal parte izquierda ( X ), si el valor de éste se obtiene de la siguiente manera: X.atributo = f (.atributos ) X

 Atributos heredados. Se propagan hacia abajo o dentro del mismo nivel del árbol. En concreto, en una producción X ──> Y se dice que el símbolo Y    N, tiene un atributo heredado si éste se calcula de la siguiente manera: Y.atributo = f ( X.atributos, .atributos, .atributos )

X



Y



 Ejemplo 4.3 Atributos heredados. Se resolverá el mismo problema que en los ejemplos precedentes. Es decir, contabilizar el número de símbolos a que tiene una palabra perteneciente al lenguaje L = {an | n>0 }. La diferencia estriba en que el cálculo se va a realizar desde la raíz del árbol hasta las hojas, debido a la naturaleza de los atributos heredados. En definitiva, el número total de símbolos a se va a obtener en las hojas del árbol. Según este pleanteamiento, en la raíz del árbol es en donde debe empezar la cuenta

201

GRAMÁTICAS DE ATRIBUTOS. SEMÁNTICA

incremental de símbolos a. Sin embargo, con la gramática que se tiene, no es posible saber cuál es la producción que ocupa la raíz; ya que la producción S ──> aS puede ocupar dicha raíz, o puede estar más abajo en el árbol. Por ello, se debe modificar la gramática para tener localizada la producción que ocupa siempre la raíz del árbol: S ──> A A ──> aA | a La función de evaluación asociada a la producción S ──> A será la de indicar que el no terminal A tiene cero símbolos a. Mientras que las otras dos reglas de producción irán incrementando los correspondientes valores de los atributos en una unidad. Realizando propagación hacia abajo hasta que se aplique la producción A ──> a, en donde se tendrá el total de símbolos a. El árbol decorado para la palabra aaa es el siguiente:

S A

num = 0

a

A

num = 1

a

A

num = 2

a

num = 3

Siendo la gramática de atributos: S ──> A { A.num:= 0 } A ──> aA { A2.num:= A1.num + 1 } A ──> a { a.num:= A.num + 1 }



Atributos intrínsecos. Existe un tercer tipo de atributos cuya particularidad es que no se propagan por el árbol. Se trata de atributos propios de los símbolos terminales, cuyo valor se conoce inicialmente. Es decir, no

202

GRAMÁTICAS DE ATRIBUTOS. SEMÁNTICA

se trata de un atributo que haya que calcular, sino que son valores de partida. Así, en los ejemplos precedentes, se sabe de partida que un símbolo a tiene una a. Se podría haber utilizado dicho atributo intrínseco, como muestra el siguiente ejemplo, aunque por simplicidad no se ha hecho.  Ejemplo 4.4 Atributos intrínsecos. El ejemplo 4.2 se podría haber planteado de la siguiente manera, utilizando un atributo intrínseco para el terminal a. Dicho atributo se llama valor y se sabe de partida que toma el valor 1. S ──> a { S.num:= a.valor } S ──> aS { S1.num:= a.valor + S2.num }



En los ejemplos precedentes, a cada regla de producción se le han asociado reglas de evaluación de atributos. Se pueden considerar además ciertas reglas de comprobación de valores de atributos. Así, es posible detectar determinadas incorrecciones en la construcción de la palabra generada, lo que da lugar a una capacidad mayor de especificación que la que tienen las gramáticas de contexto libre.  Ejemplo 4.5. Definición de un lenguaje de Tipo Uno con una gramática de atributos. Sea el lenguaje L = {an bn cn | n >= 0 } No es un lenguaje de Tipo Dos, ya que no puede ser reconocido con un esquema de pila (no existe un autómata a pila). Sin embargo, se puede definir con una gramática de atributos, cuya base es una gramática de Tipo Dos. El planteamiento es el siguiente: L no puede ser generado por una gramática de Tipo Dos, pero sí que es posible obtener una gramática de contexto libre que genere el lenguaje L ' = {an bn cm | n,m >= 0 }, comprobándose que n = m a través de un sistema de atributos. Dicho sistema de atributos deberá contabilizar ambos valores ( n y m ) de una manera muy similar al Ejemplo 4.2. La gramática que genera L' = {an bn cm | n,m >= 0 } es la siguiente: S ──> AB A ──> aAb |  B ──> cB |  El valor de n se contabilizará con el atributo num_n, mientras que m se contabilizará con el atributo num_m. S ──> AB {

GRAMÁTICAS DE ATRIBUTOS. SEMÁNTICA

203

IF A.num_n B.num_m THEN rechazar_palabra () } A ──> aAb { A1.num_n:= 1 + A2.num_n } A ──>  { A.num_n:= 0 } B ──> cB { B1.num_m:= 1 + B2.num_m } B ──>  { B.num_m:= 0 } Podría haberse realizado la misma comprobación utilizando un único atributo num, ya que no hay ningún símbolo que simultáneamente requiera los dos atributos. 

4.2 LA SEMÁNTICA DE LOS LENGUAJES DE PROGRAMACIÓN. La palabra semántica referida a un lenguaje de programación en un sentido general (sin llegar a precisar, como más adelante se hará, las características semánticas concretas) se refiere al significado de un texto escrito en ese lenguaje, esto es, al significado de la notación que constituye el lenguaje de programación. En este sentido general, se puede decir que el nivel semántico de un lenguaje es mayor o menor, para indicar que el significado de las construcciones en ese lenguaje es más o menos complejo. Así, de manera intuitiva, parece evidente que la complejidad del significado de la sentencia case del lenguaje Pascal es mucho mayor que la del significado de una instrucción de asignación entre registros en un lenguaje ensamblador. Un programa escrito en un lenguaje de programación no basta con que sea correcto desde el punto de vista léxico y sintáctico. Es decir, no es suficiente que las palabras se encuentren correctamente codificadas (léxico), y además, que se encuentren correctamente ordenadas (sintaxis). En primer lugar, son necesarias comprobaciones adicionales para determinar que ese programa es correcto, es decir, que tiene un significado. Estas comprobaciones dependen del lenguaje de programación concreto y son todas aquellas que no quedan reflejadas en el léxico y la sintaxis. Por ejemplo, las comprobaciones de tipo, uso de identificadores previamente declarados, etc. A estas comprobaciones que es necesario verificar para concluir que un fuente es correcto se les denomina semántica estática. Por otra parte, un lenguaje de programación no queda definido completamente si el objetivo es únicamente determinar que un fuente es correcto (desde el punto de vista léxico, sintáctico y semántico). Es necesario también saber el significado de todas las estructuras del lenguaje

204

GRAMÁTICAS DE ATRIBUTOS. SEMÁNTICA

(declaraciones, sentencias, etc. ) para poder ejecutar dicho fuente. A este significado en tiempo de ejecución se refiere la semántica dinámica. Cabe resaltar que, en un lenguaje de programación, las características semánticas se diferencian claramente de las características lexicográficas (especificables mediante expresiones regulares) y de las sintácticas (especificables mediante gramáticas incontextuales). Las especificaciones semánticas son más complejas y no se ajustan formalmente ni con los lenguajes de Tipo Tres, ni con los de Tipo Dos.

4.2.1 Semántica estática. Para delimitar el campo de la semántica estática es necesario tener en cuenta las siguientes dos consideraciones:  Para diferenciar semántica estática de sintaxis, simplemente hay que tener en cuenta que semántica es toda aquella comprobación que no viene reflejada en la gramática sintáctica. En ocasiones, hay comprobaciones que podrían solucionarse en la sintaxis, con lo que serían comprobaciones sintácticas. Sin embargo, pueden dar lugar a gramáticas muy complicadas, por lo que se prefiere no especificarlas a través de la gramática, dejando dicha comprobación al campo de la semántica.  Para diferenciar semántica estática de dinámica, hay que tener en cuenta que, mientras la semántica estática se refiere a comprobaciones que hay que realizar sobre el fuente en tiempo de análisis (para determinar si dicho fuente es correcto o no), la semántica dinámica se refiere al tiempo de ejecución. Así por ejemplo, el comprobar que un identificador de variable no tome un valor superior a una determinada cantidad no se podrá realizar en tiempo de análisis, ya que dicho valor no se conoce hasta tiempo de ejecución, por tanto se tratará de semántica dinámica. Igualmente, tampoco se podrá comprobar en un fuente que no haya una división por cero, ya que en el denominador puede haber alguna variable. De ahí que el error “división por cero” se obtenga en tiempo de ejecución. En definitiva, después de realizar el análisis semántico del fuente, se ha conseguido determinar si dicho fuente es totalmente correcto o si presenta algún error, ya sea léxico, sintáctico o semántico. Programa

Analizador

Fuente caracteres

Léxico

Errores Léxicos

Analizador tokens

Sintáctico

Analizador

Fuente

Semántico

Correcto

estructuras sintácticamente correctas

Errores Sintácticos

Errores Semánticos

Comprobaciones de tipo. En muchos lenguajes de programación la mayoría de comprobaciones referentes a la semántica estática son comprobaciones de tipo. A estos lenguajes en los que el uso de tipos es muy estricto

GRAMÁTICAS DE ATRIBUTOS. SEMÁNTICA

205

y se debe comprobar con mucha frecuencia se les denomina fuertemente tipados. Así por ejemplo, Pascal es un lenguaje fuertemente tipado, por contra, el lenguaje de programación C da mucha mayor flexibilidad en los tipos, no siendo un lenguaje fuertemente tipado. Por ejemplo, la sintaxis de una sentencia de asignación en un lenguaje del estilo de Pascal, en el que se han considerado exclusivamente los tipos simples, puede ser la siguiente: I:I:= Identificador:= Evidentemente, no todas las sentencias de asignación que cumplen esta sintaxis son correctas, habrá que comprobar que el tipo de es compatible con el tipo del Identificador. Por ejemplo, no se puede pretender asignar un valor real a una variable de tipo lógico. Además, haciendo referencia a la sintaxis planteada en el capítulo anterior para las expresiones del lenguaje de programación Pascal, también es necesario realizar ciertas comprobaciones adicionales sobre dichas expresiones. Así, la expresión TRUE + 7 es generada por dicha gramática, que no tiene en cuenta los tipos de los operandos.  Ejemplo 4.6. Comprobaciones de tipo. La sentenciaIáreaI:= (base * altura) / 2 está bien codificada lexicográfica y sintácticamente según el lenguaje Pascal. Sin embargo, para que la sentencia sea válida han de cumplirse otras condiciones, que se refieren a la semántica estática del lenguaje Pascal:  base y altura han de ser dos identificadores de un tipo al que pueda aplicarse el operador aritmético ‘*’.  El tipo resultante de la multiplicación y la constante entera (2) han de ser compatibles para la operación de división.  El tipo resultante para la expresión (calculado en función del tipo de cada uno de sus componentes, tanto operandos como operadores) ha de ser compatible con el tipo de la variable área.  Intentar hacer una sintaxis que especifique expresiones completamente correctas es una tarea imposible, ya que habría que tener en cuenta la presencia identificadores de variables o de constantes, cuyos tipos dependen de la manera en que se hayan declarado. Así, es imposible construir una sintaxis que determine si la expresión x + y tiene significado correcto o no. Otro caso más de comprobación de tipos se tiene en la sentencia alternativa IF de Pascal, cuya sintaxis puede ser la siguiente: ::=IF THEN ELSE | IF THEN Para determinar la corrección habrá que comprobar que la expresión sea de tipo lógico. Nótese nuevamente que es imposible construir una sintaxis que genere exclusivamente expresiones lógicas, ya que no hay forma de determinar si la expresión x es lógica o no. Igualmente, el resto de sentencias de Pascal requieren de comprobaciones de tipo adicionales. Existencia y visibilidad de los objetos.

206

GRAMÁTICAS DE ATRIBUTOS. SEMÁNTICA

Hasta este punto, se han utilizado identificadores en expresiones o en sentencias sin reparar en que dicho identificador tuviera que haber sido declarado o no. Muchos de los lenguajes de programación, como Pascal, exigen que antes de utilizar por ejemplo una variable debe haberse declarado en alguna parte declarativa del programa. Así por ejemplo, la sentencia de asignación xI:= 2 de Pascal será incorrecta en cualquiera de los siguientes casos:  x no ha sido declarada.  x ha sido declarada como constante, como tipo, o como subprograma.  x ha sido declarada como variable de tipo lógico o carácter. Pero además de tener en cuenta si un determinado identificador ha sido previamente declarado, no hay que olvidar que tiene que ser visible en el punto en donde se encuentra. Es decir, hay que tener presente las reglas de ámbito del lenguaje de programación.  Ejemplo 4.7. Reglas de ámbito de Pascal. Dada la siguiente estructura de un programa en Pascal: PROGRAM ejemplo_4_7; VAR x, y: integer; PROCEDURE P1; a, b: real; BEGIN .............. END; PROCEDURE P2; x, z: boolean; BEGIN ............ END; BEGIN (* PROGRAMA PRINCIPAL *) ............ END. Al considerar las reglas de ámbito, se obtienen los siguientes resultados:  Desde P1 son visibles: x, y, a, b.  Desde P2 son visibles: x (declarada en P2), z, y.  En el programa principal son visibles: x, y. Por ejemplo, serían incorrectas las siguientes sentenciasI  xI:= 2 en P2.  aI:= 3.5 en P2.

GRAMÁTICAS DE ATRIBUTOS. SEMÁNTICA

 zI:= TRUE en P1.

207



En el apartado 6.1 del tema 6 se realiza un estudio detallado de las reglas de ámbito más habituales en los lenguajes de programación algorítmicos de alto nivel. Otras comprobaciones de la semántica estática. A continuación se enuncian a modo de ejemplo algunas comprobaciones que deben realizarse en relación con la semántica estática de Pascal. Hay que hacer notar...