1 Formateador y Analizador de textosDaniel Montoya Ramos Eva María García García Loli Burgueño Caballero
2 Índice Formateador Analizador Analizador monádico
3 Formateador de textos
4 Analizador de textos
5 Analizador de textos Introducción Show Read
6 Analizador de textos Analizador que reconoce una lista de uno o más enteros Operadores (combinadores) Metasímbolo definición (::=) Metasímbolo alternativa (|) Metasímbolo repetición ({}0) Metasímbolo repetición no vacía ({}1) Metasímbolo opción ([]) Metasímbolo agrupación (())
7 Analizador de textos Analizador que reconoce una lista de uno o más enteros Gramática Dígito ::= 0|1|2|3|4|5|6|7|8|9 NumNatural ::= {Dígito}1 NumEntero ::= [+|-] NumNatural ListaEnteros ::= [ Enumeración ] Enumeración ::= NumEntero {, NumEntero}0
8 type ReadS a = String -> [(a, String)]Analizador de textos ReadS a Tipo polimórfico para analizadores que devuelven valores de tipo a type ReadS a = String -> [(a, String)] Devolverá un par donde: La primera componente será un valor del tipo a. La segunda será de tipo String y se corresponderá con el valor de la cadena de salida.
9 Analizador de textos éxito x = \s -> [(x, s)] Segundo analizador:Primer analizador: éxito :: a -> ReadS a éxito x = \s -> [(x, s)] Toma un argumento, no consume ningún carácter y devuelve ese mismo argumento. Segundo analizador: épsilon :: ReadS () épsilon = éxito () No toma argumentos y devuelve siempre el mismo, (). Tampoco consume caracteres de la entrada. Tercer analizador: fallo :: ReadS a fallo = \s -> [] Falla siempre.
10 Analizador de textos rCHar rChar :: Char -> ReadS CharrChar c = \s -> case s of [] -> [] x:xs -> if c == x then [(x,xs)] else [] Toma un carácter como argumento Tiene éxito si la cadena de entrada comienza por ese carácter y en ese caso lo consume
11 Analizador de textos rSat rSat :: (Char -> Bool) -> ReadS CharrSat p = \s -> case s of [] -> [] x:xs -> if p x then [(x,xs)] else [] Más general que rChar Recibe como argumento una condición Tiene éxito si el primer carácter de la cadena de entrada cumple la condición y en ese caso lo consume.
12 Analizador de textos Metasímbolo alternativa. Analizador -+-infixl 5 -+- (-+-) :: ReadS a -> ReadS a -> ReadS a p1 -+- p2 = \s -> p1 s ++ p2 s El analizador p1 -+- p2 tendrá éxito si lo tiene p1, p2 o ambos Devolverá en la lista solución el resultado de aplicar p1 y el de aplicar p2
13 Analizador de textos Analizador >>> infixr 6 >>>(>>>) :: ReadS a -> (a -> ReadS b) -> ReadS b p >>> f = \s -> [ (y,s2) | (x,s1) <- p s, let p2 = f x, (y,s2) <- p2 s1 ] Argumentos: un analizador y una función. Ejemplo: función rAB rAB :: ReadS (Char, Char) rAB = rSat isUpper >>> (\x -> rSat isUpper >>> (\y -> éxito (x,y))) solo tiene éxito si en la entrada hay dos caracteres mayúscula consecutivos y en ese caso los devuelve.
14 Analizador de textos Metasímbolo repetición (rep1)rep1 :: ReadS a -> ReadS [a] Aplica el analizador p una o más veces a la entrada y devuelve el resultado en una lista Metasímbolo repetición no vacía (rep0) rep0 :: ReadS a -> ReadS [a] Idem pero también permite aplicarla cero veces
15 rNumNatural :: ReadS IntegerAnalizador de textos Reconocer números naturales rNumNatural :: ReadS Integer Devuelve un analizador de enteros Usamos los combinadores definidos y pasamos el valor a Int El resultado deseado es el primero => definimos una función primero y la aplicamos al resultado anterior
16 (?) :: ReadS a -> a -> ReadS aAnalizador de textos Metasímbolo de opción (?) (?) :: ReadS a -> a -> ReadS a Argumentos: Primer argumento: Analizador p Segundo argumento Si p tiene éxito sobre la cadena de entrada devuelve dicho resultado Si p falla devuelve el segundo argumento.
17 Analizador de textos Reconocer números enteros Ideas generales(rChar '+' -+- rChar '-') “
18 rListaEnteros :: ReadS [Integer]Analizador de textos Lista de números enteros rListaEnteros :: ReadS [Integer] Devuelve un analizador de enteros Es fácil de definir a partir de los operadores anteriores.
19 Analizadores Monádicos
20 Representación data Analiz a = AN (Estado -> [(a,Estado)]) type Estado = String
21 Funciones Aplicar un analizador a una cadena de entrada devolviendo los posibles análisis aplica :: Analiz a -> String -> [(a,Estado)] aplica (AN p) ent = p ent Analizador elemental elemento :: Analiz Char elemento = AN (\ent -> case ent of [] -> [] (x:xs) -> [(x,xs)])
22 Secuenciación instance Monad Analiz where-- return :: a -> Analiz a return v = AN (\ent -> [(v,ent)]) -- (>>=) :: Analiz a -> (a -> Analiz b) -> Analiz b (AN p) >>= k = AN (\ent -> concat [aplica (k v) sal | (v,sal) <- p ent])
23 Propiedades de las MónadasElemento neutro de la secuenciación (>>=f).return = f (>>= return) = id Asociatividad de la secuenciación (>>=g).(>>=f) = (>>=((>>=g).f))
24 Alternancia instance MonadPlus Analiz wheremplus (AN p) (AN q) = AN (\ent -> p ent ++ q ent) mzero = AN (\ent -> [] ) (!+) :: Analiz a -> Analiz a -> Analiz a (!+) = mplus
25 Ejemplo: Analizador que lee uno o dos elementosunoODosElementos :: Analiz String unoODosElementos = elementoS !+ dosElementos Main> aplica unoODosElementos "" [] :: [([Char],Estado)] Main> aplica unoODosElementos "h" [("h","")] :: [([Char],Estado)] Main> aplica unoODosElementos "hola" [("h","ola"),("ho","la")] :: [([Char],Estado)]
26 Propiedades de la alternanciaAsociativa (m !+ n) !+ o = m !+ (n!+o) Distributiva (m !+ n) >>= o = (m>>=o) !+ (n!+o) Elemento neutro mzero !+ m = m m!+ mzero = m
27 Filtros (!>) :: Analiz a -> (a -> Bool) -> Analiz ak !> p = do a <- k if p a then return a else mzero
28 Ejemplos: analizadores de letra, dígito o ambosletra :: Analiz Char letra = elemento !> isAlpha dígito :: Analiz Char dígito = elemento !> isDigit letraODígito = letra !+ dígito literal :: Char -> Analiz Char literal c = elemento !> (== c) Main> aplica letra "hola" [('h',"ola")] :: [(Char,Estado)] Main> aplica letra "5hola" [] :: [(Char,Estado)] Main> aplica dígito "5hola" [('5',"hola")] :: [(Char,Estado)]
29 Iteración iter :: Analiz a -> Analiz [a] iter m = do x <- mxs <- iter m return (x:xs) !+ return []
30 Ejemplo: analizar un númeronúmero :: Analiz Int número = do a <- dígito x <- iter dígito return (aInt (a:x)) where chrAInt :: Char -> Int chrAInt c = ord c - ord '0' aInt :: [Char] -> Int aInt = foldl1 (\x y -> 10*x + y) . map chrAInt Main> aplica número "123letras" [(123,"letras"),(12,"3letras"),(1,"23letras")] :: [(Int,Estado)]
31 Elección parcial (!*) :: Analiz a -> Analiz a -> Analiz am !* n = AN (\ent -> let as = aplica m ent in if (null as) then aplica n ent else as)
32 Ejemplo: analizador más largo, número más largoreiter :: Analiz a -> Analiz [a] reiter m = do a <- m x <- reiter m return (a:x) !* return [] número' = do a <- dígito x <- reiter dígito return (aInt (a:x)) where chrAInt :: Char -> Int chrAInt c = ord c - ord '0' aInt :: [Char] -> Int aInt = foldl1 (\x y -> 10*x + y) . map chrAInt Main> aplica número' "123letras" [(123,"letras")] :: [(Int,Estado)]
33 Ejemplo: leer cadena de espacios, token sin espaciosespacios :: Analiz String espacios = do a <- literal ' ' x <- reiter (literal ' ') return (a:x) !* return "" token :: String -> Analiz String token xs = do _ <- espacios tk <- token' xs return tk where token' [] = return [] token' (x:xs)= do c <- elemento !> (== x) cs <- token' xs return (c:cs) Main> aplica (token "let") " let x=1 in 2*x" [("let"," x=1 in 2*x")] :: [([Char],Estado)]
34 Un analizador para términosGramática -- term ::= constante | ( term + term ) | ( term / term ) data Term = Const Int | Term :/: Term | Term :+: Term deriving Show anaConst :: Analiz Term anaConst = do a <- número return (Const a)
35 Un analizador para términosanaSum' :: Analiz Term anaSum' = do _ <- literal '(' u <- term' _ <- literal '+' v <- term' _ <- literal ')' return (u :+: v) anaDiv' :: Analiz Term anaDiv' = do _ <- literal '/' return (u :/: v)
36 Un analizador para términosAnalizador más genérico con delimitadores paren :: Analiz a -> Analiz b -> Analiz c -> Analiz b paren abre m cierra = do abre x <- m cierra return x anaSum = paren (literal '(') (do { u <- term ; literal '+' ; v <- term ; return (u :+: v)}) (literal ')') anaDiv = paren (literal '(') ; literal '/' ; return (u :/: v)})
37 Un analizador para términosanaOp :: Analiz (Term -> Term -> Term) anaOp = (do {literal '+'; return (:+:)}) !* (do {literal '/'; return (:/:)}) anaExpr :: Analiz Term anaExpr = do u <- term o <- anaOp v <- term return (o u v) anaSD :: Analiz Term anaSD = paren (literal '(') anaExpr (literal ')') term = anaConst !+ anaSD
38 Ruegos y preguntas