FParsec中的尾递归

Question

我遇到了一个问题，解析器有两个分支的递归。为了更容易地演示这个问题，我使用了来自卢卡·博洛尼塞撰写的文章的lambda演算的一个简单语法作为示例：

::= \ ::=非空白字符序列::= \。::= ::= () ::= ::=

本文中的解析器相当简洁：

let ws = " \t\n" 
let specialChars = ".)(\\\n" 

let pWs = spaces 
let pName = manyChars (noneOf (ws + specialChars)) |>> EName 

let pExpr, pExprRef = createParserForwardedToRef<Expression, Unit>() 

let curry2 f a b = f(a,b) 
let pFunction = pchar '\\' >>. pipe2 pName (pchar '.' >>. pExpr) (curry2 Function) 

let pApplication = pchar '(' >>. pipe2 pExpr (pWs >>. pExpr) (curry2 Application)
                            .>> pWs .>> pchar ')'

do pExprRef := pFunction <|> pApplication <|> pName 

let pExpressions = sepBy pExpr spaces1 

let fparseString text = 
    match run pExpressions text with 
    | Success(result, _, _)   -> result 
    | Failure(errorMsg, _, _) -> failwith (sprintf "Failure: %s" errorMsg) 

我对pApplication感兴趣，因为它们由两个pExpr组成，后者也可以是pApplication。解析器在以下基准测试中耗尽堆栈空间：

let generateString level =
    let rec loop i =
        seq {
                if i < level then
                    yield "("
                    yield! loop level
                    yield " "
                    yield! loop (i+1)
                    yield ")"
                else 
                    yield "(x x)"
        }
    loop 0 |> String.concat ""

let N = 5000
let s = generateString N;; 
let _ = fparseString s;;

如何重写解析器使其成为尾递归的？

当我试图为类似Lisp的语言编写解析器并使用真正的基准测试时，我发现了这个问题。我有Term和VarBinding，它们是相互递归的类型，还有一个let解析器，它显示了与上面的pApplication相同的问题。我的解析器是论github，以防对非尾递归问题的分析是错误的。

Answer 1

FParsec的内置解析器组合器通常不允许尾递归解析器实现，主要是因为实现错误处理的方式。

这意味着FParsec解析器的递归深度受到堆栈大小的限制--与大多数递归下降解析器一样。当然，这不会影响使用many、sepBy、chainl等对序列的解析，因为这些FParsec组合器都具有堆栈空间使用常量的实现。

.NET中的默认堆栈大小通常足以用FParsec解析指定格式的人工生成的输入(假设您使用内置组合器解析序列)。但是，机器生成的具有深嵌套结构的输入(如5000级深s表达式)很容易导致堆栈溢出。

如果您事先知道输入中的嵌套深度限制在一个合理的值，您可以简单地将增加堆栈大小设置为一个适当的值。希望这对于基准数据是正确的。

否则，您可能必须为语法的递归元素实现一个特殊的解析器函数。您需要使用低-级别 API接口 of FParsec来实现这个函数，显然您必须使用实现此函数，以便它使用堆而不是堆栈。来跟踪嵌套上下文和中间解析结果。