formateador y analizador de textos daniel montoya ramos eva maría garcía garcía loli burgueño...
TRANSCRIPT
1
Formateador y Analizador de textos
Daniel Montoya RamosEva María García GarcíaLoli Burgueño Caballero
2
Formateador
Analizador
Analizador monádico
Índice
3
Formateador de textos
4
Analizador de textos
5
Introducción
› Show
› Read
Analizador de textos
6
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 (())
Analizador de textos
7
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
Analizador de textos
8
ReadS a› Tipo polimórfico para analizadores que
devuelven valores de tipo atype 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.
Analizador de textos
9
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.
Analizador de textos
10
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
Analizador de textos
11
rSatrSat :: (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.
Analizador de textos
12
Metasímbolo alternativa. Analizador -+-
infixl 5 -+-(-+-) :: ReadS a -> ReadS a -> ReadS ap1 -+- 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
Analizador de textos
13
Analizador >>>infixr 6 >>>(>>>) :: ReadS a -> (a -> ReadS b) -> ReadS bp >>> 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.
Analizador de textos
14
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
Analizador de textos
15
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
Analizador de textos
16
Metasímbolo de opción (?)
(?) :: ReadS a -> a -> ReadS a
› Argumentos:1. Primer argumento: Analizador p2. Segundo argumento
› Si p tiene éxito sobre la cadena de entrada devuelve dicho resultado
› Si p falla devuelve el segundo argumento.
Analizador de textos
17
Reconocer números enteros› Ideas generales
(rChar '+' -+- rChar '-') “<cadena>”1. <cadena> empieza por ‘+’2. <cadena> empieza por ‘-’3. <cadena> empieza por un dígito
((rChar '+' -+- rChar '-') ? ‘+’) “<cadena>” Problema resuelto Queda reconocer el numero natural
Analizador de textos
18
Lista de números enteros
rListaEnteros :: ReadS [Integer]
› Devuelve un analizador de enteros› Es fácil de definir a partir de los
operadores anteriores.
Analizador de textos
19
Analizadores Monádicos
20
data Analiz a = AN (Estado -> [(a,Estado)])
type Estado = String
Representación
21
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)])
Funciones
22
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])
Secuenciación
23
Elemento neutro de la secuenciación
› (>>=f).return = f› (>>= return) = id
Asociatividad de la secuenciación
› (>>=g).(>>=f) = (>>=((>>=g).f))
Propiedades de las Mónadas
24
instance MonadPlus Analiz where mplus (AN p) (AN q) = AN (\ent -> p
ent ++ q ent) mzero = AN (\ent -> [] )
(!+) :: Analiz a -> Analiz a -> Analiz a (!+) = mplus
Alternancia
25
unoODosElementos :: 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)]
Ejemplo: Analizador que lee uno o dos elementos
26
Asociativa(m !+ n) !+ o = m !+ (n!+o)
Distributiva(m !+ n) >>= o = (m>>=o) !+
(n!+o) Elemento neutro
mzero !+ m = mm!+ mzero = m
Propiedades de la alternancia
27
(!>) :: Analiz a -> (a -> Bool) -> Analiz a
k !> p = do a <- k
if p a then return a else mzero
Filtros
28
letra :: 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)]
Ejemplos: analizadores de letra, dígito o ambos
29
iter :: Analiz a -> Analiz [a] iter m = do x <- m xs <- iter m return (x:xs) !+ return []
Iteración
30
nú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)]
Ejemplo: analizar un número
31
(!*) :: Analiz a -> Analiz a -> Analiz a m !* n = AN (\ent -> let as = aplica m ent in if (null as) then aplica n ent else as)
Elección parcial
32
reiter :: 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)]
Ejemplo: analizador más largo, número más largo
33
espacios :: 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)]
Ejemplo: leer cadena de espacios, token sin espacios
34
Gramá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)
Un analizador para términos
35
anaSum' :: Analiz Term anaSum' = do
_ <- literal '(' u <- term' _ <- literal '+' v <- term' _ <- literal ')' return (u :+: v)
anaDiv' :: Analiz Term anaDiv' = do
_ <- literal '(' u <- term' _ <- literal '/' v <- term' _ <- literal ')' return (u :/: v)
Un analizador para términos
36
Analizador 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 '(') (do {
u <- term ; literal '/' ; v <- term ; return (u :/: v)}) (literal ')')
Un analizador para términos
37
anaOp :: 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
Un analizador para términos
38
Ruegos y preguntas