Translate

viernes, 10 de julio de 2020

Análisis usando Parsec

Vamos a construir un analizador simple usando la biblioteca Parsec en Haskell.

La función polimórfica show devuelve una representación de una estructura de datos a cadena. La forma más fácil de hacer que un tipo de datos pueda ser parámetro de show es utilizar la cláusula deriving:

    show :: Show a => a -> String
    data D = D ... deriving (Show)
    d :: D
    d = D ...
    str :: String
    str = show d 

Vamos a hacer un parse a XML

    parseShow :: String -> String
    xml = parseShow $ show res

Primero creamos un tipo de datos PersonRecord

data PersonRecord  = MkPersonRecord {
    name :: String,
    address :: Address,
    id :: Integer,
    labels :: [Label]    
} deriving (Show)

Y los tipos Address y Label se definen de la siguiente manera:

data Address = MkAddress {
    line1 :: String,
    number :: Integer,
    street :: String,
    town :: String,
    postcode :: String
} deriving (Show)

data Label = Green | Red | Blue | Yellow deriving (Show)

Derivamos Show usando la cláusula deriving. El compilador creará automáticamente la función show para este tipo de datos. Nuestro analizador analizará la salida de esta función show derivada automáticamente.

Luego creamos algunas instancias de PersonRecord:

rec1 = MkPersonRecord 
    "Wim Vanderbauwhede" 
    (MkAddress "School of Computing Science" 17 "Lilybank Gdns" "Glasgow" "G12 8QQ")
    557188
    [Green, Red]

rec2 = MkPersonRecord 
    "Jeremy Singer" 
    (MkAddress "School of Computing Science" 17 "Lilybank Gdns" "Glasgow" "G12 8QQ")
    42
    [Blue, Yellow]

Podemos probar esto muy fácilmente:

main = putStrLn $ show [rec1,rec2]    

Este programa produce el siguiente resultado:

[MkPersonRecord {name = "Wim Vanderbauwhede", address = MkAddress {line1 = "School of Computing Science", number = 17, street = "Lilybank Gdns", town = "Glasgow", postcode = "G12 8QQ"}, id = 557188, labels = [Green,Red]},
MkPersonRecord {name = "Jeremy Singer", address = MkAddress {line1 = "School of Computing Science", number = 17, street = "Lilybank Gdns", town = "Glasgow", postcode = "G12 8QQ"}, id = 42, labels = [Blue,Yellow]}]

Show muestra la información de la siguiente manera:

Listas: [... elementos separados por comas ...]
Registros: {... pares clave-valor separados por comas ...}
Strings: "..."
Tipos de datos algebraicos: nombre del tipo de variante

Creamos un módulo ShowParser que exporta una sola función parseShow:

module ShowParser ( parseShow ) where
Some boilerplate:
    import Text.ParserCombinators.Parsec
    import qualified Text.ParserCombinators.Parsec.Token as P
    import Text.ParserCombinators.Parsec.Language

El módulo Parsec.Token proporciona varios analizadores básicos. Cada uno de estos toma como argumento un lexer, generado por makeTokenParser usando una definición de lenguaje. Aquí usamos emptyDef del módulo Language.

Es conveniente crear un nombre más corto para los analizadores predefinidos que desea usar, p.

    parens = P.parens lexer
    -- and similar

La función parseShow toma el resultado de show (una cadena) y produce el correspondiente XML (también una cadena). Está compuesto por el analizador real showParser y la función run_parser que aplica el analizador a una cadena.

    parseShow :: String -> String
    parseShow = run_parser showParser

    showParser :: Parser String

    run_parser :: Parser a -> String -> a
    run_parser p str =  case parse p "" str of
        Left err -> error $ "parse error at " ++ (show err)
        Right val  -> val  


Definimos un formato XML para una estructura de datos genérica de Haskell. Utilizamos algunas funciones auxiliares para crear etiquetas XML con y sin atributos.

Header:
<?xml version="1.0" encoding="utf-8"?>
    xml_header =  "<?xml version=\"1.0\" encoding=\"UTF-8\"?>\n"
Tags:
<tag> ... </tag>
    otag t = "<"++t++">"
    ctag t = "</"++t++">"
    tag t v = concat [otag t,v,ctag t]
