parsing - 将语法产生式翻译成 Parsec

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

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'

其中 primaryExpr 的类型为 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;
                   .... }

如何修复此类型错误？

最佳答案

使用 chainl1 。 chainl1 p op 以左关联方式解析一个或多个由 p -s 分隔的 op -s。 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 (否则我们如何将它绑定(bind)到 e' ？)，所以它应该是 return e 。

关于parsing - 将语法产生式翻译成 Parsec，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/29257907/