Teoría de compiladores

Compilador Concepto: Programa informático cuya función es transformar código fuente legible para el humano a código de máquina que una CPU puede ejecutar.

Teoría de compiladores. O Teoría de compiladores: En la comunicación hombre-máquina existe una dificultad real: las computadoras operan sobre bits (ceros y unos) y registros y los hombres se entienden por medio de idiomas (lenguaje natural), o utilizan una noción científica determinada por el área de problemas en que trabaja, entre otras vías. Los lenguajes de programación son el vehículo de comunicación entre el hombre y la computadora. Un lenguaje de programación es una técnica estándar de comunicación que permite expresar las instrucciones que han de ser ejecutadas en una computadora. Consiste en un conjunto de reglas sintácticas y semánticas que definen un programa informático. Un programa fuente escrito en un lenguaje de programación necesita pasar por un proceso de conversión al lenguaje de maquina que entiende la computadora, a ese proceso de conversión del programa fuente al lenguaje o código de máquina se le llama proceso de compilación o simplemente compilación. Y al programa capaz de realizar ese proceso se le llama compilador o traductor.

Teoría de compilador

Conceptos básicos

Veamos informalmente algunos conceptos básicos.

• Lenguaje: Conjunto de símbolos y reglas que permiten la comunicación, es decir, trasmitir una idea, un mensaje.

• Léxico (vocabulario): Conjunto de palabras que forman parte de un lenguaje específico.

• Gramática: Agrupa los elementos de forma, estructura y significado que permiten expresarse en un lenguaje determinado.

• Sintaxis: Conjunto de reglas necesarias para construir frases correctas en un lenguaje.

• Semántica: Significado de frases generadas por la sintaxis y el léxico.

• Lenguaje de programación: Conjunto de símbolos y reglas que permiten la comunicación con un computador.

• Lenguaje de alto nivel: Lenguaje que permite la comunicación de un computador mediante símbolos convencionales cercanos a un lenguaje natural.

• Lenguaje de bajo nivel: Similar al lenguaje de máquina con pequeñas modificaciones nemotécnicas que facilitan su uso, por ejemplo el lenguaje ensamblador.

Lenguaje de Maquina: Combinación de dígitos binarios mediante los cuales un ordenador funciona.

Compiladores y traductores

• Traductor es un programa que toma como entrada un programa escrito en un lenguaje de programación (lenguaje fuente) y produce como salida un programa en otro lenguaje (lenguaje objeto). El traductor se escribe en un lenguaje denominado lenguaje de implementación.

Cuando el lenguaje fuente es de alto nivel (Pascal, C++, etc.) y el lenguaje objeto es un lenguaje de bajo nivel o de máquina, al traductor se le denomina compilador.

El lenguaje de implementación puede ser en general cualquier lenguaje de programación, aunque existen lenguajes explícitamente diseñados para escribir compiladores (FSL, CDL, etc.). El criterio fundamental que se sigue para elegir un lenguaje de implementación es: “Este debe minimizar el esfuerzo de implementación y maximizar la calidad del compilador”. Generalmente los traductores se representan a través de una T en la que se incluyen los lenguajes que intervienen en el proceso.

• Intérprete por su parte es un programa que toma el código fuente, lo analiza y a diferencia de los compiladores lo ejecuta directamente, sin generar un lenguaje objeto.

Estructura de un compilador.

El trabajo de un compilador consiste en tomar la cadena fuente del programa, determinar si es sintacticamente válida y, a la vez, generar un programa equivalente en un lenguaje que la computadora entienda. El trabajo del compilador se puede dividir en diferentes partes:

Para un compilador en particular, el orden de los procesos puede variar y, en muchos casos, varios procesos pueden combinarse en una sola fase. En traductores reales el proceso anteriormente descrito no transita en la forma Linealidadlineal en la que aparece en el esquema propuesto en la figura, normalmente el centro del proceso de compilación gira alrededor del Analizador Sintáctico el cual es el encargado de activar cada una de las restantes fases según sea necesario. Los módulos generales son:

1. Análisis lexicológico (scanner)
2. Análisis sintáctico (parser)
3. Análisis semántico
4. Generación de código intermedio
5. Optimización de código intermedio
6. Generación de código ejecutable
7. Tabla de símbolos
8. Gestión de errores

