PDF de programación - Se desea implementar una calculadora con sintaxis Lisp

Compiladores I 1ª Convocatoria 95/96 (27-I-96)

4º Ing. Informática. C.P.S. Universidad de Zaragoza

Se desea implementar una calculadora con sintaxis Lisp. El programa debe procesar
una secuencia de listas Lisp tomadas de stdin. Cada lista contiene una expresión
aritmética (en notación prefija), y para cada una de ellas se debe escribir el resultado
de su expresión correspondiente. Para simplificar, asumiremos '+' y '*' como únicos
operadores.

Ejemplo: Para un fichero de entrada como el siguiente

;

(+ 2 4 6 8 10);
(* (+ 1 2 3) (+ 9 7 1))
(+

(* 10 2 3)
25
(* 8 9 (+ 1 1) )

);
(+ 20 -20);
(+ 20);
(* 30);

debe generar la salida

-> 30
-> 102
-> 229
-> 0
-> 20
-> 30

Como se puede ver en el ejemplo, los separadores en la entrada (blancos,
tabuladores, saltos de línea) no influyen en el resultado.

Ejercicio 1 (1 pto.): Escribir un fuente Lex (Flex) para el reconocimiento de los
tokens fundamentales que permitan resolver, en conjunción con los Ejercicios 2 y 3,
la calculadora deseada.

Ejercicio 2 (2 ptos.): Escribir una gramática (en Yacc/Bison) que exprese una
sintaxis (clara y concisa) para las entradas a la calculadora propuesta.

Ejercicio 3 (2 ptos.): Completar la gramática del ejercicio anterior de manera que
implemente la calculadora. Notar que basta con añadir al resultado del Ejercicio 2
las acciones necesarias.

Nota 1: Si se considera necesario, se puede establecer un nivel de anidamiento
máximo en las listas de listas de 125 niveles.

-1-

Compiladores I 1ª Convocatoria 95/96 (27-I-96)

4º Ing. Informática. C.P.S. Universidad de Zaragoza

Considérese la siguiente gramática:

ALS →
ALS →
AL →
NS →
NS →

=ALS AL
=AL
=NUM NS ',' NS '\n'
=NS N
=N

Se desea saber si se trata de una gramática SLR o no. Para ello, responder a las
siguientes preguntas.

Ejercicio 4 (2 ptos.): Construir la familia canónica de conjuntos LR(0)

Ejercicio 5 (1.5 ptos.): Construir el autómata a partir de dichos conjuntos

Ejercicio 6 (1.5 ptos.): ¿Se trata de una gramática SLR o no?

Tiempo total para el examen:

3 horas

-2-

=
=
=
=
=
=
=
=
=
=
=
Compiladores I 2ª Convocatoria 95/96 (22-VI-96)

4º Ing. Informática. C.P.S. Universidad de Zaragoza

Ejercicio 1: Considérese la siguiente gramática:

=[ S
| S1

S ∅
S1 ∅

=[a]

1.1) (1 pto.) Establecer el lenguaje que genera. Es necesario que se justifique,

lo más formalmente posible, la respuesta dada

1.2) (1.5 ptos.)
1.3) (1 pto.) ¿Se trata de una gramática LL(1)?
1.4) (0.5 ptos.)

¿Se trata de una gramática SLR(1)?

Si no es SLR(1), dar una gramática equivalente que sí lo
sea. Análogamente, si no es LL(1) dar una gramática equivalente que sí lo
sea.

Ejercicio 2 (1.5 ptos.): Considerar una analizador LR. Para definir una lista no vacía
de identificadores podemos pensar en las siguientes alternativas:

a) listaID:
|

listaID ID
ID

b) listaID:
|

ID listaID
ID

¿Son igualmente correctas las dos definiciones? ¿En qué se diferencia el
funcionamiento de una y otra? Si ambas son correctas, ¿Cuál de ellas es más
aconsejable? Ejemplificarlo con los sucesivos cambios de estado de la pila del
analizador sintáctico para la secuencia de tokens

