Práctica 12: Gramaticas de atributos y TDS (Teoría de Lenguajes)

De Cuba-Wiki
Saltar a: navegación, buscar
Back.png Volver a la página de la materia

Ejercicio 1[editar]

Determinar el conjunto de cadenas generadas por la siguiente gramatica de atributos: G = <VN, VT , P, S>.

Donde: VN = {S,X, Y,Z}, VT = {x, y, z}, size es un atributo sintetizado de X y un atributo heredado de Y y Z, y P es:

S -> X Y Z	{Y.size = X.size ; Z.size = X.size} 
X -> x 	{X.size = 1}
X -> X2 x  {X.size = X2.size + 1} 
Y -> y 	{Condition: Y.size = 1}
Y -> Y2 y  {Y2.size = Y.size - 1} 
Z -> z 	{Condition: Z.size = 1}
Z -> Z2 z  {Z2.size = Z.size - 1}

Respuesta

El conjunto de cadenas generado es . La raiz se divide en XYZ, cada uno representando una cadena de x, y, z consecutivos respectivamente. Luego, al resolver X, se calcula su tamaño sumando 1 por cada no terminal encontrado. Al volver a la produccion S -> XYZ, se carga en el atributo size de Y y de Z el valor de size de X (notar que la gramatica es L-atribuida). En la evaluacion de Y, se resta uno por cada no terminal encontrado y se acepta la cadena de entrada sii al llegar al ultimo no terminal size vale uno; es decir, si la cantidad de y equivale a la de x. Analogo para Z.

Ejercicio 2[editar]

Sin cambiar el lenguaje generado, modificar la gramatica del ejercicio 1 para que size se utilice solo como atributo sintetizado.

Respuesta

Para que size sea sintetizado, debe ser asignado siempre en funcion de los atributos de sus hijos.

S -> X Y Z		{Condition (X.size = Y.size = Z.size)}
X -> x			{X.size = 1}
X1 -> X2 x		{X1.size = X2.size + 1}
Y -> y			{Y.size = 1}
Y1 -> Y2 y		{Y1.size = Y2.size + 1}
Z -> z			{Z.size = 1}
Z1 -> Z2 z		{Z1.size = Z2.size + 1}


Ejercicio 3[editar]

Dar una gramatica de atributos que genere el lenguaje . Construir un arbol decorado para la cadena aabccbcc.

Respuesta

El no terminal A representa la tira inicial de a. El no terminal D representa las tiras de . Y C representa las tiras de c que hay dentro de cada D. El atributo n entero sintetizado en cada no terminal simboliza el valor de n en la definicion del lenguaje.

La primer produccion es si no hay ocurrencias de , basta chequear que n sea mayor o igual a 2. En la segunda sí hay ocurrencias, entonces se chequea que la cantidad de a y la cantidad de c en cada no terminal D sean las mismas.

Las dos siguientes permiten contar la cantidad inicial de a y sintetizar el valor en A. Las dos siguientes, que comienzan con D, repiten las tiras de chequeando que la cantidad de c de cada tira sea siempre la misma y mayor o igual a 2. Las dos ultimas producciones cuentan la cantidad de c de cada tira y sintetizan el valor en C.

G = <VN, VT , P, S>
VN = {S,A,D,B,C}
VT = {a,b,c}
Atributos:
int sintetizado A.n, D.n

S -> A         {Condition: A.n > 1}
S -> A D       {Condition: A.n = D.n && A.n > 1}
A -> A2 a      {A.n := A2.n + 1}
A -> a         {A.n := 1}
D -> D2 b C    {D.n := C.n} {Condition: C.n = D2.n && C.n > 1}
D -> b C       {D.n = C.n}
C -> C2 c      {C.n := C2.n + 1}
C -> c         {C.n := 1}


El arbol decorado se construye a partir del arbol de analisis sintactico agregando los valores de los atributos (ojo: los hijos de cada nodo no estan necesariamente en orden, no se como hacer para que graphviz lo respete).