Análisis lexicológico.

La entrada de un compilador es el código de un programa escrito en un lenguaje de programación. Dicho código no es más que una secuencia de símbolos pertenecientes al alfabeto del lenguaje de programación. El analizador lexicológico o scanner se encarga de tomarlos y agruparlos en entidades sintácticas simples o elementales denominadas tokens o lexemas. Las categorías de tokens pueden variar de un lenguaje a otro, pero en general se distinguen las siguientes:

• palabras reservadas
• identificadores
• constantes numéricas y literales
• operadores

A cada token se le asigna una estructura lexicológica consistente en un par de la forma <tipo del token, info>. La primera componente es una categoría sintáctica como “constante”, “identificador”, “operador”, etc., y la segunda componente proporciona información relacionada con el token en particular (valor de la constante, índice del símbolo en la tabla de símbolos, etc.). Podemos afirmar, por lo tanto, que el scanner es un traductor cuya entrada es una cadena de símbolos (programa fuente) y cuya salida es una secuencia de estructuras lexicológicas o tokens.

Operaciones sobre la tabla de símbolos.

Una tarea fundamental en un compilador es la de almacenar los identificadores utilizados en un programa y sus atributos principales, de manera que en cualquier momento pueda conocerse de un identificador, su tipo, alcance, etc., para el caso de los procedimientos, la cantidad y tipo de los parámetros, etc. Esta información se almacena generalmente en una estructura conocida como tabla de símbolos, la cual tiene una entrada para cada identificador y sus atributos. Los tokens que representan constantes o identificadores se almacenan en la tabla de símbolos a medida que van apareciendo.

Ejemplo: 1 a Variable real 2 b Variable real 3 c Variable real 4 7 constante entera

Análisis sintáctico(parsing)

El análisis sintáctico es un proceso en el cual se examina la secuencia de tokens para determinar si el orden de esa secuencia es correcto de acuerdo a ciertas convenciones estructurales (reglas) de la definición sintáctica del lenguaje. La entrada del analizador sintáctico o parser es la secuencia de tokens generada por el scanner. El parser analiza solamente la primera componente de cada token; la segunda componente se utiliza en otros pasos.

Ejemplo: Supongamos existen unas reglas que definen expresión de la forma siguiente: exp -> exp + exp exp -> exp / exp exp -> id exp -> const

Qué resultado se obtendría del proceso de análisis sintáctico de la expresión A + * B? A + * B ⎯scanner ⎯> id1 + * id2 ⎯parser ⎯> Error: No cumple con la especificación sintáctica del lenguaje.

Qué resultado se obtendría del proceso de análisis sintáctico de la expresión A + B * 7? A + B * 7 ⎯scanner ⎯> id1 + id2 * 7 ⎯parser ⎯> Sí, se cumple con la especificación sintáctica del lenguaje.

Es necesario conocer la estructura sintáctica de una secuencia de tokens. Por ejemplo, en una expresión A = B+C*7 en la que las variables A, B y C representan valores reales, la estructura sintáctica de esa expresión debe reflejar el hecho de que B y 7 deben multiplicarse antes de que se realice la suma y luego de hacer todas las operaciones se efectuará la asignación. Para ello, se agrupan los tokens en una estructura en forma de árbol, conocida como árbol sintáctico.

Ejemplo: Veamos el árbol sintáctico para la secuencia: id1 = id2 + id3 * 7 Esta secuencia conduce a que se realicen las siguientes operaciones: 1. id3 se multiplique con 7 2. el resultado de 1 se sume con id2 3. el resultado de 2 se almacene en id1

En el árbol sintáctico anterior los descendientes directos de cada nodo representan las acciones a realizar y los valores para los cuales deben realizarse las acciones.

Análisis semántico.

En el análisis semántico se detectan errores relacionados con la validez del programa. Se puede decir que estos errores son de tipo sintáctico-semántico, pero no pueden ser detectados por el analizador sintáctico, ya que se relacionan con interdependencias entre las diferentes partes de un programa que no son reflejadas en un análisis gramatical. El analizador semántico recibe la información resultado del análisis sintáctico que puede ser un árbol jerárquico con la información relativa a la organización de los tokens en la instrucción que se esta analizando. Ejemplo de errores que pueden ser detectados en el proceso de análisis semántico son los casos de compatibilidad entre la declaración de un identificador y su uso (chequeo de tipos), la concordancia entre la definición de una función y su activación o llamada, etc.

