Unidad de Aprendizaje
"Compiladores"

10-11/02 Enero - Junio 2011
ESCOM IPN  -  ISC Plan 2003


Documentos Utiles

Libro: Compiladores, principios, herramientas y técnicas (Dragon book) *117MB Aprox.
Formato de referencias IEEE

Prácticas


Clases


Clase 01 "Presentación del curso y Tareas 01 & 02"

Presentación del curso de Compiladores (Unidades tematicas, formato de las evaluaciónes, formato de tareas y practicas así como acuerdos del grupo) y requisitos de las Tarea 01 y 02

Clase 02 "Lenguajes de programación y compiladores"

Para poder darle instrucciones a una computadora es necesario el uso de un lenguaje de programación y de programas que traduzcan instrucciones escritas bajo este lenguaje a un lenguaje de nivel máquina. La cantidad de lenguajes de programación existentes en la actualidad es grande, y la abstracción de estos es la que permite decidir cuál de ellos usar según el problema y paradigma a usar.

Clase 03 "Anatomía de un compilador"

El proceso de compilación se compone de dos etapas, el análisis y la síntesis. La parte del análisis divide el programa fuente en sus elementos componentes y crea una representación intermedia del programa fuente. La etapa de síntesis construye el programa objeto deseado a partir de la representación intermedia del programa fuente.

Clase 04 "Como se crea un programa ejecutable de un lenguaje compilado"

Generalmente el término "compilar" para un programador hace referencia a la generación de un archivo ejecutable (si se trata de un lenguaje compilado). Aunque en realidad implique más que solo "compilar".

Clase 05 "Análisis léxico I (Introducción al análisis léxico y manejo de buffers)"

En el ámbito de compiladores, el análisis léxico es la parte que tiene contacto directo con el código fuente, el analizador léxico hace las funciones, a la vez, de preprocesador y de scanner o lexer. Como primera etapa para una implementación adecuada de un scanner, el manejo de búferes tiene la intención de mejorar el rendimiento de esta primera fase donde se hace necesario el acceso al archivo con el código fuente de entrada.

Clase 06 "Análisis léxico II (Alfabetos, símbolos y cadenas)

Antes de lograr implementar el análisis léxico, es necesario definir conceptos que lográn poder implementar un manejo y reconocimiento de cadenas de manera adecuada.

Clase 07 "Análisis léxico III (Lenguajes regulares)"

Los lenguajes regulares se llaman así porque sus palabras contienen “regularidades” o repeticiones de los mismos componentes. Como ya se sabe el analizador léxico (scanner) se encarga de dividir el programa fuente en un conjunto de unidades sintácticas (tokens).Para llevar a cabo esta división del programa en unidades sintácticas, el analizador léxico utiliza un subconjunto de las reglas de la gramática del lenguaje en el que está escrito el programa que se va a compilar. Este subconjunto de reglas corresponde a un lenguaje regular, i.e. un lenguaje definido por expresiones regulares.

Clase 08 "Análisis léxico IV (Expresiones regulares y Ejercicios 01)"

Las expresiones regulares se construyen en forma recursiva a partir de las expresiones regulares más pequeñas. Cada expresión regular r denota un lenguaje L(r), el cual también se define de forma recursiva, a partir de lenguajes denotados por las subexpresiones de r.

Clase 09 "Análisis léxico V (Autómatas finitos & Mapas Conceptuales 01 y 02)"

Si la información se codifica en cadenas de símbolos, podemos con un autómata manipular cadenas de símbolos que se le presentan a su entrada, produciendo otras tiras o cadenas de símbolos a su salida. Un autómata finito recibe los símbolos de entrada, uno detrás de otro, el símbolo de salida que en un instante determinado produce un autómata, no sólo depende del último símbolo recibido a la entrada, sino de toda la secuencia o cadena, que ha recibido hasta ese instante.

Clase 10 "Análisis léxico VI (AFD, AFND & Nomenclatura de Thompson)"

Un autómata finito puede ser de dos tipos, según el comportamiento de la función de transición, (determinista o no), por otro lado la construcción de Thompson es una herramienta que permite construir fácilmente un autómata no determinista que sea capaz de reconocer un lenguaje regular dado.

Clase 11 "Análisis léxico VII (Conversión de AFN a AFD y Ejercicios 03)"

Un autómata finito no determinista presenta probelmas al implementarse debido al indeterminismo de ciertos estados ante cierta entrada, por lo que es necesario lograr una transformación a su correspondiente representación determinista para lograr una implementación práctica.

Clase 12 "La herramienta LEX"

Exposiciónes: 6CV6

