Teoría de compiladores

TEORÍA DE COMPILADORES

Las Gramáticas tipo 0 y 1 muestran un buen número de propiedades indecidibles. En las Gramáticas de tipo 0, por ejemplo, puede suceder que no se pueda determinaralgorítmicamente si una frase dada es producto de ella o no; es decir, no se podría saber si una Máquina de Turing diseñada para reconocer esas frases se detendrá o no durante el transcurso de esa computación.La Gramática que describe la sintaxis de los Lenguajes de programación usuales es de tipo 2 y el analizador sintáctico de un compilador es un Autómata de Pila. Así mismo, el analizador lexicográficode un compilador es un Autómata Finito, porque la Gramática que se emplea en la definición léxica de un Lenguaje como C, Fortran o Pascal es de tipo 3.
De hecho, se puede diseñar una Gramática tipo 3que mostraría como se pueden obtener los nombres de los componentes Léxicos para uno de esos Lenguajes, con excepción de las palabras reservadas, mismas que se analizan por otro mecanismo.
Paradiseñar las etapas de análisis de un compilador, es necesario saber diseñar e implementar los Autómatas de este curso, ya que el analizador léxico es un Autómata Finito y los analizadores sintácticos ysemánticos son generalmente Autómatas de Pila.
No es posible diseñar las etapas de análisis de un compilador sin el conocimiento de los temas estudiados en este curso.
Precisamente, el curso de Teoríade la Computación es Pre-requisito para cursar la materia de Compiladores.
En la siguiente figura se muestran las etapas de un compilador:



TOKEN O COMPONENTE LÉXICO:
Es cualquiera de lossímbolos terminales que se manejan en la construcción de sentencias de un programa en un Lenguaje de alto nivel. Se define como un par ordenado:
Token = ( Tipo, Valor ).
ANALIZADOR LÉXICO
Su función escomprobar la correcta construcción de los tokens. A ciertos componentes léxicos (como los id) se les introduce en la tabla de símbolos, si no están ya incluídos.
ANALIZADOR SINTÁCTICO
Su...