我正在尝试转换以下语法产生式
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
以左关联方式解析由 op
-s 分隔的一个或多个 p
-s。 op
返回一个二进制函数,用于将两侧 p
-s 的结果合并为一个结果。
由于您的语法似乎没有分隔符,因此您可以将 chainl1
与仅返回组合函数的 op
一起使用:
callExpr :: IParser Expr
callExpr = chainl1 primaryExpr (return CallExpr)
对于您的 callExpr
实现,我可以发现两个错误。
首先,您使用 return $ callExpr' e
,但 callExpr' e
已经是一个单子(monad)值,因此只需 callExpr' e
即可一定要正确。
其次,在也许 e (\e2 -> callExpr' (CallExpr e e2)) e2m
中,默认的 e
应该是 monadic (否则我们如何绑定(bind)它到e'
?),所以它应该是return e
。
关于parsing - 将语法产生式转换为秒差距,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/29257907/