Download Examen_CompI_Feb04 - Universidad de Zaragoza

Compiladores I
1ª Convocatoria 04/05 (02-02-05)
4º Ing. Informática. C.P.S. Universidad de Zaragoza
Ejercicio 1 (2.0 ptos.): Escribir una gramática libre de contexto, de la clase
LL(1), que genere el mismo lenguaje que la expresión regular
(a|c+|ba|bc)* b+
Probar que, efectivamente, es de dicha clase.
Ejercicio 2 (2.5 ptos.): Dada la siguiente gramática, se pretende construir el
autómata LR(1) y las tablas del análisis LR(1) para la siguiente gramática:
S: a a A| a A c| c;
A: A b | b a;
Se pide:
2A) Rellenar el contenido de los estados del autómata LR(1).
Estado 0
S
Estado 1
Estado 11
Estado 3
Estado 6
Estado 2
Estado 5
Estado 4
a
Estado 7
A
Estado 8
Estado 10
c
Estado 9
Estado 13
Estado 12
2B) A partir del autómata rellenar el contenido de la tabla acción e ir_a
correspondientes al análisis LR(1).
Compiladores I
1ª Convocatoria 04/05 (02-02-05)
4º Ing. Informática. C.P.S. Universidad de Zaragoza
a
b
c
$
S
A
Estado 0
Estado 1
Estado 2
Estado 3
Estado 4
Estado 5
Estado 6
Estado 7
Estado 8
Estado 9
Estado 10
Estado 11
Estado 12
Estado 13
2C) Determinar si se trata o no de una gramática LR(1) En caso de respuesta
negativa ¿De qué tipo es/son el/los conflictos existente(s)? ¿A qué son/es
debido(s) este(s) tipo(s) de conflicto(s)?.
2D) Realizar los pasos necesarios para analizar la cadena de entrada aacb.
Compiladores I
Pila
1ª Convocatoria 04/05 (02-02-05)
4º Ing. Informática. C.P.S. Universidad de Zaragoza
Árbol
entrada
Acción
baac$
Ejercicio 3 (1.0 ptos.): Justifica si es verdad o no la siguiente afirmación:
“Toda gramática SLR(1) es también LL(1)”
Ejercicio 4 (1.0 ptos.): Determinar si el lenguaje generado por la siguiente
gramática es finito o infinito. Razonar, tan formalmente como sea posible, la
respuesta.
S --> a a A | B
B --> a A | b
a --> b B
Compiladores I
1ª Convocatoria 04/05 (02-02-05)
4º Ing. Informática. C.P.S. Universidad de Zaragoza
Ejercicio 5 (1.5 ptos.): Sea el siguiente analizador léxico
(procesaArbolesBinarios.l)
y
el
siguiente
analizador
sintáctico
(procesaArbolesBinarios.y) para árboles binarios enteros:
%{
#include <stdio.h>
#include “procesaArbolesBinarios.tab.h”
%}
%option case-insensitive
separador
[\t \n]+
digito
[0-9]
cteEntera
{digito}+
%%
{separador}
{cteEntera}
“nil”
%%
{/*saltarlo*/}
{yylval.valCant = atoi(yytext); return tkNumero;}
{return tkNil}
%{
#include <stdio.h>
%}
%union{
struct{
.
.
int estaOrdenado;
}atributosArbol;
/*1 Está ordenado. 0 En caso contrario*/
int valCant;
}
%start Arbol
%token <valCant> tkNumero
%token tkNil
%type <atributosArbol> Arbol
%%
Arbol:
tkNumero Arbol Arbol
|
tkNil
%%
int main(){
yyparse();
exit(0);
}
{ . . . };
{ . . . };
Completar el fuente Bison con los atributos y acciones necesarias para
sintetizar el atributo “estaOrdenado”, es decir, que los valores de los
números del primer subárbol sean <= que el valor del número actual y los
valores de todos los números del segundo subárbol sean >= al valor del
número actual. Por ejemplo (2 (1 nil nil) (3 nil nil) ) está ordenado, pero ( 1 (2
nil nil) (3 nil nil) ) no lo está.