10-11/02 Enero - Junio 2011
ESCOM IPN - ISC Plan 2003
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
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.
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.
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".
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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).
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.
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.