FParsec 中的尾递归

Question

我遇到了具有两个递归分支的解析器的问题。为了更容易地演示这个问题，我使用了 Luca Bolognese 写的文章为例：

<前><代码><表达式>; ::= <名称>; | <功能> | <应用> <名称> ::= 非空白字符序列 <功能> ::= \ <名称>; 。 <正文> <正文> ::= <表达式>; <应用> ::= ( <函数表达式> <参数表达式> ) <函数表达式> ::= <表达式>; <自变量表达> ::= <表达式>;

文章中的解析器非常简洁：

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 组成，而这两个 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 表达式）很容易导致堆栈溢出。

如果您事先知道输入中的嵌套深度被限制在合理的值，您可以简单地 增加堆栈大小到适当的值。希望您的基准数据也是如此。

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