Combinadores Monádicos de Análise Sintática

Daniel Yokomizo / @dyokomizo

http://dyokomizo.github.io/talks

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

Como lembrar disso tudo?

A Parser for Things / is a function from Strings / to Lists of Pairs / of Things and Strings! ©Fritz Ruehr, Willamette University

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)

Referências