Parseri

Parser je funkcija koja od niza nekih simbola generiše vrednosti. Najčešće parseri služe da se niske (liste karaktera) transformišu u neke vrednosti poput brojeva ili struktura podataka.

ghci> read "39.5" :: Float
39.5
ghci> read "[True, False]" :: [Bool]
[True, False]

Parsiranje je generalno težak problem. Stoga ne čudi što je tokom istorije računarstva razvijeno mnogo teorije o parserima i konkretnim tehnikama za njihovo konstruisanje. Svakako, teorija o parserima prevazilazi obime ove knjige, ali možemo ovde prikazati jednu tehniku za konstrukciju parsera. U pitanju su takozvani parser kombinatori koji su zapravo funkcije višeg reda kojima se jednostavniji parseri kombinuju u složenije.

Tip parsera

Parsiranjem bi trebalo nisku (koja je lista karaktera) pretvoriti u neku vrednost tipa T. Na primer, parser celobrojnih brojeva bi trebalo da nisku transformiše u vrednost tipa Int, pa bi tip ovakvog parsera bio String -> Int. Parser logičkih lista bi trebalo da nisku pretvori u vrednost tipa [Bool], pa bi tip ovakvog parsera bio String -> [Bool]. Stoga ćemo definisati novi (apstraktni) tip Parser a = String -> a, koji može predstaviti parsere za vrednosti bilo kog tipa. Međutim, kroz ovaj novi tip je neophodno obezbediti još par stvari.

1. Prvo, nećemo svaki parser konstruisati kao jedinstvenu funkciju. Složenije parsere ćemo konstruisati kombinovanjem manjih funkcija. Svaka od tih funkcija parsiraće jedan karakterističan deo niske (Na primer, parser Float vrednosti može biti sačinjen od tri parsera: prvog koji parsira ceo deo, drugog koji parsira tačku, i trećeg koji parsira razlomljeni deo. Slično, parser logičkih nizova može biti sačinjen od parsera koji parsira zagrade, parsera za literale logičke vrednosti, parsera za zarez, parsera za beline, itd...). Parsere ćemo kombinovati tako što će svaki naredni parser, parsirati ono "što ostane" nakon pokretanja prethodnih parsera. Stoga jedan parser vrednosti T neće vraćati samo vrednost tipa T, već uređen par tipa (T, String), gde druga koordinata označava ostatak niske koja se parsira.
2. Drugo, ne možemo očekivati da će svako parsiranje biti uspešno. Iz niske "Hi!" ne možemo parsirati broj niti logičku listu. Zbog toga, parser će zapravo vratiti možda-vrednost Maybe (T, String). Ako je parser uspeo, rezultat je oblika Just (x, s) za neku nisku s i vrednost x :: T. U suprotnom, parser vraća Nothing.

Uzimajući prethodno u obzir, stižemo do definicije tipa

newtype Parser a = P (String -> Maybe (a, String))

Sa navedenom definicijom tipa biće zgodna funkcija koja "pokreće" parser nad niskom:

parsiraj :: Parser a -> String -> Maybe (a, String)
parsiraj (P p) s = p s 

Kreirajmo parser koji parsira jedno slovo iz niske. Taj parser ima tip Parser Char. Sa konstruktorom P obuhvatićemo funkciju koja uzima jedno slovo sa početka niske. Ako je niska prazna, parser će vratiti Nothing.

slovo :: Parser Char
slovo = P f
    where
        f [] = Nothing
        f (x:xs) = Just (x, xs)

Testiranje parsera je veoma jednostavno (i veoma čitljivo!):

ghci> parsiraj slovo "Hello world!"
Just ('H', "ello world!")
ghci> parsiraj slovo ""
Nothing

Nakon slova, najprirodnije je kreirati parser cifre. Parser cifre treba da nam vrati numeričku vrednost cifre, ako ulazna niska počinje sa cifrom.

