Ejercicios de Gramaticas Compiladores 2

Bueno, saludos a todos, quiero compartir ejercicios que resolvimos sobre gramaticas (Traduccion Dirigida por la Sintaxis) con unos compañeros y que fueron de mucha utilidad cuando lleve el curso de Compiladores 2, espero que les sea de ayuda, si alguien encuentra algun error favor de comentarlo (y si pueden componerlo) para subir el problema corregido.

Problema 1

Escriba una definicion dirigida por la sintaxis para una gramatica que reconoce expresiones aritmeticas en notacion postfijo, de tal manera que genere la misma expresion pero en notacion prefijo e infijo.

S ->E         {write(“prefijo: “ E.pre); write(“infijo:” E.inf); }
E >  E E +  { E.pre = concat(‘+’, E1.pre, E2.pre); E.inf = concat(E1.inf, ‘+’, E2.inf); }
       | E E    {E.pre = concat(‘’,E1.pre, E2.pre); E.inf = concat(E1.inf, ‘’,E2.inf); }
       | E E * { E.pre = concat(‘*’, E1.pre, E2.pre); E.inf = concat(E1.inf, ‘*’, E2.inf); }
       | E E /  { E.pre = concat(‘/’, E1.pre, E2.pre); E.inf = concat(E1.inf, ‘/’, E2.inf); }
       | ( E )   { E.pre = E1.pre; E.inf = E1.inf }
       | num   { E.pre = num; E.inf = num }

Problema 2

Para la siguiente gramatica que reconoce expresiones regulares, escriba una definición dirigida por la sintaxis que genere el arbol de la epresion y que al final pueda indicar cuantas hojas fueron creadas, y que muestre la misma expresion regular sin parentesis redundantes.

Precedencia en expresiones regulares:
*=1
.=2
|=3

S::=E
E::= E|E {  E.ptr=crear_Nodo(‘|’,E1.ptr,E2.ptr)
                 E.cad=concat(E1.cad,’|’,E2.cad);
                 E.pre=1;
              }
E::=E.E{ E.ptr=crear_Nodo(‘.’,E1.ptr,E2.ptr)
               if (E1.pre<2) Then E1.cad=concat(‘(‘, E1.cad, ‘)’);
               if (E2.pre<2) Then E2.cad=concat(‘(‘, E2.cad, ‘)’);
              E.cad=concat (E1,’.’,E2);
              E.pre=2;
            }
E::=E*E{   E.ptr=crear_Nodo(‘*’,E1.ptr,E2.ptr)
                 if (E1.pre<3) Then E1.cad=concat(‘(‘, E1.cad, ‘)’);
                 if (E2.pre<3) Then E2.cad=concat(‘(‘, E2.cad, ‘)’);
                 E.cad=concat (E1,’*’,E2);
                 E.pre=3;
             }
E::=(E){   E.ptr=E1.ptr;
               E.cad=E1.cad;
               E.pre=E1.pre;
             }
E::=id{ E.ptr=Nodo_Hoja(id)
            E.cad=id;
            E.pre=4;
         }
E::=num{ E.ptr=Nodo_Hoja(num);
                E.cad=num;
                E.pre=4;
              }

Problema 3

Escriba una gramatica que reconozca numeros binarios de la forma 101.101 teniendo como componente lexico el 0 y el 1, escriba una definicion dirigida por la sintaxis que calcule el valor correspondiente en decimal. Ejemplos: 1.1 en decimal equivale a 1.5, 10.10 en decimal equivale a 2.5, 11.11 en decimal equivale a 3.75, 101.101 en decimal equivale a 5.625.

Problema resuelto utilizando Atributos Heredados:

S->{L1.ladoh = 1; }L .{L2.ladoh = 0; } L { write (L1.val +”.”+ L2.val) }
       |L { write (L1.val ) }
L ->{L1.lado = L.lado }L B {
                                                 L.base = L1.base*2
                                                 if (L.lado==1)
                                                      L.val = L1.val*2+B.val
                                                 else
                                                      L.val = L1.val+B.val / L.base
                                             }
L->{B1.lado = L.lado }B {
                                            L.base =2
                                            if (L.lado==1)
                                                L.val = B.val
                                           else
                                                L.val =B.val / 2
                                        }
B ->  0 {B.val=0}
        | 1 {B.val=1}

101.101 = 101 = 2^2 + 0^1 + 2^0 = 4 + 0 + 1 = 5
0.101 = 1*1/2 + 0*1/4 + 1*1/8 = 0.625

Problema resuelto utilizando Atributos Sintetizados:

S->   L . L { write (L1.val1 +”.”+ L2.val2) }
         |L { write (L1.val1 ) }
