Translate grammar production to Parsec

Question

I'm trying to convert the following grammar production

callExpr:
    primaryExpr
  | callExpr primaryExpr

to a Parsec expression in Haskell.

Obviously the problem is that it's left-recursive, so I'm trying to parse it recursive-ascent style. The pseudocode I'm trying to implement is:

e = primaryExp
while(true) {
    e2 = primaryExp
    if(e2 failed) break;
    e = CallExpr(e, e2)
}

and my attempt at translating this into Haskell is:

callExpr :: IParser Expr
callExpr = do
    e <- primaryExpr
    return $ callExpr' e
  where
    callExpr' e = do
        e2m <- optionMaybe primaryExpr
        e' <- maybe e (\e2 -> callExpr' (CallExpr e e2)) e2m
        return e'

where primaryExpr has type IParser Expr and IParser is defined as

type IParser a = ParsecT String () (State SourcePos) a

This however gives me the following type error:

Couldn't match type `ParsecT String () (State SourcePos) t0'
              with `Expr'
Expected type: ParsecT String () (State SourcePos) Expr
  Actual type: ParsecT
                 String
                 ()
                 (State SourcePos)
                 (ParsecT String () (State SourcePos) t0)
In a stmt of a 'do' block: return $ callExpr' e
In the expression:
  do { e <- primaryExpr;
       return $ callExpr' e }
In an equation for `callExpr':
    callExpr
      = do { e <- primaryExpr;
             return $ callExpr' e }
      where
          callExpr' e
            = do { e2m <- optionMaybe primaryExpr;
                   .... }

How do I fix this type error?

Answer 1

Use chainl1. chainl1 p op parses one or more p-s separated by op-s in a left-associative way. op returns a binary function which is used to combine the results of the p-s on both sides into a single result.

Since your grammar doesn't seem to have a separator, you can use chainl1 with an op that just returns the combining function:

callExpr :: IParser Expr
callExpr = chainl1 primaryExpr (return CallExpr)

As to your callExpr implementation, I can spot two errors.

First, you use return $ callExpr' e, but callExpr' e is already a monadic value, so just callExpr' e would be correct.

Second, in maybe e (\e2 -> callExpr' (CallExpr e e2)) e2m, the default e should be monadic (or else how could we bind it to e'?), so it should be return e.