Parsimine tähendab sõnest info tuvastamist ja paigutamist mingisse andmestruktuuri. Enamasti peame olema valmis juhtumiks, et parsimine ebaõnnestub, ja meil pole võimalik andmestruktuuri tagastada.
Vaatame tavalist kümnendkujul arvude lugemist. Näiteks sõnest \"1234\" saab parsida täisarvu 1234 ehk näiteks Just 1234. Samas, sõnest \"xyz\" ei saa parsida täisarvu ja peame tagastama näiteks Nothing.
Moodulis Data.String.Parser on selliseks parsimiseks tüüp Parser, funktsioon parse ja parser integer. Parsimise tulemus on tüübist Either String (a, Int), kus parem väärtus on positiivne tulemus (koos tarbitud tähtede arvuga) ja vasak väärtus veateade.
| Main> parse integer "1234" Right (1234, 4) Main> parse integer "xyz" Left "Parse failed at position 0-0: could not satisfy predicate" Main> parse (char '.') "." Right ('.', 1) Main> parse (char '.') "1234" Left "Parse failed at position 0-0: expected '.'" |
Miks aga on tarvis positiivses tulemuses tagastada tarbitud tähtede arvu? Põhjus on selles, et siis saab parsereid omavahel järjestikuselt kombineerida — näiteks monaadide võimalusi kasutades.
| 1sulus : Parser Double 2sulus = do _ <- char '(' 3 a <- integer 4 _ <- char ')' 5 return a |
Parser sulus loeb nüüd täpselt sulgudes olevaid täisarve.
| Main> parse sulus "1234" Left "Parse failed at position 0-0: expected '('" Main> parse sulus "(1234)" Right (1234, 6) |
Kuidas aga teha parserit, mis loeb nii sulgudes kui ilma sulgudeta täisarve. Selleks on operaator <|>. Kui meil on sama tüüpi parserid a ja b, siis a <|> b parsib esmalt vasakpoolse parseriga a ja ainult nurjumisel parempoolsem parseriga b. Näitena saame kasutada parserit integer <|> sulus.
| Main> parse (integer <|> sulus) "1234" Right (1234, 4) Main> parse (integer <|> sulus) "(1234)" Right (1234, 6) |
Rekursiivsete andmestruktuuridesse parsimise jaoks saab kasutada ka rekursiivseid parsereid. Tuleb aga arvestada, et Idris võib väärtustada avaldisi agaralt, ja lõpmatu tsükli tekkimise vältimiseks võib olla tarvis vasak-rekursiivne parser ümber kirjutada parem-rekutsiivselt.
| 1intlist : Parser (List Integer) 2intlist = nil <|> cons 3 4 where nil : Parser (List Integer) 5 nil = do _ <- string "[]" 6 pure [] 7 8 cons : Parser (List Integer) 9 cons = do x <- integer 10 _ <- string "::" 11 xs <- intlist 12 pure (x::xs) |
Parser intlist loeb täisarvude liste.
| Main> parse intlist "1::2::3::[]" Right ([1, 2, 3], 11) Main> parse intlist "3::1::[]" Right ([3, 1], 8) |
Siiani vaatasime puhtaid parsereid aga moodulis Data.String.Parser on implementeeridud ka üldisem juht, kus arvutus toimub etteantud monaadis. Näiteks võime võtta listide parsimise IO-monaadis, kus trükime järjest välja parsimise edusammud. Pane järgnevas koodis tähele, kuidas lift funktsioon teisendab monaadilise arvutuse tüübis IO a-st parseri väärtuse ParseT IO a.
| 1intlist_debug : ParseT IO (List Integer) 2intlist_debug = cons <|> nil 3 4 where nil : ParseT IO (List Integer) 5 nil = do _ <- string "[]" 6 lift (putStrLn "nil parsed") 7 pure [] 8 9 cons : ParseT IO (List Integer) 10 cons = do x <- integer 11 lift (putStrLn "int \{show x} parsed") 12 _ <- string "::" 13 lift (putStrLn "cons parsed") 14 xs <- intlist_debug 15 pure (x::xs) |
Parser intlist_debug loeb täisarvude liste jooksvalt väljundit genereerides. Pane ka tähele, et kogu parsimine käib nüüd IO monaadi all ja peame seda käivitama :exec-ga.
| Main> :exec parseT intlist_debug "1::2::3::[]" >>= printLn int 1 parsed cons parsed int 2 parsed cons parsed int 3 parsed cons parsed nil parsed Right ([1, 2, 3], 11) |
Nägime, kuidas parsereid defineerida ja kuidas neid kasutada. Hüppasime üle detailidest, kuidas parserid sisemiselt töötavad. Seda vaatamegi järgmisena.
Sisemiselt on ParseT m a väärtused kirjed, kus on salvestatud funktsioon State -> m (Result a), kus State ja Result on defineeritud järgnevalt.
| 1record State where 2 constructor S 3 input : String 4 pos : Int 5 maxPos : Int 6 7data Result a = Fail Int String | OK a State |
Sisuliselt kirjeldab State sisendsõne veel parsimata suffiksit vältides sõnest koopiate tegemist. Tulemuse andmestruktuur Result on olemuselt sarnane Maybe struktuuriga, lisades vea tekkimise asukoha sõnes ning lõppseisundi õnnestumise korral.
Monaadi kõrvale jättes on parserid sisuliselt funktsioonid tüübiga String -> Maybe (a, String). Ehk, õnnestumise puhul tagastatakse parsitud väärtus ja sõne ülejääk. Vea korral midagi sisulist tagastama ei pea.