一些背景优先。我目前正在学习一些关于monadic解析器组合器的东西。当我试图从this paper(第16-17)转移“chainl1”功能,我想出了这个解决方案:计算表达式中的递归函数
let chainl1 p op = parser {
let! x = p
let rec chainl1' (acc : 'a) : Parser<'a> =
let p' = parser {
let! f = op
let! y = p
return! chainl1' (f acc y)
}
p' <|> succeed acc
return! chainl1' x
}
我测试了一些大的输入功能,并得到了StackOverflowException。现在我想知道,是否有可能重写递归函数,它使用一些计算表达式,所以它使用尾递归?
当我扩大计算表达式时,我看不出它通常是可能的。
let chainl1 p op =
let b = parser
b.Bind(p, (fun x ->
let rec chainl1' (acc : 'a) : Parser<'a> =
let p' =
let b = parser
b.Bind(op, (fun f ->
b.Bind(p, (fun y ->
b.ReturnFrom(chainl1' (f acc y))))))
p' <|> succeed acc
b.ReturnFrom(chainl1' x)))
这摆脱了通过用户代码递归,但在我的实现这里http://lorgonblog.spaces.live.com/blog/cns!701679AD17B6D310!1772.entry它仍然StackOverflows通过解析器实现本身。我现在会被激发去研究'延续解析器'... – Brian 2010-06-29 18:31:55
FParsec http://www.quanttec.com/fparsec/处理这个问题吗? – Brian 2010-06-29 18:33:00
布赖恩,我也用你的博客系列作为学习资源。它帮助了很多。同时我将Mau的答案('seq')与我的解析器进行了比较。我猜想monad中的Delay方法是导入。但我真的不知道。 FParsec使用'while'...但我想使用功能性解决方案:D – PetPaulsen 2010-06-29 18:50:15