¿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