Compiladores

Ultima modificación: Lunes, Febrero 9/2009 12:30pm

Volver a la Página Principal.

Boletín del Curso: 1er Semestre del 2009
Notas del Curso: Notas
Recursos en la Red

Material Opcional de preparación para los ECAES

Lenguajes Formales y Expresiones Regulares
Autómatas
Autómatas de Pila
Gramáticas y Lenguajes Libres de Contexto
Máquinas de Turing

Temas que se evalúan en el ECAES

SUBÁREA: LENGUAJES FORMALES Y AUTÓMATAS
Justificación. Con esta denominación se agrupan temas que, en currículos clásicos, pueden ser incluidos en cursos de lenguajes formales o de compiladores.
Al enunciar 'Autómatas' dentro de los temas del área se ha advertido que no se quiere incluir el tema de autómatas en toda la extensión de la palabra (teoría de autómatas, por ejemplo), sino su uso práctico en IS, en el modelaje de sistemas descritos con estados y transiciones y en aplicaciones de lenguajes formales.

Temas
• Conceptos básicos de lenguajes formales
o Definición
o Gramáticas / BNF
• Máquinas de Turing
o Definición, fundamentos
• Autómatas
o Estados, transiciones
o Autómatas determinísticos, no determinísticos
o Modelaje con autómatas
o Autómatas finitos / Relación con lenguajes regulares
o Autómatas de pila / Relación con lenguajes libres de contexto
• Semántica de lenguajes
• Herramientas de análisis sintáctico
o Cómo se utilizan o Limitaciones

Bibliografía Adicional

Introducción a la Teoría de Autómatas, Lenguajes y Computación. 2da Ed. John Hopcroft, Alfred Aho, Rajeev Motwani. Editorial Pearson. (Está en la biblioteca de la UCO)
(Altamente Recomendado!) El cuaderno de Compiladores de álgun estudiante que haya asistido a mi materia (a partir del 1er Semestre del 2002). Los dos únicos temas que tendrían que reforzar son el de las Máguinas de Turing, y los Autómatas de Pila; los cuales, por razones de tiempo, no se alcanzan a ver.

Descripción del Curso

Este curso difiere de aquellos cursos "normales" ya que no sólo se da un descripción teórica de los conceptos subyacentes en el funcionamiento y diseño de un compilador, sino que también usted tendrá la oportunidad de escribir un compilador para un subconjunto representativo de las principales características de los lenguajes de programación de alto nivel (y en español !!!). Este subconjunto está relacionado en el Apéndice B del Texto Guía. Por lo tanto, este curso incluirá una cantidad substancial de programación para ver en funcionamiento los conceptos teóricos, y por lo tanto debe poseer conocimientos suficientes en Pascal o C/C++.

Plan del Curso

Texto Guía de la Materia

Texto Guía de Compiladores - Por: Mario Zuluaga Tobón

Debido a que existe muy poca literatura en español acerca del tema de compiladores, se escribió el presente texto. El objetivo primordial del texto es hacer accesibles, en un lenguaje claro, los conceptos elementales que permitirán al estudiante construir un compilador en español. Este será similar al mostrado en los programas de muestra más abajo.

En este texto se hallan contenidos cada uno de los temas ha ser discutidos en el aula de clase. Por lo tanto, la planeación de la materia corresponderá principalmente a la secuencia de temas reflejada en la tabla de contenido del libro. Obviamente, se harán las ampliaciones que ya están contempladas en el plan del curso.

A continuación se puede tener acceso en línea al primer capítulo y el prólogo del libro, en formato pdf. En el prólogo se encuentra un vistazo general del contenido del libro.

El libro tiene un costo de doce mil pesos ($12.000). En la actualidad, para adquirir el libro se debe dirigir para ello al autor del mismo.

Tabla de Contenido del Libro

PROLOGO	ix

1. CONCEPTOS BASICOS	1
1.1. Qué es un compilador	3
1.2. Fases de un compilador	3
1.3. Un ejemplo completo del proceso de compilación	6
1.4. Temas relacionados	13

2. ANALISIS LEXICO	15
2.1. Implementación de un analizador léxico	18
2.2. Manejo de buffers de entrada	20
2.3. Diagramas de transiciones de estado	23
2.4. Implementación de un diagrama de transiciones.	26
2.5. Tablas de símbolos	26
2.6. Temas relacionados	30

3. ANALISIS SINTACTICO	31
3.1. Gramáticas libres de contexto	33
3.2. Diseño y construcción de un analizador sintáctico descendente	39
3.3. Recursividad por la izquierda y el símbolo épsilon	42
3.4. Análisis sintáctico predictivo no recursivo (tablas sintácticas)	43
3.5. Cómo manejar los errores de compilación	45
3.6. Traducción dirigida por sintaxis	51
3.7. Temas relacionados	55

4. ANALISIS SEMANTICO	57
4.1. Temas relacionados	61

5. GENERACION DE CODIGO INTERMEDIO	63
5.1. Un ejemplo completo	68

6. OPTIMIZACION Y GENERACION DE CODIGO	71

APENDICES	77
Apendice A: Evaluador de expresiones	79
Apendice B: Gramática propuesta para un compilador	94

REFERENCIAS	97

Programas de Muestra

Analizador Léxico en Pascal.
Programa para Evaluación de Expresiones en Pascal, el cual corresponde al Apéndice A del Texto Guía.
Código fuente del programa de Evaluación de Expresiones, el cual corresponde al Apéndice A del Texto Guía.
Programa que construye árboles de expresiones. (Deben también instalar los Runtime DLLs) La idea del programa es que usted le puede suministrar una expresión que incluya operaciones booleanas y/o expresiones aritméticas, tan complejas como se quiera. El programa determina si la expresión está bien escrita o no (análisis sintáctico), y a medida que hace eso va generando (traducción dirigida por sintaxis) un arbol binario que representa la expresión. La última carpeta muestra el recorrido en inorden, postorden y preorden del arbol que equivale a las notaciones infija, postfija y prefija respectivamente. En dicha carpeta también se puede hacer que el programa grafique el árbol. Intenten por ejemplo con la expresión X := (A + B) * (C / D) y vayan aumentándole complejidad, por ejemplo (A + -B / C / D), etc. El programa les permite manipular varias expresiones al tiempo para que puedan observar las diferencias entre las mismas. La vista Ventana>>Cascada es muy útil, además las expresiones no tienen que ser en forma de asignación..
Compilador en Español, en ambiente gráfico, con programas de ejemplo, los cuales se pueden EJECUTAR y DEPURAR en el mismo compilador. (Debe instalar tambien los Runtime DLLs) (Agosto 29/2002 - Versión 3.5 Se adicionó el manejo de rutinas)
Nota: Lo acompañan tres clases de programas de ejemplo que son:
- Archivos program?.txt que son los utilizados para verificar la corrección del compilador realizado. No se deben ejecutar ya que sólo se usan para la verificación del análisis léxico, sintáctico y semántico; y por lo tanto carecen de sentido.
- Archivos gencod?.txt que se utilizan para ejemplificar la generación de código en lo tocante al etiquetado de los saltos y el relleno en retroceso. No se deben ejecutar porque no poseen sentido.
- Archivos como factoria.txt, promedio.txt, etc. que se utilizan para ejemplificar la ejecución usando el concepto de Máquina Abstracta.
Compilador en Español en ambiente D.O.S en Pascal. De manera similar debe quedar el compilador de las personas que decidan hacerlo en ambiente D.O.S., es decir, en Pascal, C/C++, etc.

Talleres y Exámenes en esta clase

Las fechas de examenes y talleres se definirán en clase.