Lex es un programa para generar analizadores léxicos (en inglés scanners o lexers). Lex se utiliza comúnmente con el programa yacc que se utiliza para generar análisis sintáctico.

Clase 13 "Lenguajes y gramáticas I (Definición de lenguaje y gramática)"

La Gramática es el estudio de las reglas y principios que regulan el uso de las lenguas y la organización de las palabras dentro de una oración. También se denomina así al conjunto de reglas y principios que gobiernan el uso de un lenguaje muy determinado; así, cada lenguaje tiene su propia gramática.

Clase 14 "Lenguajes y gramáticas II (Jerarquía de las gramáticas y ejercicios 04)"

En 1950 el lingüista norteamericano Avram Noam Chomsky introdujo la teoría de las gramáticas transformacionales o teoría de lenguajes formales, que convirtió la lingüística en una ciencia y proporcionó una herramienta que no sólo podía aplicarse a los lenguajes naturales, sino que facilitaba el estudio y la formalización de los lenguajes para la programación de computadoras. En función de la forma de sus producciones, se puede caracterizar qué tan compleja es una gramática formal.

Clase 15 "Lenguajes y gramáticas III (Árbol de derivación y ambigüedad de las gramáticas & Mapa conceptual 03 )"

Un árbol de derivación permite mostrar gráficamente cómo se puede derivar cualquier cadena de un lenguaje a partir del símbolo inicial de una gramática que genera ese lenguaje. Al árbol de derivación también se le llama árbol de análisis o árbol de análisis gramatical o árbol de análisis sintáctico.

Clase 16 "Análisis sintáctico I (Introducción al análisis sintáctico y gramáticas libres de contexto & Ejercicios 05)"

El análisis sintáctico o parsing utiliza los primeros componentes de los tokens producidos por el analizador léxico para crear una representación intermedia en forma de árbol que describa la estructura gramatical del flujo de tokens (sintaxis). Las gramáticas libres de contexto permiten describir la mayoría de los lenguajes de programación, de hecho, la sintaxis de la mayoría de lenguajes de programación está definida mediante gramáticas libres de contexto.

Clase 17 "Análisis sintáctico II (Gramáticas limpias y bien formadas & tipos de análisis sintáctico)"

Exposiciónes: La herramienta YACC 6CV1, 6CV6

Una gramática bien formada permite el correcto análisis y detección a la hora de ser impuesta en algún lenguaje. Por ello es necesario verificar la correcta escritura y reglas de producción posibles en una grámatica.

Clase 18 "Análisis sintáctico III (Análisis descendente)"

En el análisis sintáctico descendente se parte del símbolo de inicio de la gramática que se coloca en la raíz y se va construyendo el árbol desde arriba hacia abajo, hasta las hojas, eligiendo la derivación que da lugar a una concordancia con la cadena de entrada. Se basa en la idea de que predice una derivación y establece una concordancia con el símbolo de la entrada (predict/match). 

Clase 19, 20 y 21"Análisis sintáctico IV (Análisis LL(1) y Ejercicios LL(1))"

El análisis sintáctico LL es un análisis sintáctico descendente, para una  gramática libre de contexto. En éste tipo de análisis las entradas son de izquierda a derecha, y la construcción de las derivaciones son por izquierda. La clase de gramática que es analizable por éste método es conocido como gramática LL. Un analizador LL es llamado un analizador LL (k) si usa k tokens cuando el analizador ve hacia delante de la sentencia. Las gramáticas LL(1) permiten construir de forma automática un analizador determinista descendente con tan sólo examinar en cada momento el símbolo actual de la cadena de entrada (símbolo de pre análisis) para saber qué producción aplicar; la gramática LL(1), aunque es bastante restrictiva, es muy popular ya que de los analizadores LL correspondientes sólo necesita ver el siguiente token para hacer el análisis de sus decisiones. Lenguajes mal diseñados usualmente suelen tener gramáticas con un alto nivel de k, y requieren un esfuerzo considerable a analizar.

Clase 22, 23 y 24 "Análisis sintáctico V (Análisis SLR y Ejercicios SLR)"

El análisis SLR o LR(0) proviene del inglés Simple LR,  es el más elemental de los analizadores ascendentes. El principal objetivo es construir un autómata finito determinístico para reconocer los prefijos de la cadena, esos elementos se agrupan por estados. Es el método ascendente que tiene un menor número de gramáticas para reconocer, en contraste con los otros métodos. Si existe una confusión en la tabla de análisis, al ser en el mismo estado una “reducción” y un “desplazamiento” no se puede realizar por ese método.