我遇到了具有两个递归分支的解析器的问题。为了更容易地演示问题，我使用了来自 the article written by Luca Bolognese 的 lambda 演算的简单语法。例如:
<expression> ::= <name> | <function> | <application> <name> ::= nonblank character sequence <function> ::= \ <name> . <body> <body> ::= <expression> <application> ::= ( <function expression> <argument expression> ) <function expression> ::= <expression> <argument expression> ::= <expression>
文章中的解析器相当简洁:
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 相同的问题.我的解析器是 on github以防非尾递归问题分析错误。
最佳答案
FParsec 的内置解析器组合器通常不允许尾递归解析器实现，主要是因为错误处理的实现方式。
这意味着 FParsec 解析器的递归深度受堆栈大小的限制——就像大多数递归下降解析器的情况一样。当然，这不影响用many、sepBy、chainl等序列的解析，因为这些FParsec组合子都有与恒定的堆栈空间使用。
.NET 中的默认堆栈大小通常足以使用 FParsec 以明确指定的格式解析人工生成的输入(假设您使用内置组合器解析序列)。但是，机器生成的具有深层嵌套结构的输入(例如 5000 级深 s 表达式)很容易导致堆栈溢出。
如果您事先知道输入中的嵌套深度被限制在一个合理的值内，您可以简单地 increase the stack size到一个合适的值。希望您的基准数据也是如此。
否则，您可能必须为语法的递归元素实现一个特殊用途的解析器函数。您需要使用 low 来实现此功能- level API FParsec，你显然必须 implement this function such that it uses the heap instead of the stack用于跟踪嵌套上下文和中间解析结果。
关于.net - FParsec 中的尾递归，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/9251971/