Attributes:
<tag attr1="..." attr2="...">
    tagAttrs :: String -> [(String,String)] -> String -> String 
    tagAttrs t attrs v = 
        concat [
            otag (unwords $ [t]++(map (\(k,v) -> concat [k,"=\"",v,"\""]) attrs))
            ,v
            ,ctag t
            ]

También utilizamos algunas funciones para unir cadenas. Del Preludio tomamos:

    concat :: [[a]] -> [a] -- join lists
    unwords :: [String] -> String -- join words using spaces

También definimos una función para unir cadenas con caracteres de nueva línea:

    joinNL :: [String] -> String -- join lines using "\n"

Veamos las diferencias entre show y nuestro parse XML : 

Lists
[ ..., ..., ... ]

XML :

<list>
<list-elt>...</list-elt>
...
</list>

    list_parser = do
        ls <- brackets $ commaSep showParser 
        return $ tag "list" $ joinNL $ map (tag "list-elt") ls

Tuples

 ( ..., ..., ... )

XML:

<tuple>
<tuple-elt>...</tuple-elt>
...
</tuple>

tuple_parser = do
    ls <- parens $ commaSep showParser 
    return $ tag "tuple" $ unwords $ map (tag "tuple-elt") ls

Record types

Rec { k=v, ... }

XML:

<record>
<elt key="k">v</elt>
...
</record>

key-value pairs: k = v -- v can be anything
record_parser = do
    ti <- type_identifier
    ls <- braces $ commaSep kvparser
    return $ tagAttrs "record" [("name",ti)] (joinNL ls)

kvparser = do
    k <- identifier
    symbol "="
    t <- showParser
    return $ tagAttrs "elt" [("key",k)] t
    
type_identifier = do
    fst <- oneOf ['A' .. 'Z']
    rest <- many alphaNum
    whiteSpace
    return $ fst:rest    

Algebraic data types

e.g. Label

XML:

<adt>Label</adt>

adt_parser = do
    ti <- type_identifier 
    return $ tag "adt" ti

Cadenas y números 

quoted_string = do
    s <- stringLiteral
    return $ "\""++s++"\""

number = do
    n <- integer
    return $ show n

Combine todos los analizadores utilizando el combinador de elección <|>.

    showParser :: Parser String 
    showParser =
        list_parser <|> -- [ ... ]
        tuple_parser <|> -- ( ... )
        try record_parser <|> -- MkRec { ... }
        adt_parser <|> -- MkADT ...
        number <|>    -- signed integer
        quoted_string <?> "Parse error"

Parsec probará todas las opciones en orden de ocurrencia.

Main program
Import the parser module

    import ShowParser (parseShow)

    rec_str =  show [rec1,rec2]    
    main = putStrLn $ parseShow rec_str

Si probamos esto :

[wim@workai HaskellParsecTutorial]$ runhaskell test_ShowParser.hs 
<?xml version="1.0" encoding="UTF-8"?>
<list><list-elt><record name="MkPersonRecord"><elt key="name">"Wim Vanderbauwhede"</elt>
<elt key="address"><record name="MkAddress"><elt key="line1">"School of Computing Science"</elt>
<elt key="number">17</elt>
<elt key="street">"Lilybank Gdns"</elt>
<elt key="town">"Glasgow"</elt>
<elt key="postcode">"G12 8QQ"</elt></record></elt>
<elt key="id">557188</elt>
<elt key="labels"><list><list-elt><adt>Green</adt></list-elt>
<list-elt><adt>Red</adt></list-elt></list></elt></record></list-elt>
<list-elt><record name="MkPersonRecord"><elt key="name">"Jeremy Singer"</elt>
<elt key="address"><record name="MkAddress"><elt key="line1">"School of Computing Science"</elt>
<elt key="number">17</elt>
<elt key="street">"Lilybank Gdns"</elt>
<elt key="town">"Glasgow"</elt>
<elt key="postcode">"G12 8QQ"</elt></record></elt>
<elt key="id">42</elt>
<elt key="labels"><list><list-elt><adt>Blue</adt></list-elt>
<list-elt><adt>Yellow</adt></list-elt></list></elt></record></list-elt></list>

 
Parsec facilita la creación de potentes analizadores de texto a partir de bloques de construcción utilizando analizadores y combinadores de analizadores predefinidos.

La estructura básica de un analizador Parsec es bastante genérica y reutilizable.

El ejemplo muestra cómo analizar texto estructurado (salida de Show) y generar un documento XML que contenga la misma información.

Dejo link: