Tema 2: Análisis léxico
Horas de trabajo estimadas y calendario de clases
Posible planificación del trabajo al ritmo de las clases presenciales:
08/10 - 15/10 - 22/10 - 29/10 - 05-12/11 - Para saber más
Plan de trabajo y bibliografía recomendada
- 2.1 Introducción.
Semana del 08/10/2009
- Lee el apartado 2.1 del libro "Construcción de compiladores" de K. Louden.
- 2.2 Expresiones regulares extendidas. Análisis y modelado
léxicos. Estrategia avariciosa.
- Los contenidos de la asignatura II20 que supondremos
conocidos son los de los apartados 3.1, 3.3 y 3.4 del
libro
"Introducción a la teoría de autómatas, lenguajes y
computación" (aunque en algún detalle menor, como el
operador de unión o la cadena vacía, utilizaremos otra
notación).
- Lee el apartado 2.2 del libro de Louden.
- En nuestro curso seguiremos los criterios de este listado de "Metacaracteres utilizados en expresiones regulares y arcos de MDD".
Semana del 15/10/2009
- Completa los ejercicios del "Bloque 2: Análisis" de esta
"Recopilación de
ejercicios sobre expresiones regulares en exámenes de
Compiladores e intérpretes" (soluciones en clase).
- Completa este "Ejercicio sobre especificaciones léxicas" (solución y otro ejemplo en clase).
Semana del 22/10/2009
- Completa todos los ejercicios del "Bloque 1: Modelado" de
esta "Recopilación
de ejercicios sobre expresiones regulares en exámenes de
Compiladores e intérpretes".
Tras intentarlos, mira estos ejemplos de soluciones correctas e incorrectas (explicación y más soluciones en clase): ejercicio 1A, ejercicio 4, ejercicio 5 (el 3 es análogo), ejercicio 6A, ejercicio 6B.
- 2.3 Autómatas Finitos Deterministas (AFD) y Máquinas Discriminadoras Deterministas (MDD).
Semana del 29/10/2009
- Los contenidos de la asignatura II20 que supondremos
conocidos son los del capítulo 2 del libro
"Introducción a la teoría de autómatas, lenguajes y
computación", aunque nos limitaremos a trabajar con
AFDs.
- Lee el apartado 2.3 del libro de Louden. Seguiremos
otros convenios para representar las MDDs, pero el libro
te puede ayudar a entender los principios generales.
- En nuestro curso seguiremos los criterios del último
apartado de este listado de "Metacaracteres
utilizados en expresiones regulares y arcos de MDD".
- De estos "Ejercicios
sobre autómatas finitos y otras máquinas
deterministas", resuelve los cuatro primeros
(solución y otro ejemplo en clase).
- Mira este ejemplo de
implementación mediante control de flujo
correspondiente a la MDD del ejercicio 3
anterior. Intenta hacer algo similar en la práctica 1.
Después mira este ejemplo de implementación mediante una tabla de transición de estados correspondiente a la misma MDD.
- Ejercicios adicionales.
Semanas del 05/11/2009 y 12/11/2009
Intenta resolver cada uno de los siguientes ejercicios en menos de 45 minutos sin ningún error, y observa el nivel de preparación que se valora en el examen.
- Pregunta 2 en el examen
de septiembre 2009.
Abrir solución (AFD).
Abrir solución (expresión regular).
- Pregunta 2 en el examen
de junio 2009.
Abrir solución (se ha supuesto que no hay que aceptar la cadena vacía; si hubiese que aceptarla, lo único que cambiaría es que el estado 1 sería final).
- Pregunta 2 en el examen de diciembre 2008 (solución en clase).
Abrir solución (AFD).
Abrir solución (expresión regular).
- Pregunta 2 en el examen
de septiembre 2008 (solución en clase).
Abrir solución (AFD).
Abrir solución (expresión regular; incluye ejemplos de soluciones incorrectas).
- Pregunta 2 en el examen
de junio 2008.
Abrir solución (AFD).
Abrir solución (expresión regular).
- Control
de análisis léxico del grupo TE1 del curso 2008/2009
(incluye posibles soluciones; más en clase).
- Control de análisis léxico del grupo TE2 del curso 2008/2009 (solución en clase).
- Evaluación del tema 2 en el itinerario A (grupo TE2): jueves 10/12/2009.
- Otros ejercicios opcionales.
Resto del curso
Los siguientes ejercicios no se incluyen en las hora previstas, pero se pueden discutir en tutorías o en las sesiones de refuerzo con quien quiera seguir practicando.
- Control de
análisis léxico del grupo TE2 del curso 2007/2008.
- Pregunta 2 en el examen de diciembre 2007.
Abrir solución (incluye ejemplos de soluciones incorrectas).
- Pregunta 2 en el examen de diciembre 2005.
Abrir solución (incluye una propuesta de ejercicios adicionales).
Abrir solución (AFD de los ejercicios adicionales).
- Pregunta 2 en este examen de septiembre 2005 (día 8, E79).
- Pregunta 2 en este otro
examen de septiembre 2005 (día 16, II26; sesión de refuerzo del 03/05/2010).
- Pregunta 2 en el examen virtual de mayo 2005.
Abrir solución (del examen completo).
- Pregunta 2 en el examen de septiembre 2003.
Abrir solución (incluye una propuesta de ejercicios adicionales).
- Pregunta 2 en el examen de
junio 2003.
Abrir solución (del examen completo; ten en cuenta que falta representar que el estado G es final, los apartados sobre MM3 no nos interesan, y la notación del último apartado para limitar la talla a 80 no la aceptamos este curso).
- Pregunta 2 en el examen de diciembre 2002 (sesión de refuerzo del 10/05/2010).
- Pregunta 3 en el examen de diciembre 2001.
- Pregunta 3 en el examen de septiembre 2001.
- Temario opcional.
Los siguientes apartados no se incluyen en las horas previstas en el curso 2009/2010 ni serán exigibles en el examen, pero se pueden explicar en tutorías a quien tenga interés.
- Utilización del generador de analizadores léxicos flex.
- Construcción de un AFD a partir de una expresión regular mediante el algoritmo de los items.
- Los contenidos de la asignatura II20 que supondremos
conocidos son los de los apartados 3.1, 3.3 y 3.4 del
libro
"Introducción a la teoría de autómatas, lenguajes y
computación" (aunque en algún detalle menor, como el
operador de unión o la cadena vacía, utilizaremos otra
notación).
