Tema 5: Generación de código
Horas de trabajo estimadas y calendario de clases
Posible planificación del trabajo al ritmo de las clases presenciales:
15/04 - 22/04 - 29/04 - 06/05 - 13/05 - Para saber más
Presentación
El objetivo de este tema es ver cómo, recorriendo recursivamente el AST obtenido en las fases de análisis, podemos traducir a un lenguaje destino de bajo nivel un programa fuente escrito en un lenguaje de programación de alto nivel. Por ello, el índice coincide en parte con el de la asignatura Metodología y Tecnología de la Programación. No incluimos la reserva de memoria dinámica ni la optimización del código obtenido (a los estudiantes interesados en esos temas se les indicará dónde estudiarlos en la bibliografía). Supondremos que los estudiantes han cursado también las asignaturas Introducción a los Computadores y Arquitectura de Computadores I, y ya han aprendido por tanto lo necesario sobre programación en ensamblador y organización de la memoria.
Esta es la parte del curso en la que el contenido teórico es menor. Las explicaciones necesarias se darán en clase utilizando ejemplos con los lenguajes de la práctica 4. La mayoría de los ejercicios de este tema coinciden también con los de esa práctica, de modo que el tiempo de trabajo total (en clase y fuera de clase) del tema 5 contribuye a realizar la práctica 4 en el plazo previsto, y al mismo tiempo el trabajo de la práctica 4 contribuye a aprender el contenido del tema. Es importante intentar seguir cada semana la planificación propuesta, para poder abordar en cada sesión problemas de dificultad creciente habiendo superado los anteriores.
Al finalizar la práctica 4 se recomienda dedicar al menos 10 horas a resolver ejercicios sobre Minicomp en exámenes de cursos anteriores. En esta página se propone una selección con varios tipos de problemas.
Plan de trabajo y bibliografía recomendada
- 5.1 Tipos de datos básicos: enteros y reales. Expresiones
aritméticas. Variables y asignación. Entrada/salida.
Semana del 15/04/2010
- Mira este ejemplo 1 y este LEEME.
- Piensa cómo resolver lo que se propone en las versiones 1 a 5 de la práctica 4.
- 5.2 Expresiones lógicas. Sentencias de control de flujo condicionales e iterativas.
Semana del 22/04/2010
- Mira este ejemplo 2 y este fichero NodoMenor.
- Resuelve este control
de generación de código del grupo TE2 del curso
2008/2009.
Después mira y compara estas tres soluciones.
- Piensa cómo resolver lo que se propone en las versiones 6
a 8.1 de la práctica
4.
- Resuelve el primer ejercicio de este control de generación de código del grupo TE2 del curso 2007/2008.
Después mira la primera de estas tres soluciones y resuelve el ejercicio adicional que se propone si no lo has hecho ya.
- Resuelve el primer ejercicio de este control de generación de código del grupo TE2 del curso 2007/2008.
- 5.3 Tipos estructurados: cadenas estáticas y vectores estáticos multidimensionales.
Semana del 29/04/2010
- Mira este ejemplo 3.
- Mira este ejemplo 4.
- Piensa cómo resolver lo que se propone en las versiones
8.2 y 9 de la práctica 4.
- Resuelve el segundo ejercicio de este control de generación de código del grupo TE2 del curso 2007/2008. Coincide con el apartado E1 (inversión de vectores) en la pregunta 1 del examen de diciembre 2007; la última frase se dijo en la pizarra en ese examen.
- 5.4 Funciones. Recursividad.
Semana del 06/05/2010
- Mira este ejemplo 5.
- Mira este ejemplo 6.
- Mira este ejemplo 7.
- Piensa cómo resolver lo que se propone en las versiones 10 y 11 de la práctica 4.
- Ejercicios adicionales.
Semana del 13/05/2010 y siguientes
- En la pregunta 1 de los exámenes de cursos
anteriores puedes encontrar ejercicios adicionales
sobre modificaciones de Minicomp. Tras finalizar la
práctica 4, y como preparación final para el examen de la
asignatura, es aconsejable que hagas alguno más. Intenta
estos implementándolos hasta que funcionen, y después
compara tu solución con la que se proporciona aquí:
- Apartado E2 en la pregunta 1 del examen
de junio 2009 (escritura de rangos).
Abrir implementación de una solución.
- Apartado E2 en la pregunta 1 del examen
de diciembre 2008 (operador barra).
Abrir implementación de una solución.
- Apartado E1 en la pregunta 1 del examen
de junio 2008 (producto escalar de vectores).
Abrir implementación de una solución.
- Apartado E2 en la pregunta 1 del examen
de diciembre 2007 (polinomios).
Abrir implementación de una solución.
- Apartado E1 en la pregunta 1 del examen de septiembre 2008 (compilación condicional).
- Apartado E2 en la pregunta 1 del examen
de junio 2009 (escritura de rangos).
- Esta solución
de este examen
virtual de mayo 2005 ilustra cómo escribir la
solución de la pregunta 1 en el examen final (aunque
habría que ajustarse a los lenguajes e implementación de
la práctica 4 de este curso, que tampoco son exactamente
iguales). Observa que no se pide una implementación
completa sino una explicación por escrito, pero para
evitar ambigüedades explicando cómo se realizaría la
generación de código lo mejor es utilizar código Python
que genera código Rossi, no lenguaje natural ni
pseudo-código.
- Esta solución del segundo ejercicio del control de generación de código del grupo TE2 del curso 2007/2008 que has visto antes es un ejemplo también de cómo responder la pregunta 1 del examen final.
- Evaluación del tema 5 en el itinerario A (grupo TE2): jueves 20/05/2010.
- Otros ejercicios opcionales.
Resto del curso
Los siguientes ejercicios tampoco se incluyen en las horas previstas, pero son recomendables y se pueden discutir en tutorías o en las sesiones de refuerzo con quien quiera seguir practicando.
- Apartado E1 en la pregunta 1 del examen
de diciembre 2009 (sentencia iterativa
para-cada-tal-que).
- Apartado E2 en la pregunta 1 del examen
de diciembre 2009 (operador es-prefijo; sesiones
de refuerzo del 21/06/2010 y del 24/06/2010).
- Apartado E1 en la pregunta 1 del examen
de septiembre 2009 (búsqueda en vectores).
- Apartado E2 en la pregunta 1 del examen
de septiembre 2009 (alias; sesión de refuerzo del
21/06/2010).
- Apartado E1 en la pregunta 1 del examen
de junio 2009 (sumatorios y productorios de vectores).
- Apartado E1 en la pregunta 1 del examen
de diciembre 2008 (operadores de incremento y
decremento; sesión de refuerzo del 17/05/2010).
- Apartado E2 en la pregunta 1 del examen
de junio 2008 (sentencia de escritura múltiple;
sesión de refuerzo del 31/05/2010).
- Apartado E1 en la pregunta 1 del examen
de septiembre 2007 (recorrido de vectores).
- Apartado E2 en la pregunta 1 del examen
de septiembre 2007 (autoasignaciones sobre vectores).
- Apartado E2 en la pregunta 1 del examen
de junio 2007 (intercambios múltiples).
- Apartado E1 en la pregunta 1 del examen
de junio 2007 (rotación de vectores; sesión de
refuerzo del 24/05/2010).
- Apartado sobre interrupción de bucles en la pregunta 1 del examen de junio 2003 (completando esta solución; sesión de refuerzo del 24/06/2010).
En esta carpeta de exámenes resueltos de Minicomp tienes también bastantes implementaciones realizadas por dos estudiantes del curso 2006/2007, por si quieres compararlas con las tuyas (ten en cuenta que el profesorado resolvió las dudas planteadas por los estudiantes pero no corrigió la totalidad de la implementación; no está garantizada la ausencia de errores; en ese curso la versión inicial del compilador no era la misma de este curso, pero con diff puedes comparar cada solución con la versión inicial, que está en ese mismo directorio).
- Estudio final.
Para complementar las explicaciones de clase, lee estos apuntes de generación de código de J. M. Vilar y relaciónalos con la práctica 4. No es necesario que aprendas los pseudo-lenguajes que se utilizan en los apuntes, pero debes entender los conceptos y saber aplicarlos en la práctica.
- Otras fuentes de información.
Si quieres ver otras explicaciones de este tema:
- Una presentación alternativa la puedes encontrar en el
capítulo 6 ("Generación de código intermedio") del libro
"Compiladores
: principios, técnicas y herramientas" (2008) de A.
Aho, M.
Lam, R.
Sethi y J.
Ullman y en la versión
original en inglés. El apartado 6.6 es especialmente
interesante. En él ilustra cómo aplicar lo del apartado
5.2 empleando atributos del ETDS.
- También puedes consultar el capítulo 8 ("Generación de código") del libro "Construcción de compiladores" de K. Louden.
- Mira este ejemplo 1 y este LEEME.