Examen #2 [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)   S ==>   a
(2)   S ==> ( L )
(3)   L ==>  S L
(4)   L ==>   ε

1.a) [11 pts] Haga la tabla LL(1) para esta gramática.

1.b) [8 pts] Muestre cómo es reconocida la hilera ( a ( a ( a a a ) ) )

1.c) [14 pts] Escriba un programa Plis.c++, escrito en C++, que puede reconocer L(G). Obtenga su programa directamente de la gramática G. Los lexemas válidos para el token "a" deben ser identificadores que comienzan con una letra. Debe usar Lex.

1.d) [2 pts] Modifique su programa Plis.c++ de manera que a cada identificador "a" que esté al principio de una "lista" sea "ejecutado" usando como argumentos los demás elementos de la "lista". Llame a su programa modificado Lisp.c++. Suponga que cuenta con un diccionario de nombres de identificadores con el que puede ejecutar algunas rutinas predefinidas; por ejemplo SUM puede calcular la suma de los argumentos. Si un identificador no aparece en su diccionario, use como valor del identificador el almacenado en su "propiedad", que contiene el atributo "valor".

H -> H * K
H -> * K
L -> H
L -> 0
K -> L 1

2.a) [3 pts] Explique por qué esta gramática no es LL(1).

2.b) [12 pts] Convierta esta gramática a otra equivalente, que sí sea LL(1). Explique cómo transforma la gramática.

2.c) [12 pts] Construya el autómata LL(1) para esta gramática.

2.d) [6 pts] Escoja una hilera de al menos 7 símbolos que esté en el lenguaje L(G) y muestre cómo se procesa la hilera usando el autómata LL(1) que usted obtuvo en el punto anterior.

  3) [33 pts] Usted ha sido contratado por la CIA para examinar los documentos que fueron incautados a la red internacional de terrorismo Al-Qaeda. Por eso, usted tiene más de 100,000 archivos repartidos en varios directorios, en los que hay documentación sobre los planes de destrucción masiva de esta organización terrorista.

      Para examinar los documentos se necesita extraer información basada en palabras clave. La manera de hacerlo es con el programa "BQ-plb" que encuentre aquellos archivos que contienen las palabras buscadas.

      Su programa debe recibir una lista de palabras y encontrar todos los documentos que las contienen, tanto en el nombre del archivo como en su contenido. Con un '+' se pueden separar varios grupos de palabras, y con el '-' se puede indicar que deben aparecer 2 palabras, pero una seguida después de la otra. Esta es una posible ejecución de su programa:

D:\CIA\Al-Qaeda> BQ-plb bomb air + bus - secuestro + terremoto + quake

book 2\Secuestro y asesinato en vehículos motorizados.html
JLkmx\No más -- Un grito de esperanza.txt
Junio-18\Air strike repercutions.pdf
Junio-18\Un tsunami contra París.doc

      El operador '+' tiene el efecto de un operador de "OR" de disjunción, mientras que el espacio en blanco ' ' sirve para especificar que ambas palabras deben aparecer en el documento. Por eso la expresión "bomb air" sirve para localiza aquellos documentos que contengan ambas palabras ("bomb" y "air"). Un efecto similar tiene el operador '-', pero en este caso se requiere que una palabra aparezca antes en documento que la otra, como ocurre con la hilera "bus - secuestro", en donde el programa encontrará los documentos que contengan ambas palabras pero en donde "bus" aparezca en el documento antes que "secuestro".

3.a) [7 pts] Escriba una gramática que sirva para las hileras válidas de búsqueda del programa "BQ-plb".

3.b) [16 pts] Suponga que usted ya cuenta con la función
  bool Busque( const char * F, const char * plb, unsigned & pr, unsigned & ul );
que pone en "pr" posición en donde aparece por primera vez la palabra "plb" en el archivo "F" y en "ul" adonde aparece por última vez. Como la numeración comienza en "1", si ocurre que "pr == ul == 0" eso quiere decir que "Archivo" no contiene la hilera "Palabra", y es éste el único caso en que "Busque()" retorna "false".

      Use la función "Busque()" para incorporarle a su gramática las acciones que se requieran para que "BQ-plb" calcule sus resultados.

3.c) [10 pts] Use Lex para implementar el analizador léxico para "BQ-plb".

for (numero = 1; numero <= N; ++numero) { suma = 0; temp = numero; while ( temp != 0 ) { // suma de dígitos digito = temp % 10; // al cubo suma = suma + (digito * digito * digito); temp = temp / 10; } if (suma == numero) { cout << numero << " Suma de sus dígitos al cubo " << suma << endl; } }

4.a) [0 pts] Diga cuáles son los tokens y cuáles son los lexemas en este bloque de código.

4.b) [11 pts] Escriba una gramática LL(1) que genere la mayor parte de los programas similares éste. Explique por qué su gramática es LL(1).

4.c) [11 pts] Haga un programa Lex que sirva para obtener los tokens y lexemas de este lenguaje.

4.d) [11 pts] Escriba en C++ un analizador sintáctico recursivo descendente que reconozca este lenguaje.

A -> A 2 3    B -> B 4 2    C -> 1 C
  |  B A 3      |  2          |  3 C
  |  C                        |  4

5.a) [11 pts] Hagas las transformaciones necesarias en la gramática de manera que sirva para hacer análisis sintáctico LL(1).

5.b) [11 pts] Calcule la tabla LL(1) para esta gramática.

5.c) [11 pts] Muestre cómo sería reconocida la hilera "24213423323". Si la tabla tiene entradas duplicadas, elimine los duplicados dejando aquella producción que aparece antes en la gramática. Comente sobre el resultado que ha obtenido.

Soluciones

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