在您的代码中,下面的函数不是尾部递归的,因为在每次迭代中,它在
p'
或
succeed
:
let rec chainl1Util (acc : 'a) : Parser<'a> =
let pOp = parser {
let! f = op
let! y = p
return! chainl1Util (f acc y) }
pOp <|> succeed acc
根据您对解析器组合器的实现,以下重写可以工作(我不是这里的专家,但可能值得尝试一下):
let rec chainl1Util (acc : 'a) : Parser<'a> =
let pSuc = parser {
let! r = succeed acc
return Choice1Of2(r) }
let pOp = parser {
let! f = op
return Choice2Of2(f) }
parser {
let! cont = pOp <|> pSuc
match cont with
| Choice1Of2(r) -> return r
| Choice2Of2(f) ->
let! y = p
return! chainl1Util (f acc y) }
一般来说,在计算表达式中编写尾部递归函数的模式是有效的。类似这样的方法可以工作(对于以允许尾部递归的方式实现的计算表达式):
let rec foo(arg) = id {
return! foo(expr) }
正如您可以检查的那样,新版本与此模式匹配,但原始版本不匹配。