<graphviz> digraph G { graph [ranksep = 0.5, nodesep=0.5]; node [shape=circle,fontname=Helvetica,fontsize=12]; node [width=0.5,height=0.5,fixedsize=false]; edge [fontname=Helvetica,fontsize=10];

S [label="S"]

A [label="A"] A2 [label="A"]

D [label="D"] D2 [label="D"]

C [label="C"] C2 [label="C"] C3 [label="C"] C4 [label="C"]

a1 [label="a"] a2 [label="a"]

b1 [label="b"] b2 [label="b"]

c1 [label="c"] c2 [label="c"] c3 [label="c"] c4 [label="c"]

S -> A S -> D

A -> A2 A -> a1 A2 -> a2

D -> D2 D -> b1 D -> C

D2 -> b2 D2 -> C2

C -> C3 C -> c1

C3 -> c2

C2 -> C4 C2 -> c3

C4 -> c4 }

</graphviz>

<graphviz> digraph H { graph [ranksep = 0.5, nodesep=0.5]; node [shape=circle,fontname=Helvetica,fontsize=12]; node [width=0.5,height=0.5,fixedsize=false]; edge [fontname=Helvetica,fontsize=10];

S [label="S"]

A [label="A.n=2"] A2 [label="A.n=1"]

D [label="D.n=2"] D2 [label="D.n=2"]

C [label="C.n=2"] C2 [label="C.n=2"] C3 [label="C.n=1"] C4 [label="C.n=1"]

a1 [label="a"] a2 [label="a"]

b1 [label="b"] b2 [label="b"]

c1 [label="c"] c2 [label="c"] c3 [label="c"] c4 [label="c"]

S -> A S -> D

A -> A2 A -> a1 A2 -> a2

D -> D2 D -> b1 D -> C

D2 -> b2 D2 -> C2

C -> C3 C -> c1

C3 -> c2

C2 -> C4 C2 -> c3

C4 -> c4

}

</graphviz>

Ejercicio 04[editar]

Ejercicio 05[editar]

Ejercicio 06[editar]

Ejercicio 07[editar]

Ejercicio 08[editar]

Ejercicio 09[editar]

La gramatica G = <VT = {num, .,+}, VN = {E, T},E, P>, donde P es:

E −> E + T | T
T −> num.num | num

genera expresiones formadas por la aplicacion del operador + a constantes enteras y reales. Cuando se suman dos enteros, el resultado es entero, y en cualquier otro caso es real.

  1. Escribir una traduccion dirigida por sintaxis que determine el tipo de las expresiones generadas por G.
  2. Extender la traduccion de (a) para que ademas traduzca las expresiones a notacion postfija. Los dos operandos del + deben ser del mismo tipo, y para esto se debe usar el operador unario a_real que convierte un valor entero a un valor real equivalente.

Respuesta:

Item 1, simplemente se burbujea un atributo sintetizado con el tipo.

E −> E2 + T {E.tipo := (if E2.tipo = T.tipo = int then int else real)}
E -> T {E.tipo := T.tipo}
T −> num.num {T.tipo := real}
T -> num {T.tipo := int}

Para el item 2 deben imprimirse los operandos primero y el operador despues, conviene agregar un atributo val para T que indique que imprimir.

E −> E2 + T { 
   if (E2.tipo = T.tipo = int) {
     E.tipo := int;
     print(T.val ++ '+');
   } else {
     E.tipo := real;
     if (E2.tipo = int) print('toReal'); 
     print(T.val);
     if (T.tipo = int) print('toReal');
     print('+');
   }
 }

E -> T {
   E.tipo := T.tipo;
   print(T.val);
 }

T −> num.num {T.tipo := real; T.val := value(num.num)}
T -> num {T.tipo := int; T.val := value(num)}

Ejercicio 10[editar]

Ejercicio 11[editar]

Ejercicio 12[editar]

Ejercicio 13[editar]