Transcript
TEMA 7 - GRAMÁTICAS DE ATRIBUTOS Y SEMÁNTICA 7.1 Gramáticas de atributos Una gramática de atributos es una gramática independiente del contexto en la cual a sus símbolos terminales y no terminales se les dota de unos atributos y a sus producciones de unas funciones de evaluación que hacen que dichos atributos se propaguen a través de la gramática. Su fin es conocer un determinado valor de un atributo en cualquier parte del árbol de derivación y tomar la decisión oportuna. Un atributo es una propiedad asociada a una estructura sintáctica. Si una estructura sintáctica representada por el símbolo gramatical X tiene asociado un atributo a lo representaremos por X.a (Nombre símbolo.Nombre atributo) Las funciones semánticas relacionan los valores de los atributos definidos sobre la gramática atribuida y van asociadas a producciones de la gramática atribuida. Ejemplo: Sea el lenguaje L={an |n>=0} generado por la siguiente gramática: G={ ∑={a, $}, N={S, A}, S, P) P: S→A$ A→aA A→a Se quiere atribuir para que contabilice y escriba el número de aes que tiene una palabra generada S.num
S→A$ {writeln (A.num)} A→aA {A1.num=1+A2.num} A→a
A.num
{A.num=1}
$ A.num
a
a
1
Definición formal Una gramática de atributos está formada por una tripleta GA={GIC, A, F} G – gramática independiente del contexto A – atributos asociados a los símbolos terminales y no terminales F – función de evaluación, función asociada a producción que determina como obtener unos atributos en función de otros dentro de la misma producción A→X1 X2 X3 …Xn ; A∈N y Xi∈(Σ|N) A.a=f (X1.a,X2.b,…Xm.z) a es un atributo asociado al símbolo no terminal A y obtiene su valor en función de los atributos: a asociado a X1, b asociado a X2 ,…y z asociado a Xm ( es un atributo obtenido en función de la parte derecha de la producción) X1.a=f (A.a,X2.b) a es un atributo asociado al símbolo X1 y obtiene su valor en función de los atributos: a asociado a A , b asociado a X2 ( es un atributo obtenido en función de elementos de la parte derecha e izquierda de la producción) A.a=f (y1.b, B.a) , X1.a=f (y1.b, B.a) atributos incorrectos no se obtienen dentro de la producción Tipos de atributos: Sintetizados- son atributos que se propagan desde las hojas a la raiz A→X1 X2 X3 …Xn ; A∈N y Xi∈(Σ|N) A.a=f(X1.a,X2.b,…Xm.z) a es un atributo sintetizado obtienen sus valores de los atributos de un nivel inferior en la generación del árbol, es decir de la parte derecha de la producción S→A$ {writeln (A.num)} A→aA {A1.num=1+A2.num} A→a {A.num=1}
A.a
X1..a
X2b
…Xna
1
Heredados - son atributos que se propagan desde la raiz a las hojas o dentro de un mismo nivel A→X1 X2 X3 …Xn ; A∈N y Xi∈(Σ|N) X1.a=f(A.a,X2.b,…) a es un atributo heredado obtenido en función de los atributos a y b obtiene sus valores de los atributos del mismo nivel o superior en la generación del árbol, es decir se calculan descendentemente S→A$ {A.num=0} A→aA {A2.num=1+A1.num} A→a {writeln (A.num+1}
A.a
X1..a
X2b
…Xn.za
Intrínsecos Son atributos relativos a símbolos terminales, por lo tanto valores correspondes a las hojas (valores finales). Son valores fijos obtenidos de antemano cuyo valor se obtiene de partida. En el ejemplo anterior de contabilizar aes, el valor intrínseco de cada a es 1. S→A$ {writeln (A.num)} A→aA {A1.num=1+A2.num} A→a {A.num=1}
A.a X1..a
X 2b
…Xn za
Poder de significación de las gramáticas de atributos La gramáticas de atributos tienen un mayor poder de significación que una gramática independiente del contexto. Puede reconocer lenguajes de tipo superior, es decir de tipo 1 o tipo 0 . Sea el lenguaje L={ an bn cn| n>=0} es un lenguaje de tipo 1, solo puede ser generado por una gramática de tipo 1 o 0 . Se puede construir una gramática de atributos GA=( GIC, A, F) que genere dicho lenguaje: Sea la gramática: S→AB A→aAb |ε B→cB |ε que genera el lenguaje L={anbncm| n>=0,m>=0} Podemos atribuirla para que genere el lenguaje L={anbncn| n>=0} Atributos, necesarios para contabilizar las aes, bes y ces: num_ab atributo sintetizado asociado a A y num_c atributo sintetizado asociado a B Funciones asociadas a las producciones necesarias para la propagación de los atributos: S→AB {IF A.num_ab<>B.num_c Then error semántico} A→aAb {A1.num_ab=A2.num_ab+1} |ε {A1.num_ab=0} B→cB {B1..num_c=B2.num_c+1} |ε {B..num_c=0} Ejemplos de gramáticas de atributos 1.
Número de veces que se da la subcadena ab en una palabra, sobre una gramática que genera aes y bes, como la siguiente: S→aS | bS |ε - Atributos necesarios: uno sintetizado que contabilice el número de ab que se dan en la palabra y el otro también sintetizado para saber si anteriormente se ha dado una b. - Funciones asociadas a producciones necesarias para la propagación de los atributos S→ε {S.es_b=false, S.num_ab=0} S→bS {S,es_b=true, S1.num_ab=S2.num_ab} S→aS {IF S2.es_b=true THEN S1.num_ab=S2.num_ab +1, S1.es_b=false ELSE S1.num_ab=S2.num_ab; S1.es_b=S2.es_b }
2. La mayor subcadena formadas de aes en una palabra, sobre una gramática que genera aes y bes como la siguiente: S→aS | bS |ε Atributos necesarios: uno sintetizado que contabilice el número de aes que se dan en la palabra y el otro también sintetizado para almacenar el número mayor de aes consecutivas.
2
Funciones asociadas a producciones necesarias para la propagación de los atributos S→ε {S.num_aes=0, S.mayor=0} S→aS {S1,num_aes=S2.num_aes+1, S1.mayor=S2.mayor} S→bS {IFS2.num_aes>S2.mayor THEN S1.mayor:=S2.nun_aes;S1.num_aes:=0 ELSE S1.mayor:=S2.mayor S1.num_aes=0} 3. Crear una gramática de atributos que calcule el valor en decimal de un número binario, a partir de la siguiente gramática: S’ →S, S→0S |1S |0 | 1 S`→S {writeln (S.valor)} S→0 S {S1.pos:=s2.pos+1;S1.valor:=s2.valor} S→1 S {S1.pos:=s2.pos+1;S1.valor:=s2.valor+2 s1.pos} S→0 {S.valor:=0; S.pos:=0 } S→1 { S.pos:=0; S.valor:=2 s.pos} Ejemplo anterior con pos como atributo heredado S`→S {S.pos:=0; writeln (S.valor)} S→S 0 {S2.pos:=S1.pos+1;S1.valor:=S2.valor} S→S 1 {S2.pos:=S1.pos+1;S1.valor:=S2.valor+2 s1.pos} S→0 {S.valor:=0} S→1 {S.valor:=2 s.pos} 4. Crear una gramática de atributos que calcule el valor en decimal de un número binario, a partir de la siguiente gramática: S→A.B ; A→DA |D ; B→BD |D ; D→0 | 1 Atributos necesarios: uno sintetizado que contiene la suma de los valores y otro también sintetizado para llevar la posición Funciones asociadas a producciones necesarias para la propagación de los atributos A→D {A.pos:=0, A.valor:=D.2A.pos } A→DA {A1.pos:=A2.pos+1; A1.valor:=A2.valor+ D.2A1.pos } B→D {B.pos:=-1, B.valor:=D.2B.pos } B→BD {B1.pos:=B2.pos+1; B1.valor:=B2.valor+ D.2B1.pos } S→AB {S.valor:=A.valor+B.valor} 5. Sea L el lenguaje formado por palabras del alfabeto ∑={a,b} en las que existen n grupos de repetición, donde n>=2, tal que: Cada uno de los n-1 primeros grupos de repetición (todos menos el último) tiene longitud par. El último grupo de repetición tiene longitud n, indicando el número de grupos de repetición que tiene una palabra. A partir de la gramática S → AX | BY X → BY |B Y →AX |A A→ aA |a B→ bB |b , obtener una GA que defina L. Usaremos tres atributos de tipo sintetizado:long, asociado a los no terminales A y B, expresa la longitud del grupo long_ult, asociado a X e Y, expresa la longitud del último grupo que generan dichos no terminales. grupos, asociado a X e Y, expresa el número de grupos generados por dichos no terminales. Funciones asociadas a producciones necesarias para la propagación de los atributos: S→AX { IF A.long mod 2 <> 0 OR X.long_ult <> X.grupos + 1 THEN rechazar_palabra() } S→BY { IF B.long mod 2 <> 0 OR Y.long_ult <> Y.grupos + 1 THEN rechazar_palabra() } X→BY { IF B.long mod 2 <> 0 THEN rechazar_palabra(); X.long_ult := Y.long_ult; X.grupos := Y.grupos + 1 } X→B { X.long_ult := B.long; X.grupos := 1 } Y→AX { IF A.long mod 2 <> 0 THEN rechazar_palabra(); Y.long_ult := X.long_ult; Y.grupos := X.grupos + 1; } Y→A { Y.long_ult := A.long; Y.grupos := 1; } A→aA { A1.long := 1 + A2.long; } A->a { A.long := 1; } B→bB { B1.long := 1 + B2.long; } B->b { B.long := 1; } 3
6. Dado el alfabeto Σ= {a, b, 0, 1} sea la siguiente gramática:
::= ::= | ::= a | b ::= 0 | 1 que define las palabras con la siguiente estructura: • En primer lugar una subpalabra compuesta por letras a y b • A continuación, en el centro de la palabra, un dígito que puede ser 0 o 1. • Finalmente, una segunda subpalabra compuesta por letras a y b, y que tiene la misma cantidad de símbolos que la primera subpalabra. Se desea cambiar el lenguaje para que las palabras cumplan además las siguientes restricciones: • Si el dígito central es 0, la primera subpalabra deberá empezar por a. Por ejemplo, serían válidas las palabras aba0bba, a0a y a0b. Pero no serían válidas b0a ni ba0aa. • Pero si el dígito central es 1, entonces es la segunda subpalabra quien deberá empezar por a. Por ejemplo, serían válidas las palabras a1a, b1a y abb1abb. Pero no serían válidas a1b ni ba1ba. Se pide: A partir de la gramática anterior y sin modificarla, obtener una gramática de atributos que compruebe dichas restricciones, dando un mensaje indicativo en la raíz del árbol (representada por la producción ::= ). Dicho mensaje será simplemente 'palabra válida' o 'palabra no válida'. Previamente se indicarán los atributos a utilizar, justificando su uso, los valores que podrán tomar y si se propagan de forma heredada o sintetizada. Los atributos utilizados son: • valor, que sirve tanto para el no terminal como para . En el primer caso podrá valer 0 ó 1, mientras que en el segundo valdrá a o b. En ambos casos es de tipo sintetizado. •
digito (dígito central) es un atributo sintetizado de que mantiene el valor (0 ó 1) del dígito central generado.
•
comienzo_1a (comienzo primera subcadena) y comienzo_2a (comienzo segunda subcadena) son dos atributos sintetizados de que expresan las letras por las que empiezan la primera y la segunda subcadenas, respectivamente.
La gramática de atributos resultante será, pues: ::= 0 { .valor := 0 } ::= 1 { .valor := 1 } ::= a { .valor := a } ::= b { .valor := b } ::= { .digito := .valor; .comienzo_1a := .valor; .comienzo_2a := .valor; } ::= { .digito := .digito; .comienzo_1a := .valor; .comienzo_2a := .comienzo_2a } ::= { IF (.digito = 0) AND (.comienzo_1a = a) OR (.digito = 1) AND (.comienzo_2a = a) THEN writeln (‘palabra válida’) ELSE writeln (‘palabra no válida’) }
4
7.2 Gramática de atributos en el análisis semántico de un lenguaje de programación Podemos ampliar la definición de gramática de atributos enfocándola en la especificación del análisis semántico, es decir verificar la validez semántica. Así la tripleta anterior se pasa a la cuádrupla GA= (G, A, F, C) En donde C es el conjunto de condiciones que deben cumplir los atributos asociados a las funciones semánticas de una producción Crear una gramática de atributos que especifique la comprobación de tipos de las expresiones de un lenguaje L, cuya sintaxis es la siguiente: ::= | ::= op1, op2 | entero ::= real ::=identificador | cte_ent | ( ) ::= * | / ::= + | ::= + | - | ε
entero entero real
real real real
La semántica asociada a estas reglas de producción debe cumplir con las siguientes condiciones: Las operaciones solo se podrán realizar con tipos numéricos (entero o real). El resultado será siempre real a no ser que ambos sean enteros en cuyo caso el resultado será entero ::= {IF (.tipo<> entero ) AND (.tipo <>real OR (.tipo<>real) AND(.tipo<>entero THEN error semántico ELSE IF ((.tipo= entero AND (.tipo=entero)) THEN ((.tipo= entero ELSE((.tipo= real } expresión>::= { .tipo::=.tipo} ::= {IF (.tipo<> entero ) AND (.tipo <>real OR (.tipo<>real) AND(.tipo<>entero THEN error semántico ELSE IF ((.tipo= entero AND (.tipo=entero)) THEN ((.tipo= entero ELSE((.tipo= real } ::= { .tipo::=.tipo} ::= ident {.tipo ::0 ident.tipo } ::= const_ent {.tipo ::= entero } ::= const_real {.tipo ::= real } ::= ( {.tipo ::= .tipo }
5
7.3 Semántica de un lenguaje de programación Es la encargada del significado de los programas fuente en ese lenguaje. Se divide en dos partes: semántica estática y dinámica. Semántica estática Un texto fuente es correcto, si es correcto su léxico, sintaxis y su semántica estática. La semántica estática se encargada de las condiciones que deben cumplir los objetos que forman las estructuras que intervienen en un texto fuente. Se llama objeto a cualquier entidad que puede intervenir en un texto (programa fuente): variables, constantes, tipos y subprogramas. Los objetos que intervienen en las estructuras que componen un texto fuente, tienen que cumplir unas ciertas propiedades y características que llamamos atributos o características asociadas a esos objetos: nombre, tipo, visibilidad, definición. Los atributos de los diferentes objetos que aparecen en el texto fuente se van almacenando durante el análisis en una estructura de datos denominada tabla de datos (tabla de símbolos), y así, poderlos utilizar durante la etapa de ejecución. La acción mediante en la cual a un objeto se le asocia un determinado atributo o característica se llama ligadura, esta ligadura puede ser de dos tipos: estática (ligadura temprana) se hace a nivel de análisis, ligadura en tiempo de compilación y, dinámica (ligadura tardía) se hace a nivel de síntesis, ligadura en tiempo de ejecución. PROGRAM ejercicio; identificador a b c VAR a,b:integer; tipo integer integer real c: real; visible ejercicio ejercicio ejercicio BEGIN definida si si si READ (b,c); a:=b+c; END. El análisis semántico se realiza normalmente de forma simultánea al análisis sintáctico. Siguiente ejemplo: PROGRAM
id
ε
alm_tipo (id)
BEGIN
;
Dec (id) visible
ε
;
Alm_tipo (id) : .tipo real
READ ( )
integer
ε
: .tipo
ε
VAR
ε
Alm_tipo ( id) ,
;
, Dec (id) visible ε
END
.
visible Id.tipo= .tipo .tipo + .tipo .tipo .tipo
.tipo .tipo .tipo Obt_tipo (id)
Obt_tipo (id)
6
Características a cumplir por los objetos Compatibilidad de tipos Existen lenguajes fuertemente tipados como Pascal y otros como C que dan una mayor flexibilidad A continuación se presentan unas tablas de compatibilidad del lenguaje Pascal entre los operandos ligados por operadores : +.-,*,<,>,=,:=,DIV.. +,-,* integer real
integer integer real
real real real
/ integer real
integer real real
real real real
DIV integer real
integer integer integer
real integer integer
<,>,= integer real
integer boolean error
real error Boolean
Compatibilidad entre los objetos ligados por el operador de asignación := variable integer real
:=
expresión Integer (real – incompatible) Integer , real
- La compatibilidad en los lenguajes con estructura de bloques estructura
puede hacerse: por nombre o por
TYPE tamaño=array [1..10] of integer VAR u,v: tamaño; x,y:array [1..10] OF integer u=v compatibilidad por nombre ; u=x compatibilidad por estructura Otras de las características de los objetos es su existencia y visibilidad: En los lenguajes con estructuras de bloques como lo son: Algol, Pascal, C,… es necesario conocer donde puede estar un objeto, que condiciones tiene y donde se puede usar. Para ello es importante conocer las reglas de ámbitos del lenguaje. En los lenguajes con estructuras de bloques, se llama línea de ámbito a una sucesión de bloques anidados Un objeto es visible en su ambiente local y global de la línea de ámbito de dicho bloque, se denomina (1ª regla de ámbito) En otras palabras, en un bloque son visibles los objetos locales declarados en él y los objetos declarados en los bloques de su misma línea de ámbitos que son exteriores a él. PROGRAM P; VAR r, s : integer; PROCEDURE Q ( q1,q2…); VAR t, u: real; ………………….. PR0CEDURE R( r1,r2,…); VAR.. v, x: real; …………….. PROCEDURE S ( s1,s2…); VAR y, z: real;
P – r, s variables,. Q, S subprogramas visible los objetos locales a P Q – t, u var iables , R subprograma q1,q2..parámetros visible los objetos locales a P y Q R – v, x var iables, r1, r2,..parámetros visible los objetos locales a P , Q y R S – y, z variables, s1, s2,..parámetros visible los objetos locales a P y S
Desde el subprograma S no se puede hacer uso de los objetos locales de Q, pero si se puede hacer una llamada a Q.
7
El valor de referencia que toma la existencia de un objeto dentro de un bloque, parte desde el interior hacia el exterior de su línea de ámbito se llama (2ª regla de ámbito) PROGRAM P; VAR x, y : integer; …….integer ……………. PROCEDURE Q ( q1,q2…); VAR x, y: real; …….real. …………….. PROCEDURE R( r1,r2,…); VAR x, y: boolean; ……..boolean ……………. PROCEDURE S ( s1,s2…); VAR x, y: char; ……char …………… En los lenguajes con estructuras de bloques se pueden emplear el mismo nombre para definir objetos distintos declarados en bloques distintos resolviendo la regla entre uso y declaración. Se puede provocar la inaccesibilidad a un objeto haciendo que otro objeto declarado en un bloque mas interno, en su misma línea de ámbito, tenga su mismo nombre Características de los objetos subprogramas (fundamentales en los lenguajes con estructuras de bloques) - conocer número de parámetros - orden de colocación - coincidencia de tipos - coincidencia de parámetros actuales con formales - definición de prototipo - ………….. Semántica dinámica Semántica dinámica se refiere al significado propiamente dicho de las estructuras (sentencias) que conforman el texto fuente en tiempo de ejecución. PROGRAM ejercicio; VAR a,b:integer; c: real; BEGIN READ (b, c); a:=b+c; END. La semántica de las sentencias (estructuras) del ejemplo fuente anterior READ (b,c); a:=b+c; será: Toma el valor del tipo de variable del buffer de entrada y lo pone en la dirección de memoria b y c ; INPUT b INPUT c Coloca en la pila, la dirección de la variable a la que se va a llevar el resultado PUSHA a, lleva a la pila el valor de la dirección de la variable b PUSHA b LOAD, hacer lo mismo para la variable c lleva a la pila el valor de la dirección de la variable c PUSHA c LOAD , una vez colocados los dos valores en la pila se suman y dejando el resultado en la pila ADD y se almacena en la dirección de memoria a STORE. si queremos sacar el resultado, OUTPUT a { INPUT b INPUT c PUSHA a PUSHA b LOAD PUSHA c LOAD ADD STORE OUTPUT a} Con el conocimiento de la semántica dinámica del lenguaje es posible resolver el problema de separación semántica que existe entre el lenguaje de alto nivel y el lenguaje máquina , para su resolución se emplean los procesadores de lenguaje: traductores como compiladores o intérpretes.
8
7.4 Aplicación de las gramáticas de atributos en la especificación semántica de un LP( ejemplos) 1. La sentencia de decisión de un lenguaje L se define con las siguientes reglas sintácticas: ::= DECIDE END-DECIDE ::= | ::= CONDITION ::= VALUE OF id ::= | ::= : ; ::= | ::= | ::= id | cte-entera | cte-real | cte-lógica | ( ) ::= < | > | = | <> ::= + | - | * | / | AND | OR ::= | ε La semántica asociada a dicha sentencia establece las siguientes reglas: • Los identificadores pueden ser de tipo entero, real o lógico, incluido el que aparece en la regla . • Todas las operaciones de tipo relacional pueden realizarse entre operandos de tipo entero y/o real (no tienen por qué ser iguales), siendo el resultado de tipo lógico. • Las operaciones de suma, resta, multiplicación y división pueden realizarse entre operandos de tipo entero y/o real, siendo el resultado de tipo real. Excepcionalmente, en el caso de que ambos operandos sean enteros y el operador no sea la división, el resultado es entero. • Las operaciones AND y OR sólo pueden realizarse entre operandos de tipo lógico, siendo éste el tipo del resultado. • En el caso de la sentencia decide por condición, todas las expresiones que componen sus casos tienen que ser de tipo lógico, mientras que en el caso de la sentencia decide por valor el tipo tiene que ser idéntico al del identificador de cuyo valor se trata. Construir la gramática de atributos necesaria para la especificación semántica de las anteriores restricciones, indicando claramente cuáles son los atributos ligados a cada símbolo de la sintaxis y si son heredados o sintetizados. La sintaxis no puede ser modificada en ningún caso. Se utilizará el atributo tipo para realizar todas las comprobaciones de tipo pedidas en el enunciado. Y además el atributo clase para diferenciar el tipo de operador considerado, ya que para operadores que están en la misma regla sintáctica se aplica diferente semántica. ::= DECIDE END-DECIDE { IF .tipo <> .tipo THEN error_semantico ( ) } ::= {.tipo := logico } ::= {.tipo := .tipo } ::= CONDITION ::= VALUE OF id {.tipo := id.tipo } ::= {.tipo := .tipo } ::= { IF .tipo <> .tipo THEN error_semantico ( ) ELSE .tipo := .tipo } ::= : ; {.tipo := .tipo} ::= {.tipo := .tipo } ::= { IF ((.tipo = entero) OR (.tipo = real)) AND ((.tipo = entero) OR (.tipo = real)) THEN .tipo := logico ELSE error_semantico ( ) } 9
::= {.tipo := .tipo} ::= {CASE .clase OF and,or : IF (.tipo = logico) AND (.tipo = logico) THEN .tipo := logico ELSE error_semantico ( ) suma, resta, producto :IF (.tipo = logico) OR (.tipo = logico) THEN error_semantico ( ) ELSE IF (.tipo = entero) AND (.tipo = entero) THEN .tipo := entero ELSE .tipo := real division :IF (.tipo = logico) OR (.tipo = logico) THEN error_semantico ( ) ELSE .tipo := real } ::= id {.tipo := id.tipo } ::= cte-entera {.tipo := entero } ::= cte-real { .tipo := real } ::= cte-lógica{ .tipo := logico } ::= | ( ) {.tipo :=