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

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.

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.


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.


Ejemplo:


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


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


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


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.


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.


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.

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.


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


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 -> [])


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")]


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

letra::AnalizCharletra=elemento !> isAlpha

digito::AnalizChardigito=elemento !> isDigit

letraODigito = letra !+ digito.


Ejemplo: reconocimiento de expresiones:

term ::= constante

| ( term + term )

| ( term / term )


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

analizador léxico. Genera distintos tipos de código:

Haskell 98 Haskell estándar con arrays Haskell con extensiones GHC Haskell GHC con arrays codificados

como cadenas Flexibilidad Velocidad

Happy. Ejemplo{ module Main where }

%name calc%tokentype { Token }

%token let { TokenLet } in { TokenIn } int { TokenInt $$ } var { TokenVar $$ } '=' { TokenEq } '+' { TokenPlus } '-' { TokenMinus } '(' { TokenOB } ')' { TokenCB }

%%

Exp : let var '=' Exp in Exp { Let $2 $4 $6 }

| Exp1 { Exp1 $1 }

Exp1 : Exp1 '+' Term { Plus $1 $3 } | Exp1 '-' Term { Minus $1 $3 } | Term { Term $1 }

Term : int { Int $1 } | var { Var $1 } | '(' Exp ')' { Brack $2 }

n : t_1 .. t_n { E }

Happy. Ejemplo{ happyError :: [Token] -> ahappyError _ = error "Parse error"

data Exp = Let String Exp Exp | Exp1 Exp1

data Exp1 = Plus Exp1 Term | Minus Exp1 Term | Term Term

data Term = Int Int | Var String | Brack Exp

data Token = TokenLet | TokenIn | TokenInt Int | TokenVar String | TokenEq | TokenPlus | …deriving Show

lexer :: String -> [Token]lexer [] = []lexer (c:cs) | isSpace c = lexer cs | isAlpha c = lexVar (c:cs) | isDigit c = lexNum (c:cs)lexer ('=':cs) = TokenEq : lexer cslexer ('+':cs) = TokenPlus : lexer cslexer ('-':cs) = TokenMinus : lexer cslexer ('(':cs) = TokenOB : lexer cslexer (')':cs) = TokenCB : lexer cs

lexNum cs = TokenInt (read num) : lexer rest where (num,rest) = span isDigit cs

lexVar cs = case span isAlpha cs of ("let",rest) -> TokenLet : lexer rest ("in",rest) -> TokenIn : lexer rest (var,rest) -> TokenVar var : lexer

rest

main = getContents >>= print . calc . lexer}

Frown

Utiliza análisis LALR(k) Eficiencia Funcionales

Parsec

Es una librería de combinadores monádicos. Se trabaja directamente en Haskell. Está incluído en GHC y en Hugs. Es más eficiente con gramáticas LL(1).

Parsec. Un ejemplo El código

module Main where

import Text.ParserCombinators.Parsec

simple :: Parser Char simple = letter

ejecuta :: Show a => Parser a -> String -> IO ()ejecuta p input = case (parse p "" input) of Left err -> do{ putStr "error al analizar " ; print err } Right x -> print x

Parsec. Un ejemplo Ejecución

*Main> ejecuta simple ""Loading package parsec-1.0 ... linking ... done.error al analizar (line 1, column 1):unexpected end of inputexpecting letter

*Main> ejecuta simple "123"error al analizar (line 1, column 1):unexpected "1"expecting letter

*Main> ejecuta simple "a"'a'

Parsec. Otro ejemplo

Código

parens :: Parser ()parens = do{ char '(' ; parens ; char ')' ; parens } <|> return ()

Parsec. Otro ejemplo Ejecución

Main> ejecuta parens "((()())())()"Reading file "C:\Documents and Settings\

Brise\Mis documentos\PDA\parsec.hs":()

Main> ejecuta parens "(()"error al analizar (line 1, column 4):unexpected end of inputexpecting "(" or ")"

¿Qué podemos concluir?

Los LF respetan la estructura en fases: lexing, parsing, análisis semántico, etc.


Los LF respetan la estructura en fases: lexing, parsing, análisis semántico, etc.

lexer :: String -> [Token]parser :: [Token] -> ÁrbolAbstractosemántica :: ÁrbolAbstracto -> ÁrbolEtiquetadogeneraciónDeCódigo :: ÁrbolEtiquetado -> [Código máquina]compilador = generaciónDeCódigo . semántica . parser . lexer


Evaluación perezosa La salida del analizador léxico sería una lista

perezosa de tokens.


Evaluación perezosa La salida del analizador léxico sería una lista

perezosa de tokens.

lexer :: String -> [Token]parser :: [Token] -> ÁrbolAbstractosemántica :: ÁrbolAbstracto -> ÁrbolEtiquetadogeneraciónDeCódigo :: ÁrbolEtiquetado -> [Código máquina]compilador = generaciónDeCódigo . semántica . parser . lexer


Tipos de datos Tokens: tipo enumeradodata Token = Id String | IntConst Int | SumaOp |

ProdOp | PuntoYComa



ProdOp | PuntoYComa

Tabla de símbolos: árboles AVL o Tablas Hash



ProdOp | PuntoYComa

Tabla de símbolos: árboles AVL o Tablas Hash Árboles abstractos: tipos mutuamente recursivos



ProdOp | PuntoYComa

Tabla de símbolos: árboles AVL o Tablas Hash Árboles abstractos: tipos mutuamente recursivos

Funciones de orden superior Combinadores de analizadores.


Recursión La recursión y el reconocimiento de patrones que

existen en Haskell son un método potente para tratar este tipo de estructuras recursivas.


Recursión La recursión y el reconocimiento de patrones que

existen en Haskell son un método potente para tratar este tipo de estructuras recursivas.

Polimorfismo

data Instr a = Asignar String a (Expr a) | While (Expr a) (Instr a) | If (Expr a) (Instr a) (Instr a) | ...

Bibliografía Blas C. Ruiz, Francisco Gutiérrez, Paco Guerrero, José E. Gallardo.

Razonando con Haskell. Thomson, Madrid 2004. Cap. 14, Analizadores.

Ricardo Peña. Compile Construction in a Functional Setting. Universidad Complutense de Madrid.

Jeroen Fokker. Functional Parsers. Universidad de Utrecht. Graham Hutton y Erik Meijer. Monadic Parser Combinators.

Universidades de Nottingham y Utrecht.

Referencias web http://www.haskell.org http://www.informatik.uni-bonn.de/~ralf/frown http://www.cs.uu.nl/~daan/parsec.html