Ejemplo: Retomemos el ejemplo anterior: id1 = id2 + id3 * 7 Durante el análisis semántico de un lenguaje de fuerte chequeo de tipos el árbol sintáctico debe ser modificado para reflejar el análisis de los tipos de los datos. Note que haciendo un chequeo de tipos la constante 7, al ser una constante entera debe ser convertida a real para poder ser operada y las demás variables no tienen dificultad alguna para ser utilizadas al ser todas reales.

Gestión e información de errores.

Si los compiladores tuvieran que procesar solamente programas correctos, su diseño e implementación se simplificaría en buena medida. Pero los programadores escriben programas incorrectos frecuentemente, y un buen compilador debe ayudar al programador a localizar e identificar los errores. Los errores en un programa pueden clasificarse en 4 grandes grupos: - lexicológicos (escribir mal un número, un símbolo no permitido, etc.) - sintácticos (expresión aritmética con paréntesis no balanceados) - semánticos (aplicar un operador a un operando incompatible) - lógicos o de programación (ciclo infinito) El analizador léxico detecta errores cuando los caracteres que restan de la entrada no forman ningún token válido en el lenguaje. Los errores referentes a que los tokens no cumplan con las reglas estructurales (sintaxis) del lenguaje se detectan en la fase de análisis sintáctico. Durante el análisis semántico el compilador trata de detectar estructuras que tengan una sintaxis correcta pero incorrecta semánticamente de acuerdo a las operaciones involucradas. Ejemplo si tratamos de sumar dos identificadores, uno el nombre de un arreglo y el otro el nombre de un procedimiento. Las fases de análisis sintáctico y semántico manejan usualmente la mayor parte de los errores detectables por el compilador. Como podemos apreciar en cada fase del proceso de compilación se pueden encontrar errores. Si embargo, después de detectado el error, la fase puede tratar el error, de manera que el compilador pueda continuar, permitiendo así que se puedan detectar errores posteriores. Un compilador que se detenga cuando encuentre el primer error no es muy eficaz. El tratamiento de los errores durante el proceso de compilación (en cualquiera de sus fases) debe cumplir al menos los requisitos siguientes: - reportar la presencia de los errores clara y precisamente - recuperarse de los errores lo suficientemente rápido como para ser capaz de detectar los errores siguientes - no demorar significativamente el procesamiento de los programas correctos.

Generación de código intermedio.

Después del análisis sintáctico y semántico muchos compiladores generan una representación explícita intermedia del código fuente. Dicha representación puede verse como la representación de un programa para una máquina abstracta. Ejemplo: MSIL, Java bytecode, Notación de cuádruplos, Notación polaca, etc. El código intermedio debe tener dos características muy importantes: debe ser fácil de producir y fácil de traducir al programa objeto. El árbol creado por el analizador semántico se utiliza para generar la traducción del programa fuente y de esta forma lograr la interpretación de las acciones asociadas a la sentencia o sentencias en curso. La traducción como se había mencionado puede ser a lenguaje de máquina, o a un lenguaje intermedio, como el lenguaje ensamblador. Un método elegante y efectivo para generar el código intermedio a partir del árbol sintáctico es el denominado Traducción Sintáctica Directa. A cada nodo n se le asocia un código intermedio C(n). El código del nodo n se construye concatenando el código de sus descendientes. Luego, la traducción se hace de abajo hacia arriba.

Optimización del código intermedio.

La fase de optimización se efectúa con el objetivo de mejorar la eficiencia del código intermedio. Algunas optimizaciones resultan triviales. Por ejemplo, un código semejante al generado en la tabla anterior, puede representarse en solo dos instrucciones.

temp1 = id3 * 7.0 id1 = id2 + temp1

El compilador puede deducir que la operación EntToReal(7) puede realizarse de una vez en la fase compilación así podemos eliminar dicha instrucción sustituyendo por 7.0 directamente. Además temp3 se usa solo una vez para trasmitir su valor a id1. De esa forma no hay ninguna objeción en sustituir id1 por temp3.

