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