parsing - How to parse simple expressions? -

my homework make expression parser in haskell. couldn't find case previous questions parsing in haskell on so.

the expression defined follow:

data expr = | const int | var string | add expr expr | sub expr expr | mul expr expr | pow expr int deriving show 

the type parser defined follow:

type parser = string -> maybe (a, string) 

the parsers given in homework defined follow:

--primitive parsers  success :: -> parser success v = \inp -> (v, inp)  failure :: parser failure = \_ -> nothing  item :: parser char item = \inp -> case inp of                  "" -> nothing                 (c : cs) -> (c, cs)  --sequential parsers  (>>>) :: parser -> (a -> parser b) -> parser b p >>> f = \inp -> case p inp of                     nothing -> nothing                     (x, cs) -> f x cs  (&&&) :: parser -> parser b -> parser b  p &&& q = p >>> \_ -> q  -- conditional parsers  sat :: (char -> bool) -> parser char sat f = item >>> \c -> if f c success c else failure  digit :: parser char  digit = sat isdigit  space :: parser char space = sat isspace  char :: char -> parser char char c = sat (== c)  -- alternative parsers  (+++) :: parser -> parser -> parser p +++ q = \inp -> case p inp of                     nothing -> q inp                      res -> res  -- iterative parsers  many :: parser -> parser [a] many p = many1 p +++ success []  many1 :: parser -> parser [a] many1 p = p >>> \v -> many p >>> \vs -> success (v : vs)  --token  nat :: parser int nat = many1 digit >>> \cs -> success (read cs)  spaces :: parser () spaces = many space &&& success ()  token :: parser -> parser token p = spaces &&& p  natural :: parser int natural = token nat  symbol :: char -> parser char symbol c = token (char c) 

now have develop function expr takes string , converts expr.

to in homework find function defined follow:

expr :: parser expr expr = term >>> \t -> (symbol '+' &&& expr >>> \e -> success $ add t e) +++ (symbol '-' &&& expr >>> \e -> success $ sub t e) +++ success t 

i understand have develop 3 functions: term, power , factor.

the function factor should parse constant or variable.

the function term should parse single factor (for example 2) or multiplication between 2 factors (for example 2*x).

i don't understand how monads work , i'm having problems homework. on how these functions should written?

here image found in homework.

the various parsers need write building precedence rules order of operations of arithmetic structure of parsers. in order least precedence these are

• parenthesis , atomic literals numbers , variables, call factor
• exponentiation, call power
• multiplications, call term
• addition , subtraction, call expr.

you starting on outside operators lowest precedence , working in operators highest precedence. moving in multiplication, can write term same way wrote expr. expr consisted of terms; term consist of powers

term :: parser expr term = power >>> \p -> (symbol '*' &&& term >>> \e -> success $ mul p e) +++ success p 

in same way, power consist of factors. since right hand side of pow int, uses natural number nat instead of recursing.

power :: parser expr power = factor >>> f -> (symbol '^' &&& nat >>> \n -> success $ pow f n) +++ success f 

i'll leave writing factor you; parts wrote same expr, figured out. parenthesis inside factor wrap arbitrary expression expr, starting on again @ outside @ least precedence. allow parse things "2*(x+1)"