Índice
Motivación
¿Qué es un compilador?
Historia
Esquema de un compilador
Técnicas en Haskell estándar
Análisis monádico
Herramientas software
Alex
Happy (Frown)
Parsec
¿Qué podemos concluir?
Bibliografía
¿Qué es un compilador?
Programa que traduce texto escrito en un lenguaje de programación (código fuente) a otro (código objeto).
Código fuente escrito en un lenguaje de alto nivel (Haskell, Java, C++), que queremos pasar a un lenguaje de bajo nivel (ensamblador, lenguaje máquina).
Un poco de historia (I)
En principio, se programaba en código binario.
Años 40: Se crean mnemotécnicos para las operaciones binarias, usando los ordenadores para traducirlos a código máquina.
Años 50: Nacen lenguajes de alto nivel, para crear programas más independientes de la máquina.
Primer compilador: Fortran, 1.957. Equipo de J. Backus, de IBM.
Un poco de historia (II)
Años 60: Se establecen muchos de los principios del diseño de compiladores. Aún se suelen programar en ensamblador
Años 70: Se usan lenguajes de alto nivel, como Pascal y C.
Otros tipos: intérpretes (realizan el proceso sentencia a sentencia). Programas resultantes más lentos, pero más fáciles de depurar.
Esquema de un compilador
Dos fases
Análisis: se lee el programa fuente y se estudia la estructura y el significado del mismo.
Síntesis: se genera el programa objeto.
Otros elementos: tabla de símbolos, rutinas de tratamiento de errores, etc.
Esquema de un compilador
Dos fases
Análisis: se lee el programa fuente y se estudia la estructura y el significado del mismo.
Síntesis: se genera el programa objeto.
Otros elementos: tabla de símbolos, rutinas de tratamiento de errores, etc.
Esquema de un compilador
Dos fases
Análisis: se lee el programa fuente y se estudia la estructura y el significado del mismo.
Síntesis: se genera el programa objeto.
Otros elementos: tabla de símbolos, rutinas de tratamiento de errores, etc.
Fase de análisis
Tres fases
Análisis léxico
Análisis sintáctico
Análisis semántico
Fase de análisis
Tres fases
Análisis léxico:
identificar símbolos,
eliminar separadores,
eliminar comentarios,
crear símbolos de entrada al análisis sintáctico (tokens),
descubrir errores.
Análisis sintáctico
Análisis semántico
Fase de análisis
Tres fases
Análisis léxico
Análisis sintáctico:
comprobar que las sentencias que componen el texto fuente son correctas en el lenguaje, creando una representación interna que corresponde a la sentencia analizada.
Análisis semántico
Fase de análisis
Tres fases
Análisis léxico
Análisis sintáctico
Análisis semántico:
Se ocupa de analizar si la sentencia tiene algún significado. Incluye análisis de tipos, o en general, sentencias que carecen se sentido.
Análisis léxico en Haskell
Pretendemos reconocer expresiones regulares, que pueden ser reconocidas por un autómata finito determinista (AFD).
Implementación de los estados del AFD
f :: String -> (String, Token)
Implementación de transición de A a B: la función fA llama a fB después de leer un carácter y pasarle el resto a fB.
Análisis léxico en Haskell
Ejemplo:
Análisis léxico en Haskell
Ejemplos
funciones analizadoras simples
éxito :: a -> ReadS a
éxito x = s -> [(x, s)]
épsilon :: ReadS ()
épsilon = éxito ()
fallo :: ReadS a
fallo = s -> []
Alternativa:
infixl 5 -+-
(-+-) :: ReadS a -> ReadS a -> ReadS a
p1 -+- p2 = s -> p1 s ++ p2 s
Lectura condicional del primer carácter
rSat :: (Char -> Bool) -> ReadS Char
rSat p = s -> case s of
[] -> []
x:xs -> if p x then [(x,xs)] else []
MAIN> rSat isUpper “ABC”
[(‘A’, “BC”)]
Página siguiente |