Generación del código objeto.

La fase final de un compilador es la de generación del código objeto, consistente en código máquina o código ensamblador. Lo primero es seleccionar localizaciones de memoria para cada variable usada en el programa. Las instrucciones intermedias se traducen a secuencias de instrucciones en código maquina que realicen la misma operación. Un aspecto crucial es la asignación de las variables a registros.

Ejemplo: Las dos instrucciones obtenidas en son traducidas instrucciones en ensamblador.

MOVF id3, R2 MULF #7.0, R2 MOVF id2, R1 ADDF R2, R1 MOVF R1, id1

Los primeros dos operados, determinan el origen y el destino respectivamente. El sufijo F de cada instrucción indica que se esta trabajando con números en coma flotante (reales). Este código mueve el contenido de la dirección id3 al registro 2, seguidamente lo multiplica por el número 7.0. El símbolo # indica que 7.0 debe ser tratado como una constante. La tercera instrucción mueve el contenido de id2 al registro 1 y lo adiciona al valor calculado previamente que esta almacenado en el registro 2. Finalmente el valor calculado en el registro 1 es movido a la dirección determinada por id1.

Representación de lenguajes.

En general existen dos esquemas diferentes para definir un Lenguaje, los cuales se conocen como esquema generador y esquema reconocedor. En el caso de los esquemas generadores se trata de un mecanismo que nos permite “generar” las diferentes sentencias del lenguaje. En caso de los esquemas reconocedores se trata de un mecanismo que nos permite reconocer o verificar si cierta sentencia pertenece o no a un lenguaje. Si un Lenguaje posee un número finito de cadenas, puede ser definido simplemente listando sus cadenas, pero ¿Cómo proceder para definir Lenguajes con un número infinito de Cadenas? Para definir un lenguaje se puede utilizar una Gramática (esquema generador) o podemos utilizar Autómatas Finitos (esquema reconocedor).

Definiciones Básicas.

Antes de abordar el concepto de lenguaje, veremos un conjunto de definiciones básicas relacionadas.

• Alfabeto (Σ): Se entiende por alfabeto un conjunto arbitrario, finito y no vacío, de símbolos. Entre los alfabetos más comunes podemos mencionar el alfabeto binario {0, 1}, el alfabeto latino {a, b, c, d, e, f, g, …}, etc.
• Cadena: Una cadena es una secuencia de símbolos de cierto alfabeto colocados uno a continuación del otro.

11001: constituye una cadena sobre el alfabeto {0, 1}. abcd: constituye una cadena sobre el alfabeto de las letras latinas.

• Cadena Vacía: Una cadena vacía no es más que una cadena sin elementos, la cadena vacía se denota por e.

Notación: En lo que sigue asumiremos el siguiente convenio para denotar cadenas: a, b, c, d, … representan símbolos. y, u, v, w, … representan cadenas an =aa…a n veces a0 = e

Definición Formal de Cadena:

Una cadena sobre un determinado alfabeto Σ se define como sigue:

1. e (cadena vacía) es una cadena sobre Σ.
2. Si x es una cadena sobre Σ, y a ∈ Σ entonces xa es una cadena sobre Σ, para todo a ∈ Σ.
3. Cualquier otra cadena sobre Σ puede obtenerse, aplicando 1 y 2.

Concatenación de Cadenas:

Si x y y son cadenas sobre Σ, entonces xy es una cadena sobre Σ, que se denomina concatenación de x y y.

Reverso de una Cadena:

El reverso de una cadena x se denota xR, y es la cadena que se obtiene escribiendo los símbolos de x en sentido inverso.

Prefijos y Sufijos de una Cadena:

Sean x, y, z cadenas sobre Σ. Entonces x es un prefijo de la cadena xy y y es un sufijo de la cadena xy. Además y es una subcadena de la cadena xyz. Si x ≠ y y x es un prefijo de y entonces se dice que x es un prefijo propio. Análogamente se puede definir el concepto de sufijo propio.

Longitud de una Cadena:

La longitud de una cadena es el número de símbolos que la integran. Así decimos que la longitud de la cadena abc es 3, lo cual se denota en la forma siguiente: ⎟ abc ⎟ = 3 Obviamente se tiene que ⎟ e ⎟ = 0.