ID ID ID ID

Ejercicio 3 (2.5 ptos.): "Boxes" es un lenguaje para la descripción de secuencias de
cajas (planas) que se incluyen unas en otras. La siguiente figura muestra en la parte
izda. un programa fuente en dicho lenguaje, y en su parte dcha. el resultado gráfico
de su ejecución.

-1-

=
=
=
=
=
=
=
=
Compiladores I 2ª Convocatoria 95/96 (22-VI-96)

4º Ing. Informática. C.P.S. Universidad de Zaragoza

v 2,3
[

h 1,1
[

---+
++++

]
h 2,1,2
[

++++
----
v 1,1
[

+++-
-+-+

]

]

]

El significado del fuente es el siguiente:

v 2,3: indica que la caja en cuestión se va a dividir verticalmente en dos cajas. La
primera (empezando por la izda.) ocupará 2/5 del total, mientras que la segunda
ocupará los 3/5 restantes. Lo que le sigue entre [....] son las descripciones de las cajas
interiores.

h 1,1: indica que la primera de las subcajas (la que ocupaba los 2/5 de la izda.)
se va a dividir horizontalmente en dos subcajas, ocupando cada una la
mitad del espacio. Para cada una de estas cajas, la secuencia formada por 4
elementos de {'+','-'} indica el color de los lados, empezando por el de más
a la izda. y girando en el sentido de las agujas del reloj: '+' indica trazo en
negro, mientras que '-' indica que no hay trazo (el lado no se dibuja).

h 2,1,2: indica que la segunda de la subcajas se divide horizontalmente en 3

cajas, que ocupan respectivamente 2/5,1/5,2/5. Y así sucesivamente.

Se pide escribir la gramática Yacc correspondiente al lenguaje Boxes.

Ejercicio 4: En un afamado centro universitario propusieron una vez el siguiente
interesante ejercicio:

Se desea implementar una calculadora con sintaxis Lisp. El programa debe
procesar una secuencia de listas Lisp tomadas de stdin. Cada lista contiene
una expresión aritmética (en notación prefija), y para cada una de ellas se
debe escribir el resultado de su expresión correspondiente. Para simplificar,
asumiremos '+' y '*' como únicos operadores.

-2-

Compiladores I 2ª Convocatoria 95/96 (22-VI-96)

4º Ing. Informática. C.P.S. Universidad de Zaragoza

Ejemplo: Para un fichero de entrada como el siguiente

;

(+ 2 4 6 8 10);
(* (+ 1 2 3) (+ 9 7 1))
(+

(* 10 2 3)
25
(* 8 9 (+ 1 1) )

);
(+ 20 -20);
(+ 20);
(* 30);

debe generar la salida

-> 30
-> 102
-> 229
-> 0
-> 20
-> 30

Como se puede ver en el ejemplo, los separadores en la entrada (blancos,
tabuladores, saltos de línea) no influyen en el resultado.

4.1) (1 pto.) Para resolver el problema, algunos de los alumnos plantearon la
siguiente gramática en Yacc:

listas: listas lista ';'

| lista ';'

;
lista: '(' operador listaSexps ')'
;
listaSexps: listaSumandos

| listaMultiplicandos

;
listaSumandos: elemento

| listaSumandos elemento

;
listaMultiplicandos: elemento

| listaMultiplicandos elemento

;
operador: '+'
| '*'

;
elemento: NUMERO

| lista

;

-3-

Compiladores I 2ª Convocatoria 95/96 (22-VI-96)

4º Ing. Informática. C.P.S. Universidad de Zaragoza

Teniendo presente la necesidad posterior de generar la calculadora (su ejecutable),
¿Es correcta la gramática presentada? Justificar la respuesta. En caso de no ser
correcta poner ejemplos de problemas que podrían surgir.

4.2) (1 pto.) A la hora de implementar la calculadora deseada, otros plantearon la
siguiente solución

%{
........
char laOp;
%}
%union{
int val;

......

}
%token NUMERO
%type <val> Sexp
%type <val> lista
%type <val> listaSexps
%type <val> NUMERO
%%
listas: listas lista ';'

| lista ';'

;
lista: '('

operador
listaSexps
')'

;

{printf("-->%d\n",$2);}

{printf("-->%d\n",$1);}

{$$=$3;}

operador: '+'
| '*'

{laOp='+';}
{laOp='*';}

;
listaSexps: listaSexps Sexp

¿Es correcta esta solución? Justificar la respuesta. En caso de no ser correcta, poner
ejemplos de problemas que podrían surgir y proponer (escuetamente) usa solución.

Tiempo total para el examen:

2 horas 30 min.

-4-

{if(laOp=='+')
$$=$1+$2;

else

$$=$1*$2;

}

{$$=$1;}

{$$=$1;}
{$$=$1;}

| Sexp

;
Sexp: NUMERO

| lista

;
%%
main()
{
yyparse();
}

Compiladores I 3ª Convocatoria 95/96 (3-IX-96)

4º Ing. Informática. C.P.S. Universidad de Zaragoza

Ejercicio 1 (3 ptos.): Los identificadores para un determinado lenguaje de
programación se definen de acuerdo con la siguiente descripción:

Un identificador puede empezar con una letra o un "underscore" (carácter
"_"), debe estar seguido por 0 ó más letras, dígitos o underscores, pero con
las restricciones siguientes:

1) No pueden aparecer dos underscores seguidos
2) Un identificador no puede terminar con un underscore.

Además, no hay ninguna limitación en cuanto a la longitud de los
identificadores.

1.1)

(1.5 ptos.) Dibujar el Autómata Finito Determinista que corresponde a
los identificadores descritos anteriormente.

Para etiquetar los arcos, en lugar de utilizar caracteres simples utilizar
las siguientes clases de caracteres:

letra
digito
und

[a-zA-Z]
[0-9]
"_"

1.2)

(1.5 ptos.) Dar una expresión
identificadores descritos anteriormente

regular correspondiente a

los

Ejercicio 2 (2 ptos.): Considérese el lenguaje libros que se define como sigue:

a)
b)
c)
d)

e)

f)

g)

Un libro es o bien una novela o bien un colección de historias cortas
Una novela consiste en un título seguido por uno o más capítulos
Un capítulo es un entero seguido por un cuerpo de capítulo
Un cuerpo de capítulo es una lista de párrafos y/o ilustraciones. La lista
debe incluir al menos un párrafo.
Una collección de historias cortas se compone de dos o más historias
cortas. Dos historias cortas se separan por una página en blanco.
Una historia corta consiste en un título seguido de un cuerpo de historia
corta
Un cuerpo de historia corta es lo mismo que un cuerpo de capítulo

-1-

Compiladores I 3ª Convocatoria 95/96 (3-IX-96)

4º Ing. Informática. C.P.S. Universidad de Zaragoza

Escribir una gramática lo más clara y compacta posible para dicho lenguaje. Utilizar
letras minúsculas para los no terminales de la gramática, así como los siguientes
terminales:

terminal

T
E
P
I
B

lo que denota

un título
un entero
un párrafo
una ilustración
una pág. en blanco

Ejercicio 3 (2 ptos.): Considérese la siguiente gramática, donde NUMERO y MAS
son los símbolos terminales:

∅ listaElementos

exp=
listaElementos ∅ NUMERO
listaElementos ∅ exp MAS NUMERO

Razonar sobre si es una gramática LL(1) o no. En caso de no serlo, dar una gramática
equivalente que sea LL(1)

Ejercicio 4 (3 ptos.): Considérese la siguiente gramática que se usa para el
t