Extending the Combinator Parser: The Right Way

Transform the grammar: parse as right recursion, convert the result to associate left!

E ::= E Op T | T

E ::= T {Op T}*

binOp oper rand =

do x <- rand

op_ys <- many (oper `pair` rand)

return

(foldl (\z (op,y) -> z `op` y) x op_ys)

p `pair` q =

do x <- p

y <- q

return (x,y)

expr and term need not change at all!