Construcción de compiladores con Haskell (PPT)

---

---

Partes: 1, 2

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