Operator precedence and associativity in a parser

Question

I am trying to extend a recursive-descent parser to handle new operators and make them associate correctly. Originally there were only four operators (+ - / *) and they all had the same precedence. The function I am looking at is the parseExpRec function:

parseExpRec               :: Exp -> [Token] -> (Exp, [Token])    
parseExpRec e  []         =  (e, [])
parseExpRec e1 (op : ts)  = 
 let (e2, ts') = parsePrimExp ts in
   case op of
    T_Power     -> parseExpRec (BinOpApp Power  e1 e2) ts'
    T_Plus      -> parseExpRec (BinOpApp Plus   e1 e2) ts'
    T_Minus     -> parseExpRec (BinOpApp Minus  e1 e2) ts'
    T_Times     -> parseExpRec (BinOpApp Times  e1 e2) ts'
    T_Divide    -> parseExpRec (BinOpApp Divide e1 e2) ts'
    T_GreaterThan   -> parseExpRec (BinOpApp GreaterThan    e1 e2) ts'
    T_LessThan      -> parseExpRec (BinOpApp LessThan       e1 e2) ts'
    T_GreaterOrEqual -> parseExpRec (BinOpApp GreaterOrEqual e1 e2) ts'
    T_LessOrEqual   -> parseExpRec (BinOpApp LessOrEqual    e1 e2) ts'
    T_EqualTo       -> parseExpRec (BinOpApp EqualTo        e1 e2) ts'
    _           -> (e1, op : ts)

All of the pattern matching lines except T_Plus, T_Minus, T_Times and T_Divide have been added by me (and so have the associated tokens and extensions to the Exp datatype). However, none of them seem to associate correctly. For example, the string "3^4 + 2^3" evaluates to:

BinOpApp Power (BinOpApp Plus (BinOpApp Power (LitInt 3) (LitInt 4)) (LitInt 2)) (LitInt 3)

Which is equivalent to this in infix notation (with brackets included):

((3^4)+2)^3

How would I fix this?

Answer 1

I've written a paper on unparsing expressions using operator precedence. The appendix to the paper has an operator-precedence parser written in ML, which you could easily adapt to Haskell. The code is downloadable from the page above.

While Haskell has many fine libraries of parsing combinators, I have never seen one that was both (a) simple enough for me to understand easily and (b) supported operator-precedence parsing with arbitrary levels of precedence.

Answer 2

I think you should look at an existing parser combinator library. For example, parsec, to see how they implement precedence. In particular, the operator table