Formateador y Analizador
de textos
Daniel Montoya Ramos
Eva María García García
Loli Burgueño Caballero
1
Índice
Formateador
Analizador
Analizador monádico
2
Formateador de textos
3
Analizador de textos
4
Analizador de textos

Introducción
› Show
› Read
5
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 (())
6
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
7
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.
8
Analizador de textos
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.

9
Analizador de textos

rCHar
rChar :: Char -> ReadS Char
rChar 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
10
Analizador de textos
rSat
rSat :: (Char -> Bool) -> ReadS Char
rSat 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.
11
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
12
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.
13
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
14
Analizador 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
15
Analizador de textos

Metasímbolo de opción (?)
(?) :: ReadS a -> a -> ReadS a
› Argumentos:
1. Primer argumento: Analizador p
2. Segundo argumento
› Si p tiene éxito sobre la cadena de
›
entrada devuelve dicho resultado
Si p falla devuelve el segundo argumento.
16
Analizador de textos

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
17
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.
18
Analizadores Monádicos
19
Representación
data Analiz a = AN (Estado -> [(a,Estado)])
type Estado
= String
20
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)])
21
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])

22
Propiedades de las Mónadas

Elemento neutro de la secuenciación
› (>>=f).return
› (>>= return)

=f
= id
Asociatividad de la secuenciación
› (>>=g).(>>=f)
= (>>=((>>=g).f))
23
Alternancia
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

24
Ejemplo: Analizador que lee
uno o dos elementos
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)]

25
Propiedades de la alternancia
Asociativa
(m !+ n) !+ o = m !+ (n!+o)
 Distributiva
(m !+ n) >>= o = (m>>=o) !+ (n!+o)
 Elemento neutro
mzero !+ m = m
m!+ mzero = m

26
Filtros

(!>) :: Analiz a -> (a -> Bool) -> Analiz a

k !> p = do
a <- k
if p a then return a else mzero
27
Ejemplos: analizadores de letra,
dígito o ambos


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)]
28
Iteración
iter :: Analiz a -> Analiz [a]
 iter m = do
x <- m
xs <- iter m
return (x:xs)
!+ return []

29
Ejemplo: analizar un número


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)]
30
Elección parcial
(!*) :: 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)

31
Ejemplo: analizador más largo,
número más largo


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)]
32
Ejemplo: leer cadena de
espacios, token sin espacios


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)]
33
Un analizador para términos




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)

34
Un analizador para términos




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)
35
Un analizador para términos

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 ')')
36
Un analizador para términos




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

37
Ruegos y preguntas
38
Descargar

Analizadores sintácticos en Haskell