Ejemplos Gramaticas

Gramaticas

Ejercicios de Gramaticas que encontre en un mi cuaderno y en un  blog, casi siempre se ven los mismos ejercicios y practicar es lo IMPORTANTE aqui.(si existe algun error porfavor comentarlo).
via : Fuente

Problema 1

Gramatica  descendente que utiliza atributos sintetizados y heredados, para sumar y multiplicar. Retorna el valor de la operacion

S ->E {write("El resultado es: ", E.val); }

E ->  T { Eh.val = T.val; } E' { E.val = E'.val; }
 
E' -> + T {E'1h.val = E'h.val + T.val; } E' { E'.val = E'1.val;}
          | ɛ {E's.val = E'h.val;}

T -> F {T'h.val = F.val; } T' {T.val = T'.val;} 

T' -> * F {T'1h.val = T'h.val;} T'{ T'.val = T'1.val;}
          | ɛ {T's.val = T'h.val;}

 F ->  ( E )  {F.val = E.val; }
          | num   { F.val = val(num); }

Problema 2

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 3

Para la siguiente gramatica que reconoce expresiones regulares, escriba una definición dirigida por la sintaxis que genere el arbol de la expresion y que al final pueda indicar cuantas hojas fueron creadas, y ademas 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 4

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;}

Cadenas de Entrada de prueba:

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 5

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 (integer o char), 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 6

Escriba una definicion dirigida por la sintaxis que reconozca el mismo lenguaje y genere la misma salida del tema anterior (Problema 5), 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 7

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= todas las letras consonantes excepto la letra Y 

V=letras vocales

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 8

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 9

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 consta de una lista de identificadores seguida de un tipo de dato (integer o 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 10

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”){

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

          }else{

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

          }

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

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

          }else{

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

          }

     }

      | E * E {

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

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

        }else{

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

        }

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

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

        }else{

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

        }

}

|num{

        E.op=””;

        E.cad=num;

}