Autómatas y Compiladores

¿Por qué es importante?
1. Entrena a buenos desarrolladores, se aprenden metodologías para resolver complejos y amplios problemas, tienen influencia en todos los programas que usen compiladores,
2. Usan el análisis de un programa para transformar el código, hacen que el costo de la abstracción sea razonable
Historia de los compiladores
1. Grace Hopper
  1. Primer compilador A-0
    1. John Backus
      1. Primer compilador completo FORTRAN I
Problema: Pasar de un lenguaje a otro, usualmente bajar abstracción
1. Intérprete
  1. Convierte un código fuente y lo ejecuta al mismo tiempo
    1. Corre directamente el código
2. Compilador
  1. Convierte el código a un ejecutable
    1. ¿Cómo funciona?
      1. 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í.
3. Soluciones
Máquinas de estado finito
1. Reconocen hileras a partir de transiciones de estados
2. Aceptors
  1. Moore
    1. Estado en el que estoy
  2. Mealy
    1. Transiciones que he seguido
  3. Dado una entrada produce un output específico
3. Recognizers
  1. Reconoce o no la entrada
  2. Autómata finito
    1. No determinista NFA
    2. Determinista DFA
Lingüística
1. Símbolo
  1. Palabra
    1. Alfabeto
      1. 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
      2. Conjunto finito de símbolos. Se le conoce con Σ
    2. Cadena finita formada por la concatenación de un número de símbolos.
  2. Dato arbitrario que tiene algún significado o efecto en la máquina
¿Qué es un autómata?
1. Es un modelo matemático para una máquina de estado finito
2. ¿Como se relaciona con una computadora?
  1. Sienta las bases de la algoritmia y permite modelar y diseñar soluciones para un gran número de problemas.

Siguiente

Autómatas y Compiladores

Descripción

Resumen del Recurso

Recursos multimedia adjuntos

Similar

	Creado por José Alfaro Quirós hace más de 5 años