Lenguaje:

Un lenguaje sobre Σ es un conjunto de cadenas sobre dicho alfabeto que obedece una cierta regla de formación.

Clausura de un Alfabeto:

El conjunto Σ* denota todas las cadenas sobre Σ, incluyendo la cadena vacía, este conjunto se denomina Clausura de Σ. Por ejemplo, si Σ = {0,1} entonces Σ* = {e, 0, 1, 00, 01, 10, 11, 001,…} Resulta evidente que si L es un cierto lenguaje sobre Σ, entonces L ⊆ Σ*. El conjunto Σ+ se denomina Clausura Positiva de Σ y se define como: Σ+ = Σ* - e

Operaciones sobre Lenguajes:

Algunas de las operaciones anteriores sobre cadenas pueden ser generalizadas a los lenguajes, así podemos definir la concatenación o producto de lenguajes en la forma siguiente: Sea L1 un lenguajes sobre Σ1 y L2 un lenguaje sobre Σ2, entonces el lenguaje L1L2 se denomina concatenación o producto de los lenguajes L1 y L2 y se define como sigue: En forma análoga puede definirse la Clausura de un Lenguaje en la forma siguiente: L0 = {e} Ln = L Ln-1 para n ≥ 1 L* = ∪ Ln para n ≥ 0 Ejemplo: (a) Ponga un ejemplo de cadena que pertenezca al lenguaje L = { 0 n1n | n>=1 } Respuestas correctas: 01, 0011, 000111, 00001111, … Respuestas incorrectas: 0, 1, 001, 10, 1100, 011, …

Concepto de gramática.

La gramática es un ente o modelo matemático que permite especificar un lenguaje, es decir, es el conjunto de reglas capaces de generar todas las posibilidades combinatorias de ese lenguaje, y sólo las de dicho lenguaje, ya sea éste un lenguaje formal o un lenguaje natural. Los objetivos de una gramática son:

• Definir si una sentencia pertenece o no al un lenguaje.
• Describir estructuralmente las sentencias del lenguaje.

En la definición formal de una Gramática se utilizan dos conjuntos disjuntos de símbolos: N: Conjunto de símbolos no terminales (los cuales nos permiten representar combinaciones de símbolos). Σ: Conjunto de símbolos terminales que se corresponde con el concepto de alfabeto anteriormente estudiado. El centro de una gramática lo constituye un conjunto de “reglas de producción” (P) o reglas de formación de cadenas, las cuales están formadas por elementos de la relación: (N ∪ Σ )* N (N ∪ Σ )* → (N ∪ Σ )* Definición: Una gramática es un cuádruplo G = { N, Σ, P, S } donde: N: Conjunto de símbolos no terminales. Σ: Conjunto de símbolos terminales. P: Conjunto de Reglas de Producción. S: Axioma o símbolo distinguido (S ∈ N)

Definiciones relacionadas con el concepto de Gramáticas

Forma Sentencial: Una forma sentencial en una gramática se define en forma recursiva como sigue: Sea G = { N, Σ, P, S } una gramática, entonces:

1. S es una forma sentencial.
2. Si αβλ es una forma sentencial y β→δ ∈ P entonces αδλ es una forma sentencial.

Sentencia: Una forma sentencial que solo contenga terminales se denomina sentencia. Derivación: Sea G = { N, Σ, P, S } una gramática, la relación ⇒ (deriva directamente) se define como sigue: Si αβλ ∈ ( N ∪ Σ )+ y β → δ ∈ P entonces αβλ ⇒ αδλ. La derivación de longitud k que denotamos significa que si , entonces existe una secuencia de cadenas a = a0, a1,…,ak=β tal que tal que a = a0 ⇒ a1 ⇒ … ⇒ ak = β. La relación (deriva en forma no trivial) se define como la clausura positiva de ⇒, equivalente a con k > 0 La relación ⇒ se define como la clausura de ⇒ , equivalente a con k ≥ 0.

Clasificación de Chomsky.

