El análisis es el mecanismo que utilizamos para dar sentido a la información estructurada en un texto, por ejemplo lenguaje escrito o hablado. En el caso del lenguaje escrito, implica varios pasos:
- reconociendo los caracteres del sistema de escritura,
- palabras identificativas,
- identificar oraciones,
- identificar párrafos, etc.
Para poder hacerlo, necesitamos conocer el sistema de escritura, la ortografía y la gramática del idioma en el que está escrito el documento.
Para analizar texto estructurado como el código fuente del programa, HTML o JSON, el problema es similar.
Hasta ahora, hemos visto funciones que toman funciones como argumentos. Las funciones también pueden devolver funciones como valores
Por ejemplo, aplicación parcial de una función:
sum = foldl (+) 0
Aquí (suma) es el resultado devuelto por la aplicación parcial de (foldl).
Más explícitamente, podemos escribir esto como:
sum = \xs -> foldl (+) 0 xs
Ambos son, por supuesto, la misma cosa, solo diferentes interpretaciones.
Podemos usar este concepto para generar funciones parametrizadas
Por ejemplo, la siguiente función genera funciones que agregan un número constante a su argumento:
gen_add_n = \n ->
\x -> x+n
add_3 = gen_add_n 3
add_7 = gen_add_n 7
add_3 5 --> 8
add_7 4 --> 11
Por supuesto, esto no se limita a las constantes numéricas
Por ejemplo, la siguiente función genera funciones que realizan una operación aritmética dada en un número constante y su argumento:
gen_op_n = \op n ->
\x -> x `op` n
add_3 = gen_op_n (+) 3
mult_7 = gen_op_n (*) 7
add_3 5 --> 8
mult_7 4 --> 28
Para hacer que el problema de análisis sea más concreto, suponga que debe analizar la siguiente receta e identificar los diferentes pasos necesarios en la preparación.
Hervir una olla grande de agua. A diferencia de la pasta italiana, no es necesario salar el agua. Una vez que esté hirviendo, sostenga los fideos sobre el agua y espolvoréelos hilo por mechón. Una vez que todos los fideos estén adentro, revuelva suavemente para que estén todos sumergidos en el agua. Vuelva a hervir suavemente el agua y luego baje el fuego para que el agua hierva a fuego lento. (Esto difiere del 'hervor rodante' que se recomienda para la pasta). Si el agua amenaza con hervir, agregue aproximadamente 1/2 taza de agua fría (pero si baja el fuego a fuego lento y tenga una olla lo suficientemente grande) , esto no debería ser necesario). Cocine durante aproximadamente 7 a 8 minutos, o siguiendo las instrucciones del paquete (para fideos más delgados, de 5 a 6 minutos puede ser suficiente. Pruebe comiendo un mechón; debe cocinarse bien, no al dente, pero tampoco blanda).
Típicamente, un programa funcional se organiza alrededor de una estructura de datos en forma de árbol con un tipo de datos algebraicos que representa los datos centrales.Un analizador lee la entrada de texto y genera el árbol. Las funciones realizan transformaciones o recorridos en el árbol.
La función Show imprimen el árbol (original o transformado)
Los combinadores de analizador son funciones que le permiten combinar analizadores más pequeños en otros más grandes. Son funciones de orden superior que toman funciones como argumentos y devuelven funciones. Una biblioteca de combinador de analizador proporciona analizadores básicos (para palabras, números, etc.) y combinadores.
Parsec: combinadores de análisis monádico Hay muchas bibliotecas de análisis para Haskell. Parsec opera en una mónada.
Es posible que haya escuchado el término mónada antes, y discutiremos el concepto en detalle en una sesión posterior. Haskell usa mónadas para estructurar cálculos. Ya te has encontrado con la mónada IO, que debes usar para realizar IO en un programa Haskell. Un ejemplo típico es
hello :: String -> IO String
hello x =
do
putStrLn ("Hello, " ++ x)
putStrLn "What's your name?"
name <- getLine
return name
Esto ilustra las características sintácticas clave de una mónada: la palabra clave do, la secuencia de comandos, la forma de extraer información de un cálculo monádico utilizando la flecha izquierda <- y la palabra clave return. De hecho, el uso de la notación do es bastante similar a la programación imperativa.
También tenga en cuenta el valor de retorno de nuestra función hello: no solo String sino IO String. Un cálculo realizado en una mónada devuelve un tipo "monádico", decimos que la cadena se devuelve dentro de la mónada.
Por ejemplo, supongamos que queremos analizar una cadena de la forma (<etiqueta>), donde (etiqueta) debe ser una palabra, y devolver la etiqueta como un tipo (Etiqueta).
data Tag = MkTag String
parseTag :: Parser Tag
parseTag =
do char '<'
x <- identifier
char '>'
return (MkTag x)
Como puede ver, el analizador consta de una serie de funciones (por ejemplo, char e identificador) que se llaman secuencialmente. Además, el valor de retorno es de tipo Parser Tag, no simplemente Tag. Esto se debe a que parseTag no devuelve un valor, sino que devuelve un analizador. Podemos combinar este analizador con otros analizadores, y luego podemos ejecutar el analizador final en nuestros datos.
Para probar su analizador, inicie ghci:
[wim@fp4 ~]$ ghci
GHCi, version 7.4.1: http://www.haskell.org/ghc/ :? for help
Loading package ghc-prim ... linking ... done.
Loading package integer-gmp ... linking ... done.
Loading package base ... linking ... done.
Then, import Parsec:
Prelude> import Text.ParserCombinators.Parsec
Parsec proporciona la práctica función parseTest, que toma un analizador y una cadena y la ejecuta. Intentemos ejecutar el analizador char 'b' en la cadena "contras":
Prelude Text.ParserCombinators.Parsec> parseTest (char 'b') "cons"
Loading package bytestring-0.9.2.1 ... linking ... done.
Loading package transformers-0.2.2.0 ... linking ... done.
Loading package mtl-2.0.1.0 ... linking ... done.
Loading package array-0.4.0.0 ... linking ... done.
Loading package deepseq-1.3.0.0 ... linking ... done.
Loading package text-0.11.2.0 ... linking ... done.
Loading package parsec-3.1.2 ... linking ... done.
Because the string “cons” does not contain the character ‘b’, we get a parse error:
parse error at (line 1, column 1):
unexpected 'c'
expecting 'b'Probemos con char 'c':
Prelude Text.ParserCombinators.Parsec> parseTest (char 'c') "cons"
'c'
Prelude Text.ParserCombinators.Parsec>
This time the parse succeeded.
El código real para el ejemplo parseTag requiere algunos módulos y definiciones adicionales
Como un ejemplo simple, definamos parseDiv como:
-- the "deriving Show" is needed to let `ghci` print the result
data Tag = MkTag String deriving Show
parseDiv = do
string "<div>"
return (MkTag "div")
Para definir esta función en ghci, puede escribir esto en una línea de la siguiente manera:
let parseDiv = do { string "<div>";return $ MkTag "div" }
Ahora podemos ejecutar este analizador utilizando la función parseTest:
Prelude Text.ParserCombinators.Parsec> parseTest parseDiv "<div>"
Loading package parsec-2.1.0.1 ... linking ... done.
MkTag "div"
Prelude Text.ParserCombinators.Parsec> parseTest parseDiv "div"
parse error at (line 1, column 1):
unexpected "d"
expecting "< "
Prelude Text.ParserCombinators.Parsec>
Todos los combinadores de analizador son funciones que devuelven funciones.
Es la función devuelta que opera en la cadena, no la función del combinador del analizador.
Los analizadores básicos ((identifier),(natural),(char)) no toman argumentos (por ejemplo (identifier)) o una o más cadenas para la parametrización (por ejemplo (char)).
char = \ch -> \str ->
-- try to match the character ch
-- return the result
Si la coincidencia tiene éxito, la cadena coincidente se elimina de la cadena de entrada; de lo contrario, se devuelve la cadena original, p.
char "c" "cons" -->
"c"
char "b" "cons" -->
parse error at (line 1, column 1):
unexpected "c"
expecting "b"
Los combinadores de analizador como <|> y parens toman otros analizadores como argumentos.
parens = \p ->
\str ->
-- first match "("
-- perform the parse of p if "(" was found
-- then match ")"
-- return the result
A menudo queremos probar un analizador sintáctico; Si eso falla, intente con otro. El combinador de elección <|> proporciona esta funcionalidad.
Ejemplo: (letter_digit) coincidirá con una letra o un dígito.
letter_digit :: Parser Char
letter_digit =
do x <- letter <|> digit
return x
Prelude Text.ParserCombinators.Parsec> parseTest letter_digit "b2"
"b"
Prelude Text.ParserCombinators.Parsec> parseTest letter_digit "2b"
"2"
Prelude Text.ParserCombinators.Parsec> parseTest letter_digit "*2"
parse error at (line 1, column 1):
unexpected "*"
expecting letter or digit
Supongamos que queremos hacer coincidir la bolsa o el pantano, pero nada más.
bag_bog :: Parser String
bag_bog =
do xs <- string "bag" <|> string "bog"
return xs
Prelude Text.ParserCombinators.Parsec> parseTest bag_bog "bag"
"bag"
Prelude Text.ParserCombinators.Parsec> parseTest bag_bog "bug"
parse error at (line 1, column 1):
unexpected "u"
expecting "bag"
But there’s a problem!
Prelude Text.ParserCombinators.Parsec> parseTest bag_bog "bog"
parse error at (line 1, column 1):
unexpected "o"
expecting "bag"
La primera "bag" de la cadena del analizador coincidió con la b pero luego falló en la a. Ahora ha consumido el b. La segunda cadena del analizador "bog" ahora intenta hacer coincidir b contra o, lo que por supuesto falla.
try: no consuma entradas en el análisis fallido
Para permitirle analizar provisionalmente sin consumir ninguna entrada, Parsec proporciona la función try:
bag_bog_try :: Parser String
bag_bog_try =
do xs <- try (string "bag") <|> string "bog"
return xs
Prelude Text.ParserCombinators.Parsec> parseTest bag_bog_try "bag"
"bag"
Prelude Text.ParserCombinators.Parsec> parseTest bag_bog_try "bug"
parse error at (line 1, column 1):
unexpected "u"
expecting "bog"
Prelude Text.ParserCombinators.Parsec> parseTest bag_bog_try "bog"
"bog"
Some parsers from the library
La biblioteca Parsec proporciona algunos analizadores pequeños que son útiles para definir los más grandes:
(char \; “?”) - (char) se aplica a un personaje y le da un analizador que coincide con ese personaje
(letter): coincide con cualquier letra
(digit): coincide con cualquier dígito
(string): coincide con una cadena de caracteres
(stringLiteral \; “xyz *”): coincide con el argumento de cadena
(many \; p): coincide con 0 o más apariciones de analizador (p)
(many1 \; p): coincide con 1 o más apariciones de analizador (p)
varname :: Parser String
varname =
do x <- letter
xs <- many (letter <|> digit)
return (x:xs)
Prelude Text.ParserCombinators.Parsec> parseTest varname "a4cc7*5"
"a4cc7"
Prelude Text.ParserCombinators.Parsec> parseTest varname "34a"
parse error at (line 1, column 1):
unexpected "3"
expecting letter
Las expresiones aritméticas son complejas de analizar debido a las reglas de precedencia y la aridad de los operadores.
Parsec proporciona soporte para el análisis de expresiones, por lo que no tiene que escribir su propio analizador de expresiones.
expr_parser :: Parser Expr
expr_parser = buildExpressionParser optable term <?> "expression"
optable =
let
op name assoc =
Infix ( do { reservedOp name;
return (\x y ->(Op (MkOpExpr name x y))) } ) assoc
prefix name =
Prefix (
reservedOp name >>
return (\x->(Pref (MkPrefixOpExpr name x))) )
in
[ [ op "*" AssocLeft, op "/" AssocLeft, op "%" AssocLeft ]
, [ op "+" AssocLeft, op "-" AssocLeft ], [ prefix "-" ] ]
Este ejemplo usa una sintaxis adicional de mónada: puede usar llaves y punto y coma en lugar de sangría; y el operador >> también es una forma más corta de escribir la notación do:
do
expr1
expr2
Se puede escribir como
expr1 >> expr2
También tenga en cuenta el uso del operador <?>, Que se utiliza para definir un mensaje de error personalizado en caso de que falle un análisis sin consumir ninguna entrada. Esta es una característica de depuración muy útil.
Parsec también tiene soporte para lenguajes de programación con un mecanismo para definir la sintaxis y las palabras clave a través de makeTokenParser.
Para casos simples, puede usar emptyDef.
import Text.ParserCombinators.Parsec.Expr
import qualified Text.ParserCombinators.Parsec.Token as P
lexer = P.makeTokenParser emptyDef
parens = P.parens lexer
commaSep = P.commaSep lexer
-- and many more
Una de las JDK más utilizadas, cambia de nombre para estar bajo el paraguas de la organización eclipse.
