将语法生成翻译成Parsec

Question

我正在尝试转换以下语法生成

callExpr:
    primaryExpr
  | callExpr primaryExpr

到Haskell中的Parsec表达式.

显然问题是它是左递归的,所以我试图解析它的递归 - 上升风格.我试图实现的伪代码是:

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

我试图将其翻译成Haskell是:

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'

其中primaryExprtype IParser Expr 和IParser定义为

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

但是这会给我以下类型错误:

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;
                   .... }

如何修复此类错误？

Answer 1

使用chainl1.以左关联方式chainl1 p op解析p由-s分隔的一个或多个-s op.op返回一个二元函数,用于将p两侧的-s 结果合并为一个结果.

由于你的语法似乎并不有一个分隔符,你可以使用chainl1与op刚刚返回组合功能:

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

至于你的callExpr实现,我可以发现两个错误.

首先,你使用return $ callExpr' e,但callExpr' e已经是一个monadic值,所以只是callExpr' e正确.

第二,在maybe e (\e2 -> callExpr' (CallExpr e e2)) e2m,默认e应该是monadic(或者我们怎么能把它绑定到e'？),所以它应该是return e.