30 dic. 2007

Parser en Haskell

Hace no mucho me pidieron como proyecto final un verificador para la lógica proposicional modal, el cual decidí hacer en Haskell, estaba aprendiendo Haskell en aquellos tiempos por lo que consideré muy útil poner a prueba lo que había aprendido.

Hacer el verificador fué muy fácil, gracias a las características de Haskell (como el poder definir tipos de datos recursivos etc) y a la definición de la semántica para esta lógica, lo interesante fué cuando tuve que hacer la parte encargada de leer la entrada del programa (texto), la cual era: la especificación de la estructura de Kripke y una fórmula de la lógica modal proposicional.

Al investigar como podía hacer esto me encontré con varios programas, uno de ellos era Happy, cuyo logo es un mono sonriente, el problema fué que no pude hacerlo funcionar como yo quería por lo que tuve que seguir buscando, encontré muchas opciones similares, pero siempre tuve dos dificultades: me daba flojera leer el manual y por no leer con calma el manual no entendía como instalarlo y mucho menos usarlo; como la entrega estaba cerca y era la única parte que me faltaba y el tiempo se agotaba decidí hacerlo a pata, es decir definir las funciones para "parsear" la entrada, para esto me base en las funciones que se dan en el libro de: Haskell: The Craft of Functional Programming

Las funciones son:




{- parse que siempre falla
-}
none :: Parse a b
none inp = []

{- parse que siempre tiene exito
-}
succeed :: b -> Parse a b
succeed val inp = [(val,inp)]

{- parse que tiene exito solo si la cabeza de la entrada es igual
al token
-}
token :: Eq a => a -> Parse a a
token t (x:xs)
| t==x = [(t,xs)]
| otherwise = []
token t [] = []

{- Caso general para token, tiene exito si p x se cumple
-}
spot :: (a -> Bool) -> Parse a a
spot p (x:xs)
| p x = [(x,xs)]
| otherwise = []
spot p [] = []



{- devuleve el resultado del parsing p1 inp O p2 inp
-}

alt :: Parse a b -> Parse a b -> Parse a b
alt p1 p2 inp = p1 inp ++ p2 inp


{- parse que aplica el parsing p2 a lo que resta de la entrada despues de aplicar p1 inp
-}
(>*>) :: Parse a b -> Parse a c -> Parse a (b,c)
(>*>) p1 p2 inp = [ ( ( y , z ),rem2) | (y,rem1) <- p1 inp,(z,rem2) <- p2 rem1]

{- funcion que aplica una funcion f al resultado del parsing, en caso de ser exitoso -}

build :: Parse a b -> (b -> c) -> Parse a c
build p f inp = [ (f x,rem) | (x,rem) <- p inp]

{- realiza el parsing de una lista de objetos -} list :: Parse a b -> Parse a [b]
list p = alt (succeed []) (build (p>*> list p) (uncurry(:)))


{- aplica el parsing n veces a la entrada
-}
nTimes :: Int -> Parse a b -> Parse a [b]
nTimes 0 p = succeed []
nTimes (n+1) p = (p >*> nTimes n p) `build` (uncurry (:))


{- realiza el parsing de una lista de objetos sin cosiderar a la lista vacia
-}
neList :: Parse a b -> Parse a [b]
neList p = (p `build` (:[]))
`alt`
((p >*> list p) `build` (uncurry (:)))


{- funcion de alto nivel, aplica un parsing en caso de ser exitoso devuelve
el resultado, en caso contrario un mensaje de error
-}
topLevel :: Parse a b -> [a]->b
topLevel p inp = case results of
[]-> error"Verifique la entrada"
_-> head results
where results = [found|(found,[])<-p inp] {- -} optional :: Parse a b -> Parse a [b]
optional p = (succeed [])
`alt`
(p `build` (:[]))




La mayoria de estas funciones vienen en el libro que ya mencioné, otras son ejercicios de ese libro (el libro no tiene las respuestas a los ejercisios), con estas funciones es "muy sencillo" definir funciones propias que construyan un parser a modo, para casi cualquier entrada en texto. Para aquellos que como yo empiezan tarde sus proyectos/tareas, y que además les da flojera leer largos manuales, esto les puede ayudar, claro que Happy hace el trabajo de manera más clara y eficiente, pero aveces usar ese tipo de herramientas es como atacar a cañonazos algo que con un revolver es más que suficiente.
Nota: hice "cut and paste" de mi código, por lo que las funciones pueden lucir un poco extrañas, en algún momento subiré el código del proyecto donde usé estas funciones, lo cual podría aclarar mucho las cosas.





2 comentarios:

Anónimo dijo...

Hola tienes el programa del donde parseas me serviria mucho.

Salu2

Pablo Nocetti dijo...

Muy buena entrada, me fue muy util al resaltar mis resultados de los ejercicios del Thompson.
Creo que el parser neList está mal definido, no debería ser directamente igual a list pero sin el `alt` del succeed?

neList parseDig "12+34"
retorna:

[("1","2+34"),("1","2+34"),("12","+34")]

cuando debería retornar:

[("1","2+34"),("12","+34")]

O me equivoco?
Saludos!

ga