Monadické parsování (Parsec) a nástroje
IB016 Seminář z funkcionálního programování
Mnoho autorů napříč věky
Fakulta informatiky, Masarykova univerzita
Jaro 2022
IB016: Cvičení 03 Jaro 2022 1 / 21
HLint
Nástroj hlásící návrhy na zlepšení kódu („linter“)
samostatný balík z Hackage, nutno doinstalovat
často dostupný přímo v repozitářích distribuce
FI: na nymfách nainstalovaný z repozitářů Ubuntu
více podrobností v samostatném návodu v ISu
aisa$ cabal new-install hlint
hlint [--hint soubor_definic_navíc ] zdroják
možno integrovat přímo do GHCi, vizte návod v ISu
soubor s dodatečnými definicemi v ISu
IB016: Cvičení 03 Jaro 2022 2 / 21
Dokumentace v Haskellu: Haddock
-- | The 'square' function squares an integer.
square :: Int -> Int
square x = x * x
data T a b
      = C1 a b   -- ^ info about constructor 'C1'
      | C2 a b   -- ^ info about constructor 'C2'
syntaxe komentářů pro automatické zpracování
generování HTML dokumentace programem haddock
haddock file.hs --html -o doc
na FI: součástí modulu ghc
více informací v oficiální dokumentaci
IB016: Cvičení 03 Jaro 2022 3 / 21
Parsování: Regulární výrazy
Haskell má několik balíků pro práci s regulárními výrazy:
většina se nachází v modulech Text.Regex.*
„základní“ posixová implementace v balíku regex-posix
pěkný přehled možností různých balíku najdete třeba na
https://wiki.haskell.org/Regular_expressions
Vesměs stejný princip jako u jiných jazyků.
IB016: Cvičení 03 Jaro 2022 4 / 21
Monadické parsování - Parsec
IB016: Cvičení 03 Jaro 2022 5 / 21
Syntaktické analyzátory (parsery)
Základní regulární výrazy často nestačí.
→ využijeme syntaktické analyzátory (parsery)
lexikální analyzátor Alex + syntaktický analyzátor Happy
(podobné kombinaci lex/flex + bison/yacc)
Parsec – knihovna založena na parserových kombinátorech,
zvládá i tvorbu lexikálních analyzátorů, přívětivější chybové
hlášky
Attoparsec – další kombinátorová knihovna, rychlejší než
Parsec – hlavně pro síťové protokoly a komplikované
textové/binární formáty, chybí transformátor
A mnoho dalších – Polyparse, Megaparsec, GLL...
IB016: Cvičení 03 Jaro 2022 6 / 21
Parsec
Myšlenka:
definujme parser pomocí většího množství
menších/jednodušších parserů
IB016: Cvičení 03 Jaro 2022 7 / 21
Parsec
Myšlenka:
definujme parser pomocí většího množství
menších/jednodušších parserů
Technicky:
balík parsec (není součástí standardní distribuce)
nejpoužívanější funkce přímo v modulu Text.Parsec
pro naše účely hlavně funkce z modulů Text.Parsec.Char a
Text.Parsec.Combinators
pro zjednodušení typování importujte i modul
Text.Parsec.String
IB016: Cvičení 03 Jaro 2022 7 / 21
Datový typ Parser
myParser :: Parser a
parser, který zpracuje vstup na hodnotu typu a
instance pro třídy Functor, Applicative i Monad
ve skutečnosti je to pouze typové synonymum pro obecnější
parser, viz později
IB016: Cvičení 03 Jaro 2022 8 / 21
Aplikace parserů
Na aplikaci parserů používáme specializované funkce:1
parse :: Parser a -> SourceName -> String
-> Either ParseError a
parse p name input spustí parser p na vstupu input, name
se bude používat pouze na identifikaci v chybových hláškách
výsledkem je buď zparsovaná hodnota, nebo chyba typu
ParseError
1
typ je ve skutečnosti obecnější, viz později
IB016: Cvičení 03 Jaro 2022 9 / 21
Aplikace parserů
Na aplikaci parserů používáme specializované funkce:1
parse :: Parser a -> SourceName -> String
-> Either ParseError a
parse p name input spustí parser p na vstupu input, name
se bude používat pouze na identifikaci v chybových hláškách
výsledkem je buď zparsovaná hodnota, nebo chyba typu
ParseError
parseFromFile :: Parser a -> String
-> IO (Either ParseError a)
parseFromFile p f spustí parser p na obsahu souboru f
1
typ je ve skutečnosti obecnější, viz později
IB016: Cvičení 03 Jaro 2022 9 / 21
Základní znakový parser
satisfy :: (Char -> Bool) -> Parser Char
parser satisfy p uspěje, jestliže načtený znak splňuje zadaný
predikát (pak vrací tento znak)
IB016: Cvičení 03 Jaro 2022 10 / 21
Základní znakový parser
satisfy :: (Char -> Bool) -> Parser Char
parser satisfy p uspěje, jestliže načtený znak splňuje zadaný
predikát (pak vrací tento znak)
Existující užitečné parsery:
char :: Char -> Parser Char
digit, letter, anyChar, space :: Parser Char
oneOf, noneOf :: [Char] -> Parser Char
IB016: Cvičení 03 Jaro 2022 10 / 21
Základní znakový parser
satisfy :: (Char -> Bool) -> Parser Char
parser satisfy p uspěje, jestliže načtený znak splňuje zadaný
predikát (pak vrací tento znak)
Existující užitečné parsery:
char :: Char -> Parser Char
digit, letter, anyChar, space :: Parser Char
oneOf, noneOf :: [Char] -> Parser Char
Příklad: 02 Mar 2022
Které znakové parsery použít?
Jak napsat znakové parsery pomocí satisfy?
IB016: Cvičení 03 Jaro 2022 10 / 21
Funkce a operátory z instancí
Zamyšlení: Jak budou fungovat instance Functor, Monad?
fmap :: (a -> b) -> Parser a -> Parser b
fmap (: "!") (char 'A')
IB016: Cvičení 03 Jaro 2022 11 / 21
Funkce a operátory z instancí
Zamyšlení: Jak budou fungovat instance Functor, Monad?
fmap :: (a -> b) -> Parser a -> Parser b
fmap (: "!") (char 'A')
fmap aplikuje funkci na vrácenou hodnotu
pure :: a -> Parser a
pure 42
IB016: Cvičení 03 Jaro 2022 11 / 21
Funkce a operátory z instancí
Zamyšlení: Jak budou fungovat instance Functor, Monad?
fmap :: (a -> b) -> Parser a -> Parser b
fmap (: "!") (char 'A')
fmap aplikuje funkci na vrácenou hodnotu
pure :: a -> Parser a
pure 42
pure x nic nečte a vrátí hodnotu x
twoChars = do
char1 <- anyChar
char2 <- anyChar
pure [char1, char2]
IB016: Cvičení 03 Jaro 2022 11 / 21
Funkce a operátory z instancí
Zamyšlení: Jak budou fungovat instance Functor, Monad?
fmap :: (a -> b) -> Parser a -> Parser b
fmap (: "!") (char 'A')
fmap aplikuje funkci na vrácenou hodnotu
pure :: a -> Parser a
pure 42
pure x nic nečte a vrátí hodnotu x
twoChars = do
char1 <- anyChar
char2 <- anyChar
pure [char1, char2]
operátor >>= předá zparsovanou hodnotu zleva doprava
IB016: Cvičení 03 Jaro 2022 11 / 21
Další užitečné operátory
>> spaces >> identifier
IB016: Cvičení 03 Jaro 2022 12 / 21
Další užitečné operátory
>> spaces >> identifier
liftAX liftA2 (+) number number
IB016: Cvičení 03 Jaro 2022 12 / 21
Další užitečné operátory
>> spaces >> identifier
liftAX liftA2 (+) number number
<$> (++ "!") <$> greeting
IB016: Cvičení 03 Jaro 2022 12 / 21
Další užitečné operátory
>> spaces >> identifier
liftAX liftA2 (+) number number
<$> (++ "!") <$> greeting
<$ "greeting here" <$ greeting
IB016: Cvičení 03 Jaro 2022 12 / 21
Další užitečné operátory
>> spaces >> identifier
liftAX liftA2 (+) number number
<$> (++ "!") <$> greeting
<$ "greeting here" <$ greeting
<*> (,) <$> key <*> value
IB016: Cvičení 03 Jaro 2022 12 / 21
Další užitečné operátory
>> spaces >> identifier
liftAX liftA2 (+) number number
<$> (++ "!") <$> greeting
<$ "greeting here" <$ greeting
<*> (,) <$> key <*> value
<* string "Hello" <* spaces <* name
IB016: Cvičení 03 Jaro 2022 12 / 21
Další užitečné operátory
>> spaces >> identifier
liftAX liftA2 (+) number number
<$> (++ "!") <$> greeting
<$ "greeting here" <$ greeting
<*> (,) <$> key <*> value
<* string "Hello" <* spaces <* name
*> string "Hello" *> spaces *> name
IB016: Cvičení 03 Jaro 2022 12 / 21
Sekvence parserů
Existující užitečné parsery:
string :: String -> Parser String
between :: Parser open -> Parser close
-> Parser a -> Parser a
count :: Int -> Parser a -> Parser [a]
many, many1 :: Parser a -> Parser [a]
sepBy, sepBy1 :: Parser a -> Parser sep -> Parser [a]
choice :: [Parsec a] -> Parsec a
IB016: Cvičení 03 Jaro 2022 13 / 21
Sekvence parserů
Existující užitečné parsery:
string :: String -> Parser String
between :: Parser open -> Parser close
-> Parser a -> Parser a
count :: Int -> Parser a -> Parser [a]
many, many1 :: Parser a -> Parser [a]
sepBy, sepBy1 :: Parser a -> Parser sep -> Parser [a]
choice :: [Parsec a] -> Parsec a
Kolik vstupu spracuje many?
parse (many digit) "input name" "hello"
Jak zparsujeme datum a které parsery použijeme?
Například: 02 Mar 2022
IB016: Cvičení 03 Jaro 2022 13 / 21
Příklad kombinace parserů v do-bloku
Příklad: 02 Mar 2022
data Date = Date { dDay :: Int, dMonth :: Month
, dYear :: Int }
IB016: Cvičení 03 Jaro 2022 14 / 21
Příklad kombinace parserů v do-bloku
Příklad: 02 Mar 2022
data Date = Date { dDay :: Int, dMonth :: Month
, dYear :: Int }
dateParser :: Parser Date
dateParser = do
day <- read <$> count 2 digit
space
month <- monthParser
space
year <- read <$> count 4 digit
pure $ Date day month year
IB016: Cvičení 03 Jaro 2022 14 / 21
Příklad kombinace parserů v do-bloku
Příklad: 02 Mar 2022
data Date = Date { dDay :: Int, dMonth :: Month
, dYear :: Int }
dateParser :: Parser Date
dateParser = do
day <- read <$> count 2 digit
space
month <- monthParser
space
year <- read <$> count 4 digit
pure $ Date day month year
Jak bude vypadat parser monthParser
Jaká má parser omezení?
IB016: Cvičení 03 Jaro 2022 14 / 21
Příklad kombinace parserů v do-bloku – pokračování
Příklad: 02 Mar 2022
data Month = Jan | Feb | Mar | Apr | May | Jun
| Jul | Aug | Sep | Oct | Nov | Dec
monthParser :: Parser Month
monthParser = choice [ string "Jan" >> pure Jan
, string "Feb" $> Feb
, Mar <$ string "Mar"
, string "Apr" *> pure Apr
, pure May <* string "May"
, ...
]
IB016: Cvičení 03 Jaro 2022 15 / 21
Příklad kombinace parserů v do-bloku – pokračování
Příklad: 02 Mar 2022
data Month = Jan | Feb | Mar | Apr | May | Jun
| Jul | Aug | Sep | Oct | Nov | Dec
monthParser :: Parser Month
monthParser = choice [ string "Jan" >> pure Jan
, string "Feb" $> Feb
, Mar <$ string "Mar"
, string "Apr" *> pure Apr
, pure May <* string "May"
, ...
]
Ve vlastním kódu si vyberte jen jeden styl a buďte
konzistentní!
IB016: Cvičení 03 Jaro 2022 15 / 21
Příklad kombinace parserů v do-bloku – pokračování
Příklad: 02 Mar 2022
data Month = Jan | Feb | Mar | Apr | May | Jun
| Jul | Aug | Sep | Oct | Nov | Dec
monthParser :: Parser Month
monthParser = choice [ string "Jan" >> pure Jan
, string "Feb" $> Feb
, Mar <$ string "Mar"
, string "Apr" *> pure Apr
, pure May <* string "May"
, ...
]
Ve vlastním kódu si vyberte jen jeden styl a buďte
konzistentní!
Je tento parser korektní?
IB016: Cvičení 03 Jaro 2022 15 / 21
Alternativa parserů
<|> :: Parser a -> Parser a -> Parser a
p <|> q se pokusí nejdříve použít parser p a jestli uspěje,
vrátí jeho výsledek
jestli p selže bez toho, aby spotřeboval nějaký vstup, použije
se parser q
Příklad: string "spring" <|> string "autumn"
IB016: Cvičení 03 Jaro 2022 16 / 21
Alternativa parserů
<|> :: Parser a -> Parser a -> Parser a
p <|> q se pokusí nejdříve použít parser p a jestli uspěje,
vrátí jeho výsledek
jestli p selže bez toho, aby spotřeboval nějaký vstup, použije
se parser q
Příklad: string "spring" <|> string "autumn"
Existující užitečné parsery:
option :: a -> Parser a -> Parser a
optionMaybe :: Parser a -> Parser (Maybe a)
optional :: Parser a -> Parser ()
IB016: Cvičení 03 Jaro 2022 16 / 21
Alternativa parserů
season = string "spring" <|> string "summer"
IB016: Cvičení 03 Jaro 2022 17 / 21
Alternativa parserů
season = string "spring" <|> string "summer"
season na řetězci "summer" selže – levá alternativa sice selhala,
ale spotřebovala vstup!
IB016: Cvičení 03 Jaro 2022 17 / 21
Alternativa parserů
season = string "spring" <|> string "summer"
season na řetězci "summer" selže – levá alternativa sice selhala,
ale spotřebovala vstup!
try :: Parser a -> Parser a
try p se chová stejně jako parser p, ale když p selže, vrátí se
ve vstupu, jako by žádný nebyl parserem p spotřebován
IB016: Cvičení 03 Jaro 2022 17 / 21
Alternativa parserů
season = string "spring" <|> string "summer"
season na řetězci "summer" selže – levá alternativa sice selhala,
ale spotřebovala vstup!
try :: Parser a -> Parser a
try p se chová stejně jako parser p, ale když p selže, vrátí se
ve vstupu, jako by žádný nebyl parserem p spotřebován
Pozor: používání try zvyšuje složitost parsování! (Ale na
druhou stranu nám umožňuje mít libovolný lookahead.)
IB016: Cvičení 03 Jaro 2022 17 / 21
Příklad kombinace parserů v do-bloku – dokončení
Příklad: 02 Mar 2022
data Month = Jan | Feb | Mar | Apr | May | Jun
| Jul | Aug | Sep | Oct | Nov | Dec
monthParser :: Parser Month
monthParser = choice [ try $ Jan <$ string "Jan"
, Feb <$ string "Feb"
, try $ Mar <$ string "Mar"
, try $ Apr <$ string "Apr"
, May <$ string "May"
, ...
]
try není potřeba všude
IB016: Cvičení 03 Jaro 2022 18 / 21
Užitečné chybové hlášky
Nevýhoda kombinátorových parserů: Ladění není snadné.
(Který parser selhal?)
IB016: Cvičení 03 Jaro 2022 19 / 21
Užitečné chybové hlášky
Nevýhoda kombinátorových parserů: Ladění není snadné.
(Který parser selhal?)
Zlepšení: Doplňme do parseru popis, co dělá:
"your input:" (line 1, column 1):
unexpected "L"
expecting digit
IB016: Cvičení 03 Jaro 2022 19 / 21
Užitečné chybové hlášky
Nevýhoda kombinátorových parserů: Ladění není snadné.
(Který parser selhal?)
Zlepšení: Doplňme do parseru popis, co dělá:
"your input:" (line 1, column 1):
unexpected "L"
expecting digit
(<?>) :: Parser a -> String -> Parser a
mění chybovou hlášku („expected“)
obzvlášť vhodné pro alternativy nebo try
parser nesmí spotřebovat vstup
IB016: Cvičení 03 Jaro 2022 19 / 21
Ve skutečnosti je to obecnější...
Typ Parser a je pouze speciální případ parseru:
type Parser a = Parsec String () a
type Parsec s u a = ParsecT s u Identity a
ParsecT s u m a představuje parser, který
zpracovává typ s
udržuje si stav typu u
pracuje v monádě m
vrací výsledek typu a
IB016: Cvičení 03 Jaro 2022 20 / 21
Ve skutečnosti je to obecnější...
Typ Parser a je pouze speciální případ parseru:
type Parser a = Parsec String () a
type Parsec s u a = ParsecT s u Identity a
ParsecT s u m a představuje parser, který
zpracovává typ s
udržuje si stav typu u
pracuje v monádě m
vrací výsledek typu a
Typ funkce parse je pak následovný:
runParser :: Stream s Identity t =>
Parsec s u a -> u -> SourceName -> s
-> Either ParseError a
IB016: Cvičení 03 Jaro 2022 20 / 21
Příklady k procvičení
Napište parser pro:
datum – "2015-04-14"
rozpoznaný řetězec číslic můžete konvertovat funkcí read,
výsledek ať je vámi definovaného typu Date, rozsah
kontrolovat nemusíte
čísla která můžou mít desetinnou část – "12", "12.54"
seznam čísel – "[ 12, 12.54, 42, 66, 3.14 ]"
využijte parser z předchozího cvičení
výraz s přirozenými čísly a operacemi – (2+5)*2
precedenci operátorů neřešte, parser ať výraz rovnou
vyhodnotí, tj. ať je typu Parser Int
IB016: Cvičení 03 Jaro 2022 21 / 21