Samenvatting hst. 3 sec. 1-3 infixr 4
(<|>) :: Parser a b ! Parser a b ! Parser a b
(p <|> q) xs = p xs ++ q xs infixl 6
(<*>) :: Parser a (b!c) ! Parser a b ! Parser a c
(p <*> q) xs = [(f b,zs) | (f,ys)"p xs, (b,zs)"q ys] infixl 7
(<$>) :: (b!c) ! Parser a b ! Parser a c
(f <$> p) xs = [(f b,ys) | (b,ys) " p xs]
Toepassing: geneste haakjes !!Grammatica
!!Abstracte syntax
{ H ! #$ , H!(H)H }
data H = Leeg | Paar H H
!!Parser haakjes :: Parser Char H (\x ! Leeg) <$> epsilon haakjes = <|> (\a b c d ! Paar b d) <$> open <*> haakjes <*> sluit <*> haakjes Where open = symbol ’(’ sluit = symbol ’)’
Samenvatting hst. 3 sec. 4 !!Parser combinators voor EBNF many many1 option
:: Parser a b ! Parser a [b] :: Parser a b ! Parser a [b] :: Parser a b ! b ! Parser a b
!!Nog wat extra utilities pack sequence Choice listOf Chainr
:: Parser a o ! Parser a b ! Parser a s ! Parser a b :: [ Parser a b ] ! Parser a [b] :: [ Parser a b ] ! Parser a b :: Parser a b ! Parser a s ! Parser a [b] :: Parser a b ! Parser a (b!b!b) ! Parser a b
Abstracte syntax voor Expressies data Expr = | | | | | |
Con Int Var String Fun String [Expr] Expr :+: Expr Expr :–: Expr Expr :*: Expr Expr :/: Expr
Parser voor Expressies (met prioriteiten) expr = chainr term ( (\o!(:+:)) <$> (symbol ‘+’) <|> (\o!(:–:)) <$> (symbol ‘–’) chainl is nu beter ) term = chainr fact ( (\o!(:*:)) <$> (symbol ‘*’) <|> (\o!(:/:)) <$> (symbol ‘/’) chainl is nu beter ) fact = Con <$> getal <|> gehaakt expr <|> Var <$> naam <|> Fun <$> naam <*> gehaakt (listOf expr (symbol ‘,’) )
Parser voor Expressies (principe) expr = chainr term
( <|> ) term = chainr fact ( <|> ) gen ops next = chainr next fact = <|>
… (:+:)…‘+’ … … (:–:)…‘–’ … … (:*:)…‘*’ … … (:/:)…‘/’ …
( choice …ops… )
basis gehaakt expr
Parser voor Expressies (veel prioriteiten) expr = gen ops1 term1 term1= gen ops2 term2 term2= gen ops3 term3 term3= gen ops4 term4 term4= gen ops5 fact fact = basis <|> gehaakt expr
expr = foldr gen fact gen ops next = chainr next
[ops1,ops2,ops3,ops4,ops5]
( choice …ops… )
Gebruik van parsers !!Type van parsers type Parser a b = [a] ! [ (b, [a]) ]
!!Parser voor expressies expr
:: Parser Char Expr
expr
:: String ! [ (Expr, String) ]
!!Opstarten van de parser geefExpr :: String ! Expr geefExpr = fst . head .
filter (null.snd) .
expr
Gebruik van parsers geefExpr ::
String ! Expr
geefExpr = fst .
head .
filter (null.snd) .
expr
!!Generalisatie start :: Parser a b ! start p =
fst .
[a] ! b head .
filter (null.snd) .
Ontwerp van een parser !!Observeer de taal !!Bedenk een grammatica "!evt. transformeren
!!Maak datatype voor de ontleedboom !!Maak parse-functie "!evt. met preprocessor
!!Voeg semantiek toe "!of: als functie op ontleedboom "!of: direct tijdens het parsen
p
Parser-ontwerp (1/5) Observeer de taal !!Voorbeeld: reisschema’s vertrek
aankomst
Utrecht 9:17 9:42 Amsterdam Groningen 8:37 9:44 Zwolle 9:49 10:15 Utrecht 10:21 11:05 Rotterdam Almelo
Parser-ontwerp (2a/5) Bedenk een grammatica Groningen 8:37 9:44 Zwolle 9:49 10:15 Utrecht 10:21 11:05 Rotterdam
Schema ! Schema Tijd Tijd Schema | Stad Tijd ! Getal : Getal$ Getal ! Cijfer + Stad ! Letter +
Parser-ontwerp (2b/5) Bedenk een grammatica Groningen 8:37 9:44 Zwolle 9:49 10:15 Utrecht 10:21 11:05 Rotterdam
Schema ! Stad Tijd Overstap* Tijd Stad | Stad Overstap ! Tijd Stad Tijd$
Parser-ontwerp (2c/5) Bedenk een grammatica Groningen 8:37 9:44 Zwolle 9:49 10:15 Utrecht 10:21 11:05 Rotterdam
Schema ! Stad Rit* Rit ! Tijd Tijd Stad$
Parser-ontwerp (2d/5) Bedenk een grammatica Groningen 8:37 9:44 Zwolle 9:49 10:15 Utrecht 10:21 11:05 Rotterdam
Schema ! Rit’* Stad Rit’ ! Stad Tijd Tijd
Parser-ontwerp (3b/5) Maak datatype ontleedboom Schema ! Stad Tijd Overstap* Tijd Stad | Stad Overstap ! Tijd Stad Tijd$ data Schema = Met Stad Tijd [Overstap] Tijd Stad | Zonder Stad type Overstap = ( Tijd , Stad , Tijd )
Parser-ontwerp (3d/5) Maak datatype ontleedboom Schema ! Rit* Stad Rit ! Stad Tijd Tijd
type type type type
Schema’ = ( [Rit] , Stad) Rit = ( Stad , Tijd , Tijd ) Tijd = ( Int , Int ) Stad = String
Parser-ontwerp (4b/5) Maak parse-functie Schema ! Stad Tijd Overstap* Tijd Stad | Stad Overstap ! Tijd Stad Tijd$ schema =Met <$> stad <*> tijd <*> many overstap <*> tijd <*> stad <|> Zonder <$> stad overstap = (\t1 s t2 ! (t1,s,t2)) <$> tijd <*> stad <*> tijd tijd = (\n1 d n2 ! (n1,n2)) <$> getal <*> symbol ‘:’ <*> getal
Parser-ontwerp (4d/5) Maak parse-functie Schema ! Rit* Stad Rit ! Stad Tijd Tijd
schema’ = (\rs s ! (rs,s)) <$> many rit <*> stad rit = (\s t1 t2 ! (s,t1,t2)) <$> stad <*> tijd <*> tijd
Parser-ontwerp (5/5) Voeg semantiek toe !!Bijvoorbeeld: "!Wachttijd "!Totale reistijd "!Lijst van stations min :: Tijd ! Int min (u,m) = 60*u + m wachttijd, reistijd :: Schema! Int stations :: Schema! [String]
Semantische functies data Schema = Met Stad Tijd [Overstap] Tijd Stad | Zonder Stad type Overstap = ( Tijd , Stad , Tijd ) wacht (Zonder _) =0 wacht (Met _ _ os _ _) = sum (map f os) where f (t1,_,t2) = min t2 – min t1 stats (Zonder s) = [s] stats (Met s1 _ os _ s2) = s1 : map f os ++ [s2] where f (_,s,_) = s reis = … Oei… lastig!
Alternatieve Semantische functies type Schema’ = ( [Rit] , Stad) type Rit = ( Stad , Tijd , Tijd ) reis’ (rs,_) = sum (map f rs) where f (s,t1,t2) = min t2 – min t1 stats’ (rs,s) = map f rs ++ [s] where f (s,_,_) = s wacht’ = …
Oei… lastig!
Ontleedboom bepalen tijdens het ontleden schema’ :: Parser String Schema’ schema’ = (\rs s ! (rs,s)) <$> many rit <*> stad rit rit
=
:: Parser String Rit (\s t1 t2 ! (s,t1,t2)) <$> stad <*> tijd <*> tijd
Semantiek bepalen tijdens het ontleden schemaReis’ :: Parser String Int schemaReis’ = (\ns s ! sum ns) <$> many ritReis <*> stad ritReis ritReis =
:: Parser String Int (\s t1 t2 ! min t2 – min t1) <$> stad <*> tijd <*> tijd
Ontwerp van een parser !!Observeer de taal !!Bedenk een grammatica "!evt. transformeren
!!Maak datatype voor de ontleedboom !!Maak parse-functie "!evt. met preprocessor
!!Voeg semantiek toe "!of: als functie op ontleedboom "!of: direct tijdes het parsen
De basis-parsers many1 :: Parser a b ! Parser a [b] naam :: Parser Char String naam = many1 (satisfy isAlpha) getal :: Parser Char Int getal = foldl f 0 <$> many (satisfy isDigit) where f n c = 10*n + ord c – ord ‘0’
Publieksvraag !!Observeer de taal van floating-point getallen in standaard programmeertalen 3.14 1e6
-5F
.3
+6.02E23
float :: Parser Char Float float =
Uitwerking cijfer :: Parser Char Int cijfer = (\c!ord c–ord’0’) <$> satisfy isDigit natuurlijk :: Parser Char Int natuurlijk = (foldl (\n d!10*n+d) 0) <$> many cijfer geheel :: Parser Char Int geheel =apply <$> option ((\c!neg) <$> symbol ‘–’) id <*> natuurlijk
eigenlijk moet fromIntegral :: Int ! Float nog worden gebruikt
fractie :: Parser Char Float fractie = (foldr (\d n!(n+d)/10) 0) <$> many cijfer
Uitwerking (vervolg) fixed :: Parser Char Float fixed = (+) <$> geheel <*> option( (\p x! x) <$> fromIntegral symbol ‘.’ <*> fractie ) 0 float :: Parser Char Float float = f <$> fixed <*> option( (\p x! x) <$> symbol ‘E’ <*> geheel ) 0 where f gr ex = gr * pow 10 ex