L- >L B {
                 L.base = L1.base*2
                 L.val1 = L1.val1*2+B.val
                 L.val2 = L1.val2+B.val / L.base
              }
L->B {
               L.base =2
               L.val1 = B.val
               L.val2 =B.val / 2
}
B- >  0 {B.val=0}
       | 1 {B.val=1}

Problema 4

Escriba una definicion dirigida por la sintaxis donde unicamente utilice atributos sintetizados, para una gramatica que reconozca la declaracion de variables de acuerdo a la siguiente sintaxis: [tipo] Lista de identificadores: la que consta de un tipo (integerchar), seguido de una lista de identificadores y a partir de ello obtener la salida: Tipo:identificador, para cada identificador. Asuma que utiliza un analizador de sintaxis ascendente. Ejemplo:

Cadena de entrada: integer [a,b,c]

Salida: a:integer
b:integer
c:integer

S::= L ‘]’
L::= L ,id{
                   write(id,’:’,L1.tipo)
                   L.tipo=L1.tipo
               }
|’integer’ ‘[‘ id{
                             write(id,’:’,’integer’ )
                             L.tipo=’integer’
                        }
|’char’ ‘[‘ id{
                        write(id,’:’,’char’ )
                        L.tipo=char
                     }

Problema 5

Escriba una definicion dirigida por la sintaxis que reconozca el mismo lenguaje y genere la misma salida del tema anterior (Problema 4), pero asuma que el analizador de sintaxis es descendente. 

S::= L ]

L::= TIPO [ id { write(id,’:’,Tipo.tipo); Lh’.tipo=TIPO.tipo} L{L.tipo=Ls’.tipo; }

L’::= , id { (id,’:’,Lh’.tipo); Lh’.tipo=L’.tipo } L’ { L’.tipo= Ls’.tipo; }

| epsilon{Ls’.tipo=Lh’.tipo; }

TIPO::=char {TIPO.tipo=char}

            |int {TIPO.tipo=int}

Problema 6

Las siguientes reglas definen la traduccion de una palabra en ingles al seudolatin:

• Si la palabra comienza con una cadena no vacia de consonantes, desplegar la cadena inicial de         consonantes al final de la palagra y añadir el sufico AY, por ejemplo: PROBLEM se compierte en OBLEMPRAY
•  Si la palabra comienza con una vocal, añadir el sufico YAY, por ejemplo: OWL se convierte en OWLYAY
•  U depues de Q es una consonante
•  Y al inicio de una palabra es una vocal si no va seguida de una vocal
•  Las palabras de una sola letra no se modifican

TERMINALES

C=letras consonantes menos la letra Y 

V=letras vocales 

UQ=uq 

Y=y

Por si las dudas, que produce C, V, UQ y Y

C::=b|c|d|f|g|h|j|k|l|m|n|ñ||p|q|r|s|t|v|w|x|z

V::=a|e|i|o|u

UQ::=uq

Y::=y

S::=L

L::= LCo    L     {write(L.cad, LCo.cad,’AY’)} //Lista de consonantes seguido de lista de cualquier letra

|LVo    L           {write(LVo.cad, L.cad, ‘YAY’)} //Lista de vocales seguido de lista de cualquier letra

|Y    LCo    L    {write(L.cad, LCo.cad,Y, ’AY’)}// letra Y seguido de lista de consonantes seguido de lista de cualquier letra

|Y    LVo    L    {write(write(L.cad,Y, ’AY’) )}//Letra Y seguidoLista de vocales seguido de lista de cualquier letra

LCo:= LCo    C{LCo.cad=LCo1.cad+C} //LCo es lista de consonantes menos la letra Y

|LCo    UQ       {LCo.cad=LCo1.cad+UQ}

|LCo    Y          {LCo.cad=LCo1.cad+Y}

|C                     {LCo.cad=C}

|UQ                  {LCo.cad=UQ}

LVo::=LVo V   {LVo.cad=LVo1.cad+V} / /LVo es lista de vocales

|V                     {LVo.cad=V}

L::= L C           {L.cad=concat(L.cad+C)} // Es lista de cualquier cosa

|L V                  {L.cad=concat(L.cad+V)}

|UQ                  {L.cad=uq}

|Y                     {L.cad=y}

Problema 7

Para una gramatica que reconozca de expresiones aritmeticas escriba un esquema de traduccion que permita evaluar las expresiones y muestre el valor final asumiendo que el operador “+” tiene mayor precedencia que el operador “*”.

S::=E       {write(“El valor es: ”, E1.val)}

E::= E*T  {E.val=E1.val*T.val}

      |T       {E.val=T.val}

T::= T+F  {T.val=T1.val+F.val}

      |F       {T.val=F.val}

F::= (E)    {F.val=E.val}

      |num   {F.val=num}

Problema 8

Escriba una definición dirigida por la sintaxis para una gramática que reconozca la declaración de variables de acuerdo a la sintaxis del lenguaje pascal, la que cosnst de una lista de identificadores seguida de un tipo de dato (integer char) y a partir de ello obtener la siguiente salida: (solo debe usar atributos sintetizados). ejemplo:

Cadena entrada: a,b,c: integer; Salida: 

   a->integer

   b->integer

   c->integer

Total de variables declaradas: 3

Dec -> ListaDec{ print(ListaDec.cad)}

ListaDec-> id , ListaDec{ ListaDec.tipo=ListaDec1.tipo

                                         ListaDec.cad=concat(Id, '>',ListaDec1.tipo, ',' ListaDec.cad)

                                      }

                  | id : TIPO                     { ListaDec.tipo=TIPO.tipo ListaDec.cad=concat(id, '>', TIPO.tipo)}

TIPO ->’char’              {TIPO.tipo=’char’}

             |’int’                {TIPO.tipo=’integer’}

Solucion propuesta por el ingeniero:

S::=X

X::={L.tipo=TIPO.tipo} L ‘:’ TIPO

L::= L , id{write(id,L1.tipo)}

       |id  {write(id,L.tipo)}

TIPO::=’char’{TIPO.tipo=’char’}

            |’int’{TIPO.tipo=’int’}

Lo que dice el ingeniero es que es la solucion correcta pero no se puede implementar, todos los atributos sintetizados son por la izquierda, los atributos heredados no siempre van a ser por la izquierda.

Problema 9

Para una gramática que reconoce expresiones aritméticas, con los operadores de + y *, escriba una definición dirigida por la sintaxis para un analizador de sintaxis ascendente, que transforme la expresión de entrada, como se muestra en los ejemplos siguientes:

Entrada: 1, Salida : 1

Entrada : 1 + 2+3, Salida : SUM ( 1,2,3)

Entrada : 1 + 2 * 3, Salida : SUM ( 1, MUL ( 2,3))

Entrada: 1 + 2 +3*4 *3+5 +6, Salida: SUM ( 1, 2, MUL (3, 4, 3), 5, 6)

Entrada: (1+ 2+3) * 4 * ( 3 + 5+ 6), Salida : MUL ( SUM (1, 2, 3) , 4, SUM (3, 5, 6))

Entrada (2 + 3) * 4 * ( 3 + 5), Salida : MUL ( SUM (2, 3), 4 , SUM (3, 5))

S-> E { if(E.op=1) write(‘sum(‘,E.op’)’);

             if(E.op=2) write(‘mul(‘,E.op’)’);

           }

E-> E+E{ if(E1.op!=1 and E1.op!=0)

                     E1.cad=concat(‘mul(‘ , E1.cad, ’)’);

                if(E2.op!=1 and E2.op!=0)

                     E2.cad=concat(‘mul(‘ , E2.cad, ’)’); 

                     E.cad=concat(E1.cad, ‘ , ’ , E2.cad);

                     E.op=1;

               }

       |E*E { if(E1.op!=2 and E1.op!=0)

                       E1.cad=concat(‘sum(‘ , E1.cad, ’)’);

                  if(E2.op!=2 and E2.op!=0)

                       E2.cad=concat(‘sum(‘ , E2.cad, ’)’);

                       E.cad=concat(E1.cad, ‘ , ’ , E2.cad);

                       E.op=2;

                  }

       |(E)      {E.cad=E1.cad; E.op=E1.op;}

       |NUM {E.cad=NUM.cad; E.op=0;}

Otra posible solucion:

S->E{ write(E1.op,’(‘,E1.cad,’)’); }

E->E+E{

          if(E1.op==”” || E1.op==”sum”)then

               E.cad=concat(E1.cad,’,’);

          else

               E.cad=concat(E1.op,’(‘,E1.cad,’)’);

          endif

          if(E2.op==”” || E2.op==”sum”)then

               E.cad=concat(E.cad,E2.cad,’,’);

          else

               E.cad=concat(E.cad,E2.op,’(‘,E2.cad,’)’);

          endif

     }

|E*E{

        if(E1.op==”” || E1.op==”mul”)then

             E.cad=concat(E1.cad,’,’);

        else

             E.cad=concat(E1.op,’(‘,E1.cad,’)’);

        endif

        if(E2.op==”” || E2.op==”mul”)then

             E.cad=concat(E.cad,E2.cad,’,’);

        else

             E.cad=concat(E.cad,E2.op,’(‘,E2.cad,’)’);

        endif

}

|num{

        E.op=””;

        E.cad=num;

}