construcción de compiladores con haskell josé maría carmona cejudo briseida sarasola gutiérrez

Report

Post on 23-Jan-2016

226 Views

Category:

Documents

0 Downloads

Preview:

Click to see full reader

TRANSCRIPT

Construcción de compiladores con Haskell

José María Carmona Cejudo

Briseida Sarasola Gutiérrez

Í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ácterrSat :: (Char -> Bool) -> ReadS CharrSat 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.

exp -> term rest

rest -> + exp

| epsilon

exp = term <*> rest

rest = token AddOp <*> exp <|> epsilon

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 manymany :: Parser a b -> Parser a [b]

exp = term <*> many (token addOp <*> term <@ f4) <@ f5

Análisis sintáctico en Haskell

Lo que hemos visto se refiere a análisis de arriba a abajo.

Realizar análisis de abajo a arriba es más complejo.

Happy es una herramienta que nos facilita la creación de un analizador abajo a arriba.

Análisis semántico.

Una vez construido al árbol sintáctico, los demás algoritmos se pueden expresar como recorridos en ese árbol.

La programación funcional es muy potente a la hora de realizar recorridos en un árbol, como veremos.

Análisis semántico.

Atributos de los nodos del árbol: Se usan para asignar un valor parcial a cada nodo del

árbol, para ir calculando, por ejemplo, los valores de una expresión paso a paso.

Atributo sintetizado: Para calcularlo, necesitamos calcular antes los atributos de

los sucesores. Ejemplo: Inferencia de Tipos

Se corresponde a un recorrido de abajo a arriba. Funciones de orden superior como foldTree son muy

útiles, y nos dan una sencillez y expresividad grandes.

Análisis semántico.

Atributos heredados. Su valor ya está calculado, arriba o al mismo

nivel en el árbol. Se corresponden a un recorrido de arriba a abajo. Se puede representar mediante una función

recursiva (posiblemente de cola), acumulando los atributos.

Veamos en el árbol anterior cuáles serían atributos heredados.

Análisis semántico

Analizadores monádicos

Wadler, en 1995, introdujo el uso de las mónadas para implementar analizadores.

Usando el parser combinator &>< que hemos visto, tenemos tuplas anidadas, engorrosas de manipular.

La función monádica bind (>>=) junto con el uso de lambda-abstracciones nos permite una notación más manejable.

Además, podemos usar otros combinadores monádicos.

Analizadores monádicos

Ejemplo: secuencia Como se ha visto en clase, algo bueno de las mónadas es que

permiten simular secuenciación al estilo imperativo:

aplica :: Analiz a -> String ->[(a, Estado)]

aplica (AN p) ent = p ent

dosElementos::Analiz String

dosElementos=do

a <- elemento

b <- elemento

return[a,b]

MAIN> aplica dosElementos “abcdca”

[(“ab”, “cdca”)] :: [(String, String)]

Analizadores monádicos

Mediante MonadPlus, podemos implementar el concepto de alternancia. Mplus toma dos analizadores, y concatena el resultado de ambos sobre la cadena entrada; mzero falla siempre.

Instance MonadPlus analiz where mplus (AN p)(AN q) = AN(\ent -> p ent ++ q ent) mzero = AN (\ent -> [])

Analizadores monádicos

Tomando (!+) como sinónimo de mplus, podemos construir lo siguiente: elemento !+ dosElementos, que captura un solo carácter, o dos.

Otro ejemplo: filtros

(!>) ::Analiz a -> (a -> Bool) -> Analiz ak !> p = do

a <- kif p a then return a else mzero

unoODosElementos = elemento !+ dosElementos

> aplica unoODosElementos "abcdca"

[("a","bcdca"),("ab","cdca")]

Analizadores monádicos

Reconocimiento de una letra, o bien de un número:

letra::AnalizCharletra=elemento !> isAlpha

digito::AnalizChardigito=elemento !> isDigit

letraODigito = letra !+ digito.

Analizadores monádicos

Ejemplo: reconocimiento de expresiones:

term ::= constante

| ( term + term )

| ( term / term )

Analizadores monádicos

Ejemplo: reconocimiento de expresiones:

anaConst::AnalizTerm

anaConst=do

a <- número

return(Const a)

anaSum::AnalizTerm

anaSum=do

_ <- literal ’(’

u <- term

_ <- literal ’+’

v <- term

_ <- literal ’)’

return(u:+:v)

anaDiv::AnalizTerm

anaDiv=do

_ <- literal ’(’

u <- term

_ <- literal ’/’

v <- term

_ <- literal ’)’

return(u:/:v)

term::AnalizTerm

term=anaConst !+ anaSum !+ anaDiv

Software específico

Alex Happy Frown Parsec

Alex

Analizador léxico (Lex). Características

Basado en expresiones regulares Y en autómatas finitos deterministas (DFAs) Definir

Macros Reglas Contextos Expresiones start

Facilita envoltorios (wrappers)

Alex. Wrappers

“basic” El más simple: dada una cadena, devuelve una lista de

Tokens.

“posn” Da más funcionalidades (número de línea/columna)

“monad” El más flexible Es una plantilla para construir nuestras propias mónadas

“gscan” Presente por razones históricas

Alex. Ejemplo module Main (main) where

%wrapper "basic"

$digit = 0-9$alpha = [a-zA-Z]tokens :-

$white+ ; "--".* ; let \s -> Let in \s -> In $digit+ \s -> Int (read s) [\=\+\-\*\/] \s -> Sym (head s) $alpha [$alpha $digit \- \']*

\s -> Var s

-- Each action has type :: String -> Token

-- The token type:data Token =

Let |In |Sym Char |Var String |Int Intderiving (Eq,Show)

main = do s <- getContents print (alexScanTokens s)

Alex. Fichero resultante-- The token type:data Token =

Let |In |Sym Char |Var String |Int Intderiving (Eq,Show)

main = do s <- getContents print (alexScanTokens s)

alex_action_2 = \s -> Let alex_action_3 = \s -> In alex_action_4 = \s -> Int (read s) alex_action_5 = \s -> Sym (head s) alex_action_6 = \s -> Var s

type AlexInput = (Char,String)

alexGetChar (_, []) = NothingalexGetChar (_, c:cs) = Just (c, (c,cs))

alexInputPrevChar (c,_) = c

-- alexScanTokens :: String -> [token]alexScanTokens str = go ('\n',str) where go inp@(_,str) =

case alexScan inp 0 of AlexEOF -> [] AlexError _ -> error "lexical error" AlexSkip inp' len -> go inp' AlexToken inp' len act -> act (take len str) : go inp'

Happy

Utiliza análisis LALR(1). Trabaja en conjunción con un