UNIDAD I.- INTRODUCCIÓN A LA TEORIA DE LENGUAJES FORMALES

Get Started. It's Free
or sign up with your email address
Rocket clouds
UNIDAD I.- INTRODUCCIÓN A LA TEORIA DE LENGUAJES FORMALES by Mind Map: UNIDAD I.- INTRODUCCIÓN A LA TEORIA DE LENGUAJES FORMALES

1. ALFABETO

1.1. Conjunto no vacío y finito de símbolos. Se representa por Σ.

2. CADENA

2.1. Secuencia finita de símbolos de un determinado alfabeto (Σ).

2.1.1. La cadena vacía (Ɛ), presenta 0 apariciones de símbolos.

2.2. SUBCADENA

2.2.1. una cadena “z” es subcadena de otra cadena “w” si existen cadenas x, y ∈ Σ* tal que w = x • z • y.

3. LENGUAJE

3.1. Conjunto de cadenas dado un alfabeto (Σ), se representa por L. El lenguaje vacío (Ø) está compuesto por ninguna cadena.

4. OPERACIONES

4.1. Estas propiedades están sustentadas en la teoría de conjuntos, por lo tanto todos los conceptos manejados se aplican a los lenguajes.

5. TRADUCTORES

5.1. Programa que procesa un texto fuente (lenguaje fuente) y genera un texto objeto (lenguaje objeto). Se identifican 2 fases principales.

5.1.1. ANÁLISIS

5.1.1.1. Comprueba que el programa esté escrito conforme a las reglas del lenguaje. Su objetivo es obtener una representación de la entrada.

5.1.1.1.1. ANÁLISIS LÉXICO: Divide la entrada en componentes léxicos. ANÁLISIS SINTÁCTICO: Encuentra las estructuras presentes en la entrada. ANÁLISIS SEMÁNTICO: Comprueba que se cumplan las restricciones semánticas del lenguaje.

5.1.2. SÍNTESIS

5.1.2.1. Genera el texto equivalente en el lenguaje objeto.

5.1.2.1.1. GENERACIÓN DE CÓDIGO INTERMEDIO: En esta etapa se traduce la entrada a una representación independiente de la maquina pero fácilmente traducible a lenguaje ensamblador. GENERACIÓN DE CÓDIGO OBJETO: Genera el programa usando las herramientas de la CPU o maquina objeto y el formato para archivos ejecutables del S.O. OPTIMIZACIÓN: Transforma el código intermedio en uno de función equivalente pero de menor tamaño y/o menor tiempo de ejecución.

6. COMPILADORES.

6.1. Son aquellos traductores que tienen como entrada una sentencia de algún lenguaje formal y como salida tienen un programa ejecutable, es decir, que realiza una traducción de un código de alto nivel a código máquina.

6.1.1. LAS FASES DEL COMPILADOR SON:

6.1.1.1. ANÁLISIS

6.1.1.1.1. ANÁLISIS LÉXICO O RASTREADOR (SCANNER): Verifica si todas las cadenas pertenecen o no al lenguaje en caso de que no genere un error. ANÁLISIS SINTÁCTICO O PARSER: Analiza la estructura de las expresiones y sus relaciones jerárquicamente y determina si una cadena es válida o no. ANÁLISIS SEMÁNTICO: Realiza las comprobaciones del uso correcto de variables, funciones y los operadores en tiempo de ejecución así como los tipos de datos.

6.1.1.2. SÍNTESIS

6.1.1.2.1. GENERADOR DE CÓDIGO INTERMEDIO: Es una etapa en la que se mejora el código fuente. OPTIMIZACIÓN DE CÓDIGO FUENTE: Pasa el código intermedio a una forma más óptima y eficiente con el fin de ocupar menos espacio y un menor tiempo de ejecución generando el código para la máquina objetivo. GENERADOR DE CÓDIGO OBJETIVO: Intenta mejorar el código objetivo generado por el optimizador de código. Dichas mejoras incluyen el rendimiento reemplazando las instrucciones lentas por otras más rápidas y eliminando las operaciones redundantes o innecesarias.

7. BIBLIOGRAFIA

7.1. Louden C. Kenneth. Construcción de compiladores. Principios y Prácticas. Editorial Thompson. México 2004. ISBN: 0-534-93972-4. Cueva Lovelle, J.M. Conceptos Básicos de Procesadores de lenguaje. Editorial SERVITEC. España 1998. ISBN:84-8416-889-1. Hopcroft, J. E.; Motwani, R.; Ulman, J. D. Introducción a la Teoría de Autómatas, Lenguajes y Computación. Editorial Pearson Educación S.A., Madrid, 2007. ISBN: 978-84-7829-088-8. PROGRAMACIÓN DE SISTEMAS. 1.4 TRADUCTOR Y SU ESTRUCTURA. FECHA DE RECUPERACIÓN. 12 de febrero de 2014. http://ing-radjchv-pmz-estl.blogspot.mx/2009/09/14-traductor-y-su-estructura.html Bavera, Francisco Pedro. Un Generador de Análisis Léxicos Traductores. Universidad Nacional de Río Cuarto. Facultad de Ciencias Exactas, Fisico-Quimicas y Naturales. Departamento de Computación. Fecha de recuperación. 12 de febrero de 2014. http://dc.exa.unrc.edu.ar/staff/fbavera/papers/TesisJTLex-Bavera-Nordio-02.pdf. Estrada Canul, Roger Alfredo. Introducción a la Teoría de Lenguajes Formales. Instituto Tecnológico Superior de Felipe Carrillo Puerto. Fecha de recuperación 12 de febrero de 2014. http://www.slideshare.net/LuyzMeyner/lenguajes-autmatas. Villalta, Pedro Antonio. Compiladores e Intérpretes. Introducción a Compiladores e Intérpretes. Fecha de recuperación 13 de febrero de 2014. http://compiladores-interpretes.blogspot.mx/2012/01/introduccion-compiladores-e-interpretes.html. Galvez Rojas, Sergio. Mora Mata M. Ángel. Java a Tope: Traductores y Compiladores con Lex/Yacc, JFlex/Cup y JavaCC. Departamento de Lenguajes y Ciencias de la Computación E.T.S. de Ingeniería Informática. Universidad de Malaga. Fecha de recuperación 13 de febrero de 2014. http://www.giaa.inf.uc3m.es/docencia/II/PL2/herramientas/JFlex_JavaCC.pdf.