CI-1322 Examen Final


  Universidad de Costa Rica 

  Escuela de Ciencias de la 

  Computación e Informática

Profesor Adolfo Di Mare
CI-1322
I Semestre 2001

$[\/]$

CI-1322 Autómatas y compiladores

Examen Final [solución]

Lea bien el examen antes de hacerlo. El examen es a libro abierto. Cuenta la documentación. Cuenta la redacción y la ortografía. Puede hacer el examen con lápiz. Debe resolver todas las preguntas. ¡No haga más de lo que se le pide!

1) [33 pts] Hay muchas formas de escribir una fecha:

25 marzo 1
25 marzo 01
25 marzo 2001
25 mar 1
25 mar 01
25 mar 2001

marzo, 25 1
marzo, 25 01
marzo, 25 2001
mar, 25 1
mar, 25 01
mar, 25 2001

25/3/1
25/3/01
25-3-1
25-3-01

etc...

1.a) [16 pts] Haga un programa Perl que lea un archivo y reconozca fechas escritas en cualquier formato. Cada vez que encuentre una fecha, debe convertirla al formato (YYYY/MM/DD). Grabe tal cual lee el resto del archivo.

1.b) [16 pts] Haga lo mismo pero usando un programa generado usando Lex/Flex.

2) [33 pts] Considere el lenguaje de paréntesis anidados, en que las hileras tienen esta forma: [] () [[[]]] ((())) [([ ([( )]) ])]

2.a) [11 pts] Escriba una gramática SLR(1) que sirva para generar todas las hileras de paréntesis anidados. Evite que la hilera nula sea generada.

2.b) [11 pts] Encuentre las tablas que un analizador sintáctico SLR(1) usaría para reconocer hileras este lenguaje.

2.c) [11 pts] Muestre cómo un analizador sintáctico que use las tablas que usted calculó reconocería la siguiente hilera (suponga que el analizador léxico salta sobre los espacios en blanco):

[] (()) [([ ])]

3) [33 pts] El lenguaje C tiene una instrucción con la siguiente forma: for ( exp₁; exp₂; exp₃ ) { stmt }

3.a) [11 pts] Haga un diagrama en el que muestre cómo debe quedar compilado este código.

3.b) [22 pts] Escriba un esquema de traducción por sintaxis que transforme un ciclo for en código objeto para una máquina de pila. Debe usar la pareja Lex/Yacc o Flex/Bison en su respuesta.

Examen de Ampliación [solución]

Lea bien el examen antes de hacerlo. El examen es a libro abierto. Cuenta la redacción y la ortografía. Puede hacer el examen con lápiz. Resuelva todas las preguntas. ¡No haga más de lo que se le pide!

1) [33 pts] Programación Perl

Haga un programa que lea un grupo de archivos ASCII para obtener de ellos las direcciones electrónicas de las solicitudes que haga. Los archivos contienen colecciones de mensajes de correo electrónico como las que se muestran en la siguiente figura:

From cyberteq3@mafalda.teletel.com.ar  Wed May 20 07:51:15 1998
Return-Path: <cyberteq3@mafalda.teletel.com.ar>
Received: from teletel.com.ar (200.10.110.101)
    by mail02.rapidsite.net (8.8.5/8.8.5) with SMTP id JAA03974
    for <ci1322@ecci.ac.cr>; Wed, 20 May 1998 09:50:40 -0400 (EDT)
Received: from pc3 by teletel.com.ar with smtp
    (Smail3.1.29.1 #2) id m0yc3eF-000sC; Wed, 20 May 98 10:50 GMT
Message-Id: <m0yc3eF-000gcsC@teletel.com.ar>
Comments: Authenticated sender is <cyberteq3@mail.teletel.com.ar>
From: Juan Ramos <cyberteq3@smail.teletel.com.ar>
To: ci1322@ecci.ac.cr
Date: Wed, 20 May 1998 10:57:43 +0000
MIME-Version: 1.0
Content-type: text/plain; charset=US-ASCII
Content-transfer-encoding: 7BIT
Subject: Carta al estudiante I-Sem-1995
Priority: normal
X-mailer: Pegasus Mail for Win32 (v2.53/R1)
X-Loop-Detect: 1
Status: RO
X-Status:

Quiero información sobre el curso para un estudio personal.

Figura 3

      El renglón From: aparece siempre antes del renglón Subject:, y contiene la dirección de correo electrónico a extraer. En el renglón Subject: viene la indicación de la información a extraer. Para este ejemplo, al procesar el archivo su programa debe extraer los siguientes datos:
      Juan Ramos <cyberteq3@smail.teletel.com.ar>
      http://www.ecci.ac.cr/~ci1322/1995-1

Cada archivo a procesar contiene muchos mensajes. Su programa debe dejar en la salida estándar todas las parejas de renglones que extraiga. Sin embargo, cuide de evitar procesar renglones que no contengan la línea de Subject:.

  Diane Wood Sponheim <dsponhei@luthersem.edu> 
  http://www.ecci.ac.cr/~ci1322/1995-1

  Vary Blanco <Vary@hotmail.com>
  http://www.ecci.ac.cr/~ci1322/1997-2

  Concepcion Larios <concep@caribe.net>
  http://www.ecci.ac.cr/~ci1322/1995-2

  Asparagus Jovenus <beavis@hp9000.cpd.uva.es>
  http://www.ecci.ac.cr/~ci1322/1996-1

  Andres Rivera <arivera@quercus.inbio.ac.cr>
  http://www.ecci.ac.cr/~ci1322/1998-1

  Carolina Uribe <mcuribe@reymoreno.net.co>
  http://www.ecci.ac.cr/~ci1322/1993-3

Figura 4

2) [66 pts] Considere el lenguaje de paréntesis anidados, en que las hileras tienen esta forma: [] () [[[]]] ((())) [([ ([( )]) ])]

2.a) [11 pts] Escriba una gramática LL(1) que sirva para generar todas las hileras de paréntesis anidados. Evite que la hilera nula sea generada. Use tres o menos no terminales.

2.b) [11 pts] Encuentre las tablas que un analizador sintáctico LL(1) usaría para reconocer hileras este lenguaje.

2.c) [11 pts] Encuentre las tablas que un analizador sintáctico SLR(1) usaría para reconocer hileras este lenguaje.

2.d) [11 pts] Muestre cómo un analizador sintáctico LL(1) que use las tablas que usted calculó reconocería la siguiente hilera (suponga que el analizador léxico salta sobre los espacios en blanco):

[] (()) [([ ])]

2.e) [11 pts] Muestre cómo un analizador sintáctico SLR(1) que use las tablas que usted calculó reconocería la siguiente hilera (suponga que el analizador léxico salta sobre los espacios en blanco):

[] (()) [([ ])]

2.f) [11 pts] Compare la cantidad de esfuerzo que tiene que hacer el analizador sintáctico LL(1) respecto del SLR(1), y explique cuál de los dos es má eficiente en términos de tiempo y de espacio.

Soluciones

$[/\]$