CODEWITHSUNDEEP
parsinghaskellevaluation
rosbif
rosbif

Reputation: 11

Expression Evaluation using combinators in Haskell

I'm trying to make an expression evaluator in Hakell:

data Parser i o
  = Success o [i]
  | Failure String [i]
  | Parser
      {parse :: [i] -> Parser i o}

data Operator = Add | Sub | Mul | Div | Pow

data Expr
  = Op Operator Expr Expr
  | Val Double

expr :: Parser Char Expr
expr = add_sub
  where
    add_sub =  calc Add '+' mul_div  <|>  calc Sub '-' mul_div  <|>  mul_div
    mul_div =  calc Mul '*' pow  <|>  calc Div '/' pow  <|>  pow
    pow     =  calc Pow '^' factor  <|>  factor
    factor  =  parens  <|>  val
    val     =  Val  <$>  parseDouble
    parens  =  parseChar '('  *>  expr  <*  parseChar ')'
    calc c o p =  Op c  <$>  (p  <*  parseChar o)  <*>  p

My problem is that when I try to evaluate an expression with two operators with same priority (e.g. 1+1-1) the parser will fail.

How can I say that an add_sub can be an operation between two other add_subs without creating an infinite loop?

Upvotes: 0

Views: 127

Answers (2)

Ilya Silvestrov
Ilya Silvestrov

Reputation: 367

You should build an analog of the Parsec's chainl1 to, quote:

eliminate left recursion which typically occurs in expression grammars.

Upvotes: 0

rosbif
rosbif

Reputation: 11

As explained by @chi the problem is that calc was using p twice which doesn't allow for patterns like muldiv + .... | muldiv - ... | ...

I just changed the definition of calc to :

calc c o p p2 = Op c <$> (p <* parseChar o) <*> p2

where p2 is the current priority (mul_div in the definition of mul_div)

it works much better but the order of calulations is backwards: 2/3/4 is parsed as 2/(3/4) instead of (2/3)/4

Upvotes: 0

Related Questions