cifra :: Parser Int
cifra = P f where
    f []     = Nothing
    f (x:xs) =
        if x `elem` ['1' .. '9']
        then Just (romEnum x - fromEnum '0', xs)
        else Nothing

ghci> parsiraj cifra "9abc"
Just (0, "abc")
ghci> parsiraj cifra "1234"
Just (1, "234")
ghci> parsiraj cifra "Hello!"
Nothing

Zadatak 1. Kreirati funkciju maloSlovo :: Parser Char koja parsira samo mala latinična slova (tj. karakter iz raspona ['a' .. 'w']).

Često je zgodno da kreiramo funkciju koja kreira nekakav parser na osnovu prosleđenih argumenata. Parser simbol :: Char -> Parser Char je primer takve funkcije. Funkcija simbol uzima jedan karakter i vraća parser koji parsira isključivo taj karakter, a za sve ostale karaktere podbacuje.

simbol :: Char -> Parser Char
simbol c = P $ \s -> case s of
    x:xs -> if x == c then Just (c, xs) else Nothing
    _   -> Nothing

ghci> parsiraj (simbol 'H') "Hello!"
Just ('H', "ello!")
ghci> parsiraj (simbol 'A') "Hello!"
Nothing

Zadatak 2. Kreirati funkciju niska :: String -> Parser String koja na osnovu niske s kreira parser koji parsira isključivo s.

Kombinatori

Parseri koje smo do sad konstruisali su bili "atomički". Za kreiranje složenijih parsera, poput onih koji parsiraju čitav kôd nekog programskog jezika, potrebno je jednostavnije parsere ukombinovati u složenije. Takvo kombinovanje vršimo pomoću funkcija koje nazivamo parser kombinatori. Parser kombinatori o postojećih parsera prave nove parsere.

Verovatno najjednostavniji, netrivijalni, parser kombinator je kombinator koji na uspešan rezultat nekog parsera primenjuje datu funkciju f:

primeni :: (a -> b) -> Parser a -> Parser b
primeni f p = P $ 
        \s -> case p s of
            Just (x, s') -> Just (f x, s')
            Nothing -> Nothing

ghci> kvadrat = primeni (\x -> x*x) cifra
ghci> kvadrat "3"
Just (9, "")

Veoma koristan je parser kombinator ili, koji uzima dva parsera i kreira novi parser koji pokušava da pokrene prvi parser a slučaju neuspeha i drugi parser. Ovakav kombinator ima sasvim jednostavnu definiciju:

ili :: Parser a -> Parser a -> Parser a
ili p1 p2 = P $ 
        \s -> case parsiraj p1 s of
            Just (v, s') -> Just (v, s')
            Nothing -> parsiraj p2 s

ghci> iksoks = ili (simbol 'x') (simbol 'o')
ghci> parsiraj iksoks "xoxox"
Just ("x","oxox")
ghci> parsiraj iksoks "aaaa"
Nothing

Zadatak 3. Napisati parser koji koji simbole x i o parsira kao logičke vrednosti True i False.

Do sada smo parsirali samo jedinstvene vrednosti. Sada ćemo konstruisati parser kombinator tipa Parser a -> Parser [a] koji parsira listu vrednosti istog tipa, tako što pokreće prosleđeni parser dokle god može. Nazovimo ovaj kombinator više jer rezultat (može) sadržati više vrednosti istog tipa. Definicija kombinatora mora sadržati rekurzivne pozive, što ćemo uspostaviti sa pomoćnom rekurzivnom funkcijom r:

više :: Parser a -> Parser [a]
više (P f) = P $ \s -> (Just r s)
    where
        r [] = []
        r xs = case f xs of
            Just (v, xs') -> v : r xs'
            Nothing       -> []

Zadatak 4. Konstruisati kombinator zatim :: Parser a -> Parser b -> Parser (a , b), koji pokreće prvi a zatim i drugi parser, i vraća uređen par rezultat parsiranja.

Sada kada smo se upoznali sa najvažnijim parser kombinatorima, možemo lako konstruisati jedan veoma koristan parser. U pitanju je parser celobrojnih vrednosti. Uspešni pokretanjem parsere više cifra dobijamo vrednost tipa [Int] koja predstavlja cifre sa početka ulazne niske. Stoga je dovoljno napisati funkciju cifreUBroj :: [Int] -> Int koja će niz cifara svesti na broj. Naravno, ovde nam je potreban rekurzivan prolazak kroz listu, pri čemu ćemo čuvati "trenutnu vrednost" koja se pri svakom koraku uvećava 10 puta (tj za jedno decimalno mesto). Direktna implementacija¹ izgleda ovako:

cifreUBroj :: [Int] -> Int
cifreUBroj xs =  r 0 xs where
    r v []     = v
    r v (x:xs) = r (10 * v + x) xs

Sada, parser broj :: Parser Int može da se definiše kao broj = primeni cifreUBroj $ više cifra.

ghci> parsiraj broj "123abc456"
Just (123, "abc456")
ghci> parsiraj broj "abc"
0

Zadatak 6. Konstruisati parser celobrojnih vrednosti bez korišćenja kombinatora.

Aplikativni parseri

Tip funkcije primeni :: (a -> b) -> Parser a -> Parser b neodoljivo podseća na tip metode fmap :: Functor φ => (a -> b) -> φ a -> φ b sa kojom smo se upoznali i lekciji o funktorima. Kako je i tip Parser jedan apstraktni tip vrste * -> * ima smisla instancirati Functor Parser koristeći istu definiciju koju smo dali za primeni

instance Functor Parser where
    fmap f p = P $
        \s -> case p s of
            Just (x, s') -> Just (f x, s')
            Nothing -> Nothing

Sada je neophodno dokazati da ovako data definicija zadovoljava dva zakona.

Prvo, za svaki parser p mora važiti da je fmap id p = p. Kako je parser p oblika P p' za neku funkciju p', važi sledeće fmap id p = fmap id (P p') = P $ \s -> case p' s of 𝕁 (x, s') -> 𝕁 (id x, s'); ℕ -> ℕ = P $ \s -> case p' s of 𝕁 (x, s') -> 𝕁 (x, s'); ℕ -> ℕ = P p' = p, gde smo sa 𝕁 i ℕ skraćeno označili konstruktore Just i Nothing. Ovim je prvi zakon dokazan.

Za dokaz drugog zakona, neka su date funkcije f :: A -> B i g :: B -> C. Tada za svaki parser p = P p' :: Parser A važi fmap (g . f) p = fmap (g . f) (P p') = P $ \s -> case p' s of 𝕁 (x, s') -> 𝕁 ((g . f) x, s'); ℕ -> ℕ = P $ \s -> case p' s of 𝕁 (x, s') -> 𝕁 (g (f x), s'); ℕ -> ℕ = fmap g $ P $ \s -> case p' s of 𝕁 (x, s') -> 𝕁 (f x, s'); ℕ -> ℕ = fmap g $ fmap f $ P $ \s -> case p' s of 𝕁 (x, s') -> 𝕁 (x, s'); ℕ -> ℕ = fmap g $ fmap f $ P p' = (fmap g . fmap f) p, čime je dokazan i drugi zakon funktora.

Sledeći korak je implementirati instancu Applicative Parser. Za metodu pure :: a -> Parser a, nemamo mnogo izbora: to će biti "konstantan" parser koji ne parsira ništa. Za metodu <*> :: Parser (a -> b) -> Parser a -> Parser b takođe nemamo mnogo opcija. Ako nam je dat parser p1 :: Parser (A -> B) i parser p2 :: Parser A, sve što možemo da uradimo da bi dobili vrednost B je da "pokrenemo" parser p1 i onda sa dobijenim vrednostima "pokrenemo" parser p2. Naravno, ako neki od parsera ne uspe, tada ni "kombinacija" ovih parsera ne bi trebalo da uspe.

instance Applicative Parser where
    pure x = P $ \s -> Just (s, x)

    p1 <*> p2 = P $ \s -> primeni (parsiraj p1 s) p2
        where
            primeni Nothing       _ = Nothing
            primeni (Just (s',f)) p = parsiraj (fmap f p) s'

Zadatak 7. Dokazati da navedena definicija poštuje zakone aplikativnih funktora.

Parseri koji parsiraju funkciju (tj. vrednosti tipa oblika Parser (A -> B)) su na prvi pogled veoma čudan pojam. Šta uopšte znači parsirati funkciju iz niske karaktera? Ali, setimo se koja je bila motivacija za uvođenje aplikativnih funktora: aplikacija funkcija više promenljiva na vrednosti u funktorima. Od sada koristeći pure i <*> možemo kombinovati parsere koristeći proizvoljne funkcije.

ghci> f = \x y -> (x, y)
ghci> slovoCifra = f <$> slovo <*> cifra
ghci> parsiraj slovoCifra "D7"
Just (('D',7), "")

Kako operatori <* i *> funkcionišu u kontekstu parsera? Po definiciji, operator (<*) :: Parser a -> Parser b -> Parser a je definisan kao p1 <* p2 = liftA2 const p1 p2 što se svodi na p1 <* p2 = (fmap const p1) <*> p2. Ako je p1 :: Parser A, tada je fmap const p1 :: Parser (a -> Int) parser koji je moguće primeniti sa <*> na bilo koji drugi parser, ali će parsirana vrednost zavisiti samo od parsera p1, dok će parsirana vrednost parsera p2 biti ignorisana, pod uslovom da parser p2 uspe. Ako parser p2 nije uspešan, tada će i parser p1 <* p2 podbaciti. Slično je i sa operatorom (*>) :: f a -> f b -> f b koji ignoriše rezultat levog parsera (pod uslovom da je taj parser uspeo).

Navedeni operatori nam omogućavaju da konstruišemo parsere koji moraju parsirati neke delove niske, ali ti delovi ne utiču na parsiranu vrednost. Primer za ovu situaciju je parsiranje brojeva sa decimalnom tačkom: tačka se mora naći u zapisu decimalnog broja, ali ne utiče nikako na vrednost tog broja.

niska :: String -> Parser String
niska ""     = P $ \s -> Just (s, "")
niska (x:xs) = P $ \s -> case parsiraj (simbol x) s of
    Just (s',_) -> parsiraj ((x:) <$> niska xs) s'
    Nothing     -> Nothing

ghci> parsiraj (niska "True") "Truehelloworld"
Just ("helloworld","True")
ghci> parsiraj (niska "False") "Falsebyeworld"
Just ("byeworld","False")
ghci> parsiraj (niska "hello") "bye"
Nothing

Zadatak 8. Definisati parser decimalanBroj :: Parser Float koji parsira broj oblika \[\overline{a_1\cdots a_n .b_1\cdots b_m}.\]

Zadatak 9. Definisati parser logičkeListe :: Parser [Bool] koji parsira liste logičkih vrednosti True i False. Na primer, parser bi trebalo da ispravno parsira nisku "[True,False]". Pretpostaviti da u nisci neće biti belina.

Zadatak 10. Definisati parser preskočiBeline :: Parser () koji samo preskače karaktere beline ' ', '\n' i '\t'.

Zadatak 11. Ponovo definisati parser logičkeListe :: Parser [Bool] ali tako da ispravno parsira niske u kojima se nalaze beline između logičkih vrednosti i zareza ili zagrada. Na primer, parser bi trebalo da ispravno parsira nisku poput "[ True, False ]".

Parsiranje matematičkih izraza

U lekciji o rekurzivnim strukturama podataka, definisali smo tip Izraz ka algebarski tip data Izraz = Broj Int | Zbir Izraz Izraz | Proizvod Izraz Izraz. Takođe smo i definisali instancu Show Izraz na sasvim jednostavan način.

instance Show Izraz where
    show (Broj a) = show a
    show (Zbir a b) = "(" ++ show a ++ "+" ++ show b ++ ")"
    show (Proizvod a b) = "(" ++ show a ++ "*" ++ show b ++ ")"

Kako to obično biva, obrnuti proces, proces čitanja strukture iz niske, je značajno komplikovaniji za implementaciju, ali nam tehnika aplikativnih parsera može nam pomoći u ovom slučaju. Sa parserom kog budemo konstruisali, moći ćemo da iz niske pročitamo vrednost Izraz.

Pre nego što počnemo sa definisanjem parsera, moramo tačno definisati oblik niska koje ćemo parsirati. Na primer, složeni parseri izraza mogu ispravno parsirati izraze poput "2 + 5" ili "2*-7+6" jer su napravljeni tako da ignorišu beline (razmake), da vode računa o prioritetu operacija, podržavaju unarni operator negacije, itd... Da bismo skratili naredne redove, mi nećemo kreirati ovako složeni parser. Parser koji budemo konstruisali moći će da parsira samo one izraze koji su nastali sa funkcijom show :: Izraz -> String koju smo gore definisali tj, izraze sačinjene isključivo od cifara i znakova +, -, (, ), pri čemu se oko svakog podizraza nalaze zagrade (osim oko samih brojeva).

Kako je i sama struktura tipa Izraz rekurzivna, i parser tipa Parser Izraz biće rekurzivan. Posebno ćemo konstruisati parser izrazBroj koji parsira brojeve, parser izrazZbir koji parsira zbir dva manja izraza, i parser izrazProizvod koji parsira proizvod dva manja izraza.

Pretpostavimo da su navedeni parseri definisani. Jedan izraz može biti broj, proizvod ili zbir manjih izraza. Zbog toga, da bi parsirali izraz, prvo ćemo pokušati da parsiramo broj. Ako to ne uspemo, onda ćemo pokušati da parsiramo zbir, a ako ni to ne uspemo pokušaćemo da parsiramo proizvod⁴. Sa kombinatorom ili lako dobijamo željeni parser:

izraz :: ParserIzraz
izraz = izrazBroj `ili` izrazZbir `ili` izrazProizvod

Ostaje još definisati izrazBroj, izrazZbir i izrazProizvod. Parser izrazBroj ćemo lako definisati pomoću parsera broj :: Parser Int kog posedujemo od ranije. Sve što je potrebno je da parsiranu vrednost (koja je tipa Int), transformišemo u vrednost tipa Izraz, što se naravno postiže podizanjem konstruktora Broj :: Int -> Izraz na nivo funktora Parser:

izrazBroj :: Parser Izraz
izrazBroj = fmap Broj broj

Parser izrazZbir mora da funkcioniše na sledeći način: prvo je neophodno parsirati simbol za levu zagradu, zatim je potrebno parsirati levi sabirak, pa simbol plus, desni sabirak, i na kraju simbol desne zagrade. Rezultati parsiranja simbola nisu bitni (ako su uspešni), a rezultate parsiranja levog i desnog sabirka moramo ukombinovati u vrednost oblika Zbir x y :: Izraz. Naravno, u tome će nam pomoći podizanje konstruktora Zbir. Takođe, kako su oba sabirka izrazi sami za sebe, potrebno ih je parsirati sa izraz parserom. Ovo uspostavlja rekurziju.

izrazZbir :: Parser Izraz
izrazZbir =
    simbol '(' *>
    (Zbir <$> (izraz <* simbol '+') <*> izraz)
    <* simbol ')' 

Parsiranje proizvoda je u potpunosti analogno parsiranju zbira:

izrazProizvod :: Parser Izraz
izrazProizvod = 
    simbol '(' *>
    (Proizvod <$> (izraz <* simbol '*') <*> izraz)
    <* simbol ')' 

Testiranjem se uveravamo da parser funkcioniše:

ghci> parsiraj izraz "(1+2)"
Just ((1+2), "")
ghci> parsiraj izraz "((10+2)*32)"
Just (((10+2)*32), "")