Lenguajes y autómatas Introducción a la teoría de lenguajes formales

1. Compiladores

1.1. Es un programa complejo en el que no es fácil distinguir claramente unas partes de otras. Está compuesto por divisiones lógicas del compilador en fases, lo que permite formalizar y estudiar por separado cada una de ellas

1.2. Fases

1.2.1. Análisis léxico: El analizador léxico, también conocido como scanner, lee los caracteres del programa fuente, uno a uno, desde el fichero de entrada y va formando grupos de caracteres con alguna relación entre sí (tokens). Análisis sintáctico: También llamado parser, recibe como entrada los tokens que genera el analizador léxico y comprueba si estos tokens van llegando en el orden correcto. Siempre que no se hayan producido errores, la salida teórica de esta fase del compilador será un árbol sintáctico. Si el programa es in-correcto se generaran los mensajes de error correspondientes. Análisis semántico: El analizador semántico trata de determinar si el significado de las diferentes instrucciones del programa es válido. Para conseguirlo tendrá que calcular y analizar información asociada a las sentencias del programa. Generación de código intermedio: Hay que construir m programas que traduzcan cada lenguaje fuente al código intermedio (front ends) y n programas que traduzcan del lenguaje intermedio a cada lenguaje objeto (back ends). La utilización del lenguaje intermedio permite construir en menos tiempo compiladores para nuevos lenguajes y para nuevas máquinas. Optimización de código: La mayoría de los compiladores suelen tener una fase de optimización de código intermedio (independiente de los lenguajes fuente y objeto), y una fase de optimización de código objeto (no aplicable a otras máquinas). Generación de código objeto: En esta fase, el código intermedio optimizado es traducido a una secuencia de instrucciones en ensamblador o en código máquina.

2. Traductores

2.1. Es un programa que recibe como entrada un texto escrito en un lenguaje, llamado fuente, y genera como salida otro texto equivalente pero escrito en un lenguaje diferente denominado objeto.

3. Bibliografia

3.1. --> E. Hopcroft, J., Motwani, R., & D. Ullman, J. (2007). Teoría de autómatas, Lenguajes y computación (Tercera ed.). Madrid: Pearson Addison-Wesley. --> Jurado Málaga, E. (2008). Teorías de Autómatas y Lenguajes Formales.

3.2. E. Hopcroft, J., Motwani, R., & D. Ullman, J. (2007). Teoría de autómatas, Lenguajes y computación (Tercera ed.). Madrid: Pearson Addison-Wesley. Jurado Málaga, E. (2008). Teorías de Autómatas y Lenguajes Formales.

4. Alfabeto

4.1. Conjunto de símbolos finito y no vacío. Se utiliza el símbolo Σ para designar un alfabeto.

4.2. Σ={0,1} El alfabeto binario Σ={a, b,…, z} El conjunto de todas las letras minúsculas.

5. Cadena

5.1. También conocido en ocasiones como palabra. Es una secuencia finita de símbolos seleccionados de algún alfabeto

5.2. 0110001 Es una cadena de alfabeto binario Σ={0,1} Autómatas Es una cadena del conjunto de todas las letras minúsculas Σ={a,b,…,z}

6. Sub-cadena

6.1. Una cadena α, se dice que es una sub-cadena de la cadena β, si β = Y α U para Y y U.

6.2. De la cadena de alfabeto binario β=0010101 la sub-cadena será α=001, 101, 1010,… Del alfabeto de letras minúsculas β=autómatas la sub-cadena será α=aut, utoma, automa,…

7. Sub-cadena

8. Lenguajes

8.1. Un conjunto de cadenas, todas ellas seleccionadas de un Σ*, donde Σ es un determinado alfabeto se denomina lenguaje.

8.2. Si Σ es un alfabeto y L ⊆ Σ* entonces L es un lenguaje de Σ