Autómatas y Compiladores

Autómatas y Compiladores

1. ¿Por qué es importante?

   • Entrena a buenos desarrolladores, se aprenden metodologías para resolver complejos y amplios problemas, tienen influencia en todos los programas que usen compiladores,
   • Usan el análisis de un programa para transformar el código, hacen que el costo de la abstracción sea razonable

2. Historia de los compiladores

   • Grace Hopper
     • Primer compilador A-0
       • John Backus
         • Primer compilador completo FORTRAN I

3. Problema: Pasar de un lenguaje a otro, usualmente bajar abstracción

   • Intérprete
     • Convierte un código fuente y lo ejecuta al mismo tiempo
       • Corre directamente el código
   • Compilador
     • Convierte el código a un ejecutable
       • ¿Cómo funciona?
         • Mediante una secuencia de fases
           • Análisis Léxico
             • Crea: Tokens
               • Análisis Sintáctico
                 • Crea: Árbol sintáctico
                   • Análisis Semántico
                     • Crea: Árbol sintáctico mejorado
                       • Generador de Código Intermedio
                         • Crea: Interpretación intermedia del código
                           • Optimizador del código intermedio
                             • Crea: Representación intermedia optimizada
                               • Generador de código
                                 • Crea: Código objetivo
                                   • Optimizador de código objetivo
                                     • Crea: Código objetivo optimizado
             • Tabla de símbolos
               • Todos los nombres de identificador junto con sus tipos se almacenan aquí.
   • Soluciones

4. Máquinas de estado finito

   • Reconocen hileras a partir de transiciones de estados
   • Aceptors
     • Moore
       • Estado en el que estoy
     • Mealy
       • Transiciones que he seguido
     • Dado una entrada produce un output específico
   • Recognizers
     • Reconoce o no la entrada
     • Autómata finito
       • No determinista NFA
       • Determinista DFA

5. Lingüística

   • Símbolo
     • Palabra
       • Alfabeto
         • Lenguaje
           • Clausura de Kleen
             • Conjunto de todas las posibles concatenaciones de cadenas
           • Un conjunto de palabras, formado por símbolos en un alfabeto dado.
           • Gramáticas
             • Sirven para representar lenguajes y generarlos
           • Lenguaje regular
             • Gramática Regular
               • Generan lenguajes regulares y los representan
               • Jerarquía de Chomsky
               • Recursiva por izquierda
               • Recursiva por derecha
             • Se pueden generar a partir de los lenguajes básicos, con la aplicación de las operaciones de unión, concatenación y * de Kleene un número finito de veces.
           • Expresiones regulares
             • Patrón de búsqueda para reconocer hileras
           • Representaciones equivalentes
             • Para reconocer palabras pertenecientes a un lenguaje
               • Las cuales forman parte del análisis léxico y compiladores
             • Todos son reconocidos por
               • Máquina de Touring
                 • Dispositivo que manipula símbolos sobre una tira de cinta de acuerdo a una tabla de reglas
         • Conjunto finito de símbolos. Se le conoce con Σ
       • Cadena finita formada por la concatenación de un número de símbolos.
     • Dato arbitrario que tiene algún significado o efecto en la máquina

6. ¿Qué es un autómata?

   • Es un modelo matemático para una máquina de estado finito
   • ¿Como se relaciona con una computadora?
     • Sienta las bases de la algoritmia y permite modelar y diseñar soluciones para un gran número de problemas.

Images and files in the map