Í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”)]