Examen #1 [solución]

      Duración: dos horas. 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 tres de las preguntas. ¡No haga más de lo que se le pide!

1) [33 pts] Como programador máximo de la firma spamTico.com usted ha conseguido varios miles de archivos de texto que contienen, además de otras cosas, cientos de miles de direcciones de correo electrónico. Usted necesita escribir un programa para extraer todas esas direcciones, y decide implementarlo usando Lex/Flex.

1.a) [8 pts] Explique cuáles hileras de un archivo de texto son direcciones de correo electrónico. Recuerde que es válido usar el guión "-", el caracter de subrayado "_" y también el punto ".". Lo que distingue a las direcciones de correo electrónico es la letra de arrobas "@". Recuerde que los archivos de entrada pueden contener cualesquiera caracteres ASCII válidos, para cuya codificación se usa el rango numérico [0..127], aunque su programa debe permitir manejar archivos con letras en el rango superior [128..255].

1.b) [25 pts] Implemente el programa Lex/Flex.

  R -> Q R | 0
  Q -> R Q | 1

2.a) [0 pts] Explique qué significa que una gramática es ambigua.

2.b) [8 pts] Encuentre una hilera de al menos 10 símbolos para la que existan 2 árboles de derivación diferentes. Explique cómo obtuvo esa hilera.

2.c) [8 pts] Dibuje los 2 árboles de derivación que correspondan a la hilera que encontró en el punto anterior.

2.d) [8 pts] Dibuje el autómata finito P que averigua si es par la cantidad de ceros o unos de una subhilera de (0+1)*.

2.e) [9 pts] Explique si L(P) == L(G). Apoye su explicación con un ejemplo o un contraejemplo.

3) [33 pts] r = ( a+ | b? ) +             s = ( a* | b* ) +

3.a) [5 pts] Para la expresión regular "r" construya el autómata no determinista "Nr" que reconoce L(r).

3.b) [5 pts] Para la expresión regular "s" construya el autómata no determinista "Ns" que reconoce L(s).

3.c) [7 pts] Obtenga el autómata determinista "Dr" para L(r). Incluya el diagrama del autómata en su respuesta.

3.d) [7 pts] Obtenga el autómata determinista "Ds" para L(s). Incluya el diagrama del autómata en su respuesta.

3.e) [9 pts] Demuestre que L(r) = L(s).

4) [33 pts] Considere la siguiente gramática para la generación de expresiones lógicas:

E --> E and E
E --> E or  E
E --> id

4.a) [8 pts] Elimine la recursividad por la izquierda de la gramática anterior y obtenga una gramática equivalente.

4.b) [8 pts] ¿Es la gramática resultado del punto anterior apropiada para traducir las expresiones a la forma postfija? Si no lo fuera, arregle el problema.

4.c) [17 pts] Implemente en C/C++ un programa que realice el análisis sintáctico predictivo para la gramática obtenida en el punto anterior. Asegúrese que al finalizar el análisis la expresión quede en postfijo para que pueda ser evaluada (usted no tiene que implementar la función de evaluación).

4.d) [0 pts] Implemente la función de evaluación para este analizador sintáctico.

Soluciones

Adolfo Di Mare <adolfo@di-mare.com>.
Copyright © 2004
Derechos de autor reservados © 2004