Análise Sintática
Idéia inicial
parse :: String -> Int
parse "42" == 42
Análise Sintática
Múltiplas interpretações
type Parser = ...
parse :: Parser -> String -> Int
dec, hex :: Parser
parse dec "42" == 42
parse hex "2A" == 42
Análise Sintática
Falhas
type Parser = ...
parse :: Parser -> String -> Maybe Int
dec, hex :: Parser
parse dec "42" == Just 42
parse dec "2A" == Nothing
Análise Sintática
Parametrizando o resultado
type Parser a = ...
parse :: Parser a -> String -> Maybe a
dec :: Parser Int
chr :: Parser Char
parse dec "7" == Just 7
parse chr "7" == Just '7'
Análise Sintática
Parcialidade
type Parser a = ...
parse :: Parser a -> String -> Maybe (a, String)
dec, hex :: Parser Int
parse hex "42" == Just (42, "")
parse dec "2A" == Just (2, "A")
Análise Sintática
Combinadores
type Parser a = ...
parse :: Parser a -> String -> Maybe (a, String)
pair :: Parser a -> Parser b -> Parser (a, b)
dec :: Parser Int
chr :: Parser Char
parse (pair dec chr) "2A" == Maybe ((2, 'A'), "")
parse (pair chr dec) "2A" == Nothing
parse (pair dec chr) "42" == ???
Análise Sintática
Ambiguidade
type Parser a = ...
parse :: Parser a -> String -> [(a, String)]
pair :: Parser a -> Parser b -> Parser (a, b)
dec, hex :: Parser Int
chr :: Parser Char
parse dec "42" == [(4,"2"), (42,"")]
parse dec "2A" == [(2,"A")]
parse hex "42" == [(4,"2"), (66,"")]
parse hex "2A" == [(2,"A"), (42,"")]
parse (pair dec chr) "2A" == [((2, 'A'), "")]
parse (pair dec chr) "42" == [((4, '2'), "")]
Análise Sintática
Ambiguidade
[a] ≅ Maybe (a, [a])
Semântica Denotacional
Analisadores Sintáticos como Funções
type Parser a = String -> [(a, String)]
parse :: Parser a -> String -> [(a, String)]
parse p = p
Semântica Denotacional
Combinadores
pair p1 p2 s = concatMap p2' (p1 s)
where p2' (a, s') = concatMap (\(b, s'') -> [((a, b), s'')]) (p2 s')
pair p1 p2 s = bind p1 (\a -> bind p2 (\b -> unit (a, b)))
bind p f = \s -> concatMap (\(a, s') -> f a s') (p s)
unit x = \s -> [(x, s)]
Semântica Denotacional
Sintaticamente mais agradável
pair p1 p2 s = bind p1 (\a -> bind p2 (\b -> unit (a, b)))
pair p1 p2 s = p1 `bind` \a ->
p2 `bind` \b ->
unit (a, b)
Mônadas
Uma estrutura algébrica para analisadores sintáticos
class Monad m where
(>>=) :: m a -> (a -> m b) -> m b
return :: a -> m a
instance Monad Parser where
p >>= f = \s -> concatMap (\(a, s') -> f a s') (p s)
return x = \s -> [(x, s)]
Mônadas
Uma estrutura algébrica para analisadores sintáticos
class Monad m => MonadPlus m where
mzero :: m a
mplus :: m a -> m a -> m a
instance MonadPlus Parser where
mzero = \s -> []
mplus p1 p2 = \s -> p1 s ++ p2 s
Analisadores Sintáticos: Exemplos
chr :: Parser Char
chr [] = []
chr (c:cs) = [(c, cs)]
dec :: Parser Int
dec = many1 digit
where digit = do c <- chr
guard (isDigit c)
return (digitToInt c)
many1 p = do x <- p
xs <- many p
return (x:xs)
many p = more `mplus` zero
where zero = return []
more = do x <- p
xs <- many p
return (x:xs)
©Fritz Ruehr, Willamette University