De acuerdo con lo que hemos visto, toda gramática genera un único lenguaje, pero distintas gramáticas pueden generar el mismo lenguaje. Por ejemplo, el lenguaje generado en el ejemplo 2.3 es igual al generado por la gramática del siguiente ejemplo. Ejemplo : G0 = ( { E, T, F }, { a, +, *, (, ) }, P, E ) Donde: Podríamos pensar en clasificar las gramáticas por el lenguaje que generan, por este motivo hacemos la siguiente definición. Definición: Dos gramáticas se dicen débilmente equivalentes si generan el mismo lenguaje. Sin embargo, al hacer esta clasificación nos encontramos con que el problema de saber si dos gramáticas generan el mismo lenguaje es indecible. No existe ningún algoritmo que acepte como entrada dos gramáticas y nos diga (la salida del algoritmo) si generan o no el mismo lenguaje. De esta forma, tenemos que pensar en clasificaciones basadas en la forma de la gramática, más que en la naturaleza del lenguaje que generan. La siguiente clasificación se conoce como jerarquía de Chomsky y sigue esta dirección. Sea G = ( N, Σ, P, S) una gramática:

1. Si cada producción en P es de la forma A → xB ó A → x con A, B ∈ N y x ∈ Σ* o de la forma A→ Bx ó A → x con A, B ∈ N y x ∈ Σ* entonces la gramática G se denomina Regular Derecha o Regular la izquierda respectivamente, o de forma general Gramática Regular.
2. Si cada producción en P es de la forma A → α donde A ∈ N y α ∈ (N ∪ Σ)∗ entonces la gramática G se denomina de Libre Contexto.
3. Si cada producción en P es de la forma α → β donde |α| ≤ |β| y α contiene al menos un no terminal, entonces la gramática G se denomina Dependiente del Contexto.
4. Si una gramática G no cumple las restricciones anteriores se denomina Gramática sin Restricciones.

Expresiones Regulares.

Hasta ahora hemos visto un mecanismo muy poderoso para la representación de lenguajes, como son las gramáticas. Existe otro mecanismo para la representación de lenguajes, el cual, aunque no es tan general como las gramáticas, brinda grandes facilidades para la representación de ciertos lenguajes muy simples. En particular veremos más adelante que este mecanismo es muy útil para representar aquella parte de un lenguaje que es analizable por un analizador lexicográfico, es decir, palabras reservadas, identificadores, etc. Este nuevo mecanismo de representación de lenguajes se conoce con el nombre de Expresiones Regulares. Una expresión regular sobre un cierto alfabeto Σ puede ser definida en la forma siguiente:

1. e es una Expresión Regular sobre Σ. O sea, la cadena vacía es una expresión regular sobre cualquier alfabeto.
2. Si a es un símbolo perteneciente a Σ entonces a es una expresión regular que denota al conjunto o lenguaje {a}, o sea, el conjunto que contiene al elemento a.
3. Si r y s son expresiones regulares que denotan los lenguajes L(r) y L(s) entonces:

A) r | s, es una expresión regular que denota el lenguaje L(r) ∪ L(s). B) r. s, es una expresión que denota el lenguaje L(r). L(s) C) r* es una expresión regular que denota el lenguaje (L (r))* D) r+ es una expresión regular que denota el lenguaje (L (r))+

Esquemas reconocedores de lenguajes formales. Autómatas finitos.

Esquemas reconocedores.

Los Lenguajes, en general no finitos, pueden ser representados mediante esquemas generadores (expresiones regulares y gramáticas) o de esquemas reconocedores. A continuación analizaremos cómo representar lenguajes utilizando éste último tipo de esquema. Un reconocedor para el lenguaje L es un programa (o mecanismo) que toma como entrada una cadena x y responde “si” si x pertenece al lenguaje L o “no”, si no pertenece. De manera general un reconocedor lo podemos representar gráficamente de la siguiente forma:

Figura 1.1 Esquema general de un reconocedor

Cinta de entrada: Es una secuencia de símbolos ai que pertenecen a un alfabeto Σ y constituyen la cadena a reconocer. Usualmente la secuencia puede terminar con un símbolo especial cuya función es la de marcar el fin de la cadena.

Cabezal de lectura: Mecanismo que le permite al reconocedor obtener los símbolos de la cadena de entrada. El mismo puede moverse a la izquierda, a la derecha o quedarse estacionario en un momento determinado.

Control de estado: Centro del reconocedor. A través de un conjunto finito de estados y una función de transición se describe cómo se comporta el reconocedor ante todos los símbolos del alfabeto del lenguaje.

Memoria: Dispositivo para almacenar información. La información está constituida por símbolos pertenecientes a un alfabeto de memoria y son utilizados por el reconocedor durante el proceso de análisis de una cadena. Este dispositivo se organiza con cierta estructura. Existe una gran variedad de reconocedores:

1. Autómatas finitos.
2. Autómatas de Pila.
3. Autómatas de frontera lineal
4. Máquina de Turing.

Los reconocedores que analizaremos en este curso, dada su relación con la fase de análisis léxico, y el reconocimiento de los tokens de un lenguaje, son los autómatas finitos.

Autómatas finitos.

Un autómata finito o máquina de estado finito es una herramienta abstracta que se utiliza para reconocer un determinado lenguaje regular. Es un modelo matemático de un sistema que recibe una cadena constituida por caracteres de cierto alfabeto y determina si esa cadena pertenece al lenguaje que el autómata reconoce. Formalmente:

Definición 1.

Autómata Finito. Formalmente uma autómata finito está definido por una 5-tupla N. N = ( S, Σ, δ, S0, F ). Donde: S: Es un conjunto finito de estados. Σ: Alfabeto del lenguaje. Conjunto de símbolos de entrada del autómata. δ: Función de transición definida como: δ: S x Σ ∪ { ∈ } → P(S). S0: Es el estado inicial del autómata S0 ∈ S. F: Es el conjunto de estados finales o de aceptación del autómata. F ⊆ S.

Autómatas finitos determinista (AFD)

Un AFD o autómata finito determinista es aquel autómata finito cuyo estado de llegada está unívocamente determinado por el estado de salida y el carácter leído por el autómata. Un AFD es un caso particular de AF en el cual se cumple:

1. No existen e-transiciones.
2. Para cualquier estado si y cualquier símbolo a ∈ Σ, existe al máximo una transición que salga de si.

Un AFD se denomina completo cuando tiene una transición por cada estado y cada carácter del alfabeto. Si no cumple esta condición se lo denomina incompleto. La gran ventaja que aportan los Autómatas Finitos Deterministas viene dada por la simplicidad del mecanismo que simule el reconocimiento de una cadena.

Autómatas finitos no deterministas (AFND)

Un autómata finito no determinista (AFND) es un autómata finito que presenta cero, una o más transiciones por el mismo carácter del alfabeto y se clasifican dos grupos: con e-transiciones y sin e-transiciones dependiendo de la existencia o no de una o más transiciones sin que el autómata lea el próximo carácter de la cadena que está analizando.

Construcción de autómatas finitos a partir de expresiones regulares

Construir una expresión regular además de ser un proceso muy intuitivo constituye una forma cómoda de representar los lenguajes regulares. Pero tienen una gran desventaja y es que se hace inservible cuando queremos determinar computacionalmente si una determinada cadena pertenece o no al lenguaje representado por dicha expresión regular. Habría que generar todas las cadenas del lenguaje, o al menos una gran parte de ellas, lo que puede ser un proceso infinito. Los lenguajes descriptos por expresiones regulares son los mismos lenguajes reconocidos por los autómatas finitos. Como se vio anteriormente una de las grandes ventajas de los autómatas finitos deterministas vienes dada por la simplicidad del mecanismo que simula el reconocimiento de una cadena. Por otro lado existe un algoritmo para convertir una expresión regular en el autómata finito no determinístico correspondiente. El algoritmo, llamado construcción de Thompson, construye a partir de la expresión regular un AFND con transiciones vacías, es decir un autómata que contiene arcos rotulados con e. Luego este autómata con transiciones vacías se puede convertir en un autómata finito sin transiciones vacías que reconoce el mismo lenguaje.

Análisis Léxico

Funcionamiento de un analizador léxico

El analizador léxico es la primera fase de un compilador. Su función principal es leer los caracteres de entrada y producir como salida una secuencia de tokens que el parser luego utiliza en su análisis sintáctico. La interacción entre ambos componentes (analizador léxico y analizador sintáctico), representada en la Fig. 1, básicamente es de la siguiente forma: Ante un pedido de un token (mensaje “proximo token”), el analizador léxico lee una secuencia de caracteres del código fuente del programa hasta identificar un token, el cual es retornado como respuesta al pedido del analizador sintáctico.

Especificación de un Analizador Léxico

Antes de implementar un Analizador Léxico para un lenguaje determinado, es necesario diseñar su especificación. Para ello hay que identificar primeramente la colección de tokens que compone el lenguaje. Cada token debe estar especificado mediante algún esquema generador o un esquema reconocedor, preferiblemente expresiones regulares. Luego es necesario Especificar el Diagrama de Transición del Analizador Léxico. Cada uno de estos pasos será explicado en detalle, tomando como base un ejemplo.

Conceptos Preliminares: Tokens, Patrones y Lexemas.

Cuando se aborda el tema de la especificación de un Analizador Léxico, se hace mención a términos como token, patrón y lexema, con sus respectivos significados. Observemos el ejemplo correspondiente a la Fig. 2. En general existe un conjunto de cadenas para las cuales se produce el mismo token como salida. Este conjunto de cadenas se describe mediante una regla llamada patrón y está asociada a un token en específico. Un lexema es una secuencia de caracteres del programa fuente que “matchea” con un patrón correspondiente a un token. Por ejemplo, en la siguiente sentencia correspondiente al lenguaje de programación Pascal const pi = 3.1416; la subcadena pi es un lexema para el token “identificador”. Los lexemas que matchean con un patrón de un token representan cadenas del programa fuente que pueden ser manejadas en conjunto como una unidad léxica. Dicha unidad léxica la representa el token, el cual, en las siguientes fases del proceso de compilación, constituirá un símbolo terminal en la gramática generadora del lenguaje. En la mayoría de los lenguajes de programación constituyen tokens los siguientes conjuntos:

• palabras reservadas: cadenas predeterminadas por el lenguaje las cuales no se pueden usar como identificadores.
• operadores: Los cuales a su vez podrían dividirse en 4 tokens aritméticos, relacionales, lógicos, y de asignación.
• identificadores.
• constantes o literales: Los cuales a su vez podría dividirse en tres tokens, literales reales, literales enteras y literales de cadena.
• símbolos de puntuación: Aquí se incluyen los puntos, las comas, los paréntesis, las llaves, etc. Pueden dividirse en varios tokens, todo depende del significado sintáctico que tenga un determinado símbolo de puntuación en el lenguaje.

Los patrones pueden especificarse de varias formas. En la Fig. 2, el patrón del token const es la propia cadena const. El patrón del token relation es el conjunto de operadores relacionales de C. Para describir patrones para tokens más complejos se usa cualquier esquema generador o reconocedor de lenguajes. Generalmente se describen mediante expresiones regulares, aunque en ocasiones es conveniente también describirlos mediante un autómata finito.

Atributos de un token

Para cada token identificado por el analizador léxico, es necesario almacenar otras informaciones como el lexema, el número de línea de su primera aparición y otros datos que dependen del tipo de token (si el identificador es de un arreglo o de una función, en cada caso almacenar el límite o la cantidad y los tipos de los parámetros, etc). Dichas informaciones son necesarias para fases posteriores del proceso de compilación y son almacenadas en la tabla de símbolos del compilador. Es por ello que usualmente un token tiene un solo atributo, el cual es un apuntador a la entrada de la tabla de símbolos donde está almacenada toda la información referente al token. Por ejemplo, los tokens identificados en la siguiente sentencia de Fortrán E = M * C ** 2 se pueden escribir como una secuencia de pares: <id, puntero a la entrada en la tabla de símbolos para E> <asig_op, > <id, puntero a la entrada en la tabla de símbolos para M> <mult_op, > <id, puntero a la entrada en la tabla de símbolos para C> <exp_op, > <num, puntero a la entrada en la tabla de símbolos del ‘2’>

Note que en algunos pares no es necesario el valor del apuntador, pues la primera componente del par es suficiente para identificar el lexema. En este pequeño ejemplo, para el token num, el Compilador puede almacenar en la tabla de símbolos la cadena que forma el número y el puntero hacia esa entrada sería el atributo del token num.

Ver además

• Herramientas para generar compiladores

Fuentes

Materiales de apoyo Universidad de las ciencias Informáticas
About.com C/C++/C#
Alegasa - Definición de Compilador