Compiladores

Autómata finito: Es un vector que tiene un conjunto de entradas finitas denominadas con la letra i un conjuntos finito de estados (no vacíos) un delta denominado función de transición y un conjunto universal de todos los estados.

Existen dos tipos autómatas finitos, los cuales son:

Autómata finito determinista: es un autómata finito que además es un sistema determinista; es decir, para cada estado en que se encuentre el autómata, y con cualquier símbolo del alfabeto leído, existe siempre a lo más una transición posible desde ese estado y con ese símbolo.



Autómata finito no determinista: Una extensión de los AFD’S es la de permitir que de cada estado o nodo del diagrama de estados salga un número de flechas mayor o menor que |Σ|. Así se puede permitir que falte la flecha correspondiente a alguno de los símbolos del alfabeto, o bien que haya varias flechas que salgan de un solo nodo con la misma etiqueta. Inclusive se permite que las transiciones tengan como etiqueta palabras de varias letras o hasta la palabra vacía.

Definición. Un autómata finito no determinista es un quíntuplo (K, Σ, Δ, s, F), donde K, Σ, s y F tienen el mismo significado para el caso de los AFD y Δ, llamada la relación de transición, es un subconjunto finito K X Σ* X K.

Por razones de diseño, la construcción del compilador se divide en varios pasos o fases. Se divide en dos procesos genéricos:

Análisis: El cual hace referencia a la escritura correcta del programa fuente, escrito por un programador.

Síntesis:   Una vez se ha ejecutado el análisis de manera exitosa se procede a agrupará las componentes, que conforman el programa fuente, para construir frases con sentido con el fin de generar una salida.  Que puede ser en lenguaje de máquina o algún otro lenguaje destino que se considere conveniente.

El proceso de análisis  comprende varias fases que son: 

Análisis léxico: Es la fase encargada de la lectura y exploración misma del programa fuente,  Esto
quiere decir que el analizador léxico lee el programa fuente, y lo fracciona en componentes que tienen sentido para el lenguaje de programación que sé está considerando.

Análisis sintáctico: A esta fase le corresponde evaluar que el programa  fuente escrito realmente
cumpla con las especificaciones del lenguaje definido para el compilador.  Para ello normalmente
el programa fuente debe reflejar una estructura especial. Esta debe responder a una serie de reglas, que pueden ser recursivas o no, las cuales se denominan con el nombre de gramáticas.  (Es una de las fases más importantes de la compilación.)

Análisis Semántico:   Esta fase se dedica a determinar si todos los componentes del programa están siendo usados de manera válida, para el contexto en el cual aparecen.  Es decir, se deben los componentes colindantes  a cada componente siendo analizado, antes de determinar que las operaciones ejecutadas por el mismo estén dentro de las operaciones permitidas por el lenguaje, para dicho tipo de situaciones.

Mapa conceptual: Análisis sintáctico y análisis semántico






Una vez el programa fuente ha sido sometido a un análisis completo y se puede tener en cuenta de que esta correctamente escrito.  Solo queda faltando generar algún tipo de salida para que el ciclo de compilación quede completo.

 Las fases restantes hacen una síntesis  del programa fuente para generar la salida.  Estas fases son:

Generación  de código Intermedio: La mayoría de los compiladores modernos intentan optimizar,
hasta donde sea posible, el código que generan. Para lograr esto los compiladores analizan internamente y tratan de generar secuencias  de instrucciones internamente equivalentes a las del programa fuente, o reemplazan instrucciones para hacer un uso más eficiente en la memoria.  Su objeto general es general un código intermedio del programa fuente para que sea usado posteriormente por el optimizador de código.

Optimización de código: El objeto de esta fase es el de mejorar el código fuente escrito para que
sea más rápido de ejecutar, o use de manera más eficiente los recursos de la máquina.  Este proceso se apoya en la generación de código intermedio que fue realizada en la fase anterior.  Por lo general es mucho más complicado optimizar el código basándose en el programa fuente tal  como fue escrito por el programador.

Generación de código: El proceso de generación de código es el que constituye la salida, es decir,
genera el código de máquina que corresponde al programa fuente.  Hay  que recordar la diferencia con los intérpretes y su salida exclusiva de código.

Ejemplo de cómo se compila una línea genérica de un lenguaje:

Tomando una sencilla instrucción del lenguaje pascal se explicará cuál es la forma en que el compilador se comporta en cada fase y etapa respectiva.  Sea la instrucción:
Suma:= ultimo + penúltimo

Inicialmente el analizador léxico leerá la línea carácter a carácter usando como referencia los
espacios en blanco, que indican donde comienza y donde termina cada componen.  El analizador
léxico será invocado de manera sucesiva por el analizador sintáctico y a cada llamada, en su orden
devolviendo lo siguiente:

El identificador:   Suma
El símbolo de asignación: =
El identificador:   último
El operador de suma: +
El identificador:   penúltimo

Luego comienza el análisis sintáctico para verificar que la línea escrita en el lenguaje esta correcta.
Para lo anterior representa en una estructura jerárquica denominada árbol gramatical así: