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