¿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”)]
Análisis léxico en Haskell
Ejemplos
combinación de analizadores para conseguir uno más complejo (parser combinator)
infixl 7 &><
(&><) :: ReadS a -> ReadS b -> ReadS (a,b)
p1 &>< p2 = s -> [ ((x1,x2),s2) | (x1,s1) <- p1 s,
(x2,s2) <- p2 s1 ]
MAIN> (rChar ‘a’ &>< rChar ‘b’) “abcd”
[((‘a’, ‘b’), “cd”)]
Análisis sintáctico en Haskell
En un lenguaje funcional como Haskell, es fácil traducir las reglas gramaticales directamente a especificación funcional.
Análisis sintáctico en Haskell
El paradigma funcional nos da una expresividad a la hora de representar reglas gramaticales impensable en el paradigma imperativo.
Ejemplo: función many
many :: Parser a b -> Parser a [b]
exp = term <*> many (token addOp <*> term