Exercise set 5.

It is the fifth week of the course, and we will learn to use a monadic parser combinator library called Parsec. Start by reading chapter 13 in Programming in Haskell by Graham Hutton.

Credits

The following exercises is based on a warmup exercise from the course Advanced Programming at the University of Copenhagen.

Parsing arithmetic expressions.

Consider the grammer:

E ::= E "+" T | E "-" T | T | "-" T .
T ::= num | "(" E ")" .

Given the lexical specifications:

1. num is one or more decimal digits (0-9)
2. tokens may be separated by arbitrary whitespace (spaces, tabs, newlines).

Eliminate left-recursion.

Consult the material folder, and find the 10-parsernotes.pdf. The notes are written by Peter Sestoft and Ken Friss Larsen, who are Danish programming language researchers.

Find the section about left-factorization, come back here, and left factorize the above grammar.

finish the program:

import Text.ParserCombinators.Parsec -- exports ParseError

data Exp = Num Int | Negate Exp | Add Exp Exp
  deriving (Eq, Show)

-- Optional: if not attempted, leave as undefined
parseString :: String -> Either ParseError Exp
parseString = undefined