Laboratorium 5

Zadanie 1

Dana składnia abstrakcyjna wyrażeń arytmetycznych (jak w 3. tygodniu)

data Exp = IntE Int
        | OpE  Op Exp Exp
        | VarE String
        | LetE String Exp Exp  -- let var = e1 in e2
 
type Op = Int -> Int -> Int

a. zaprojektuj składnię konkretną
Sugestie: standardowa notacja infiksowa oraz notacja prefiksowa a la Lisp: (* (+ 1 2) 3)

b. napisz parser dla tej składni przy uzyciu Text.ParserCombinators.Parsec

UWAGA: Ze względów wydajnościowych, operator (<|>) z biblioteki Parsec jest prawie deterministyczny i nie będzie działać dobrze dla produkcji, które mają wspólny (niepusty) prefiks.

Możemy odzyskać niedeterminizm przy pomocy kombinatora try, np.

try p<|> q

Zadanie 2

Napisz własne wersje kombinatorów parsujących użytych w poprzednim zadaniu

Sugestie:

newtype Parser a = Parser { runParser :: String -> [(a,String)] }
newtype Parser a = Parser { 
  runParser :: String -> [Either ErrorMessage (a,String)] 
}

albo, używając transformatorów monad

type Parser a = StateT [Char] (ErrorT String []) a