FParsec中的尾递归

Question

FParsec中的尾递归

pad*_*pad 3 .net f# tail-recursion fparsec

我遇到了解析器有两个递归分支的问题.为了更容易地证明这个问题,我使用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>

Run Code Online (Sandbox Code Playgroud)

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

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)

Run Code Online (Sandbox Code Playgroud)

我很感兴趣,pApplication因为它们由两个pExprs 组成,而s又可以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;;

Run Code Online (Sandbox Code Playgroud)

如何将解析器重写为尾递归？

在尝试为类似Lisp的语言编写解析器并使用真实的基准测试时,我意识到了这个问题.我有Term和VarBinding哪些是相互递归的类型和let解析器,它表现出与pApplication上面相同的问题.我的解析器在github上,以防关于非尾递归问题的分析是错误的.

Answer 1

Ste*_*orf 6

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

这意味着FParsec解析器的递归深度受到堆栈大小的限制 - 就像大多数递归下降解析器一样.当然,这并不影响与序列的分析many,sepBy,chainl等,因为这些FParsec组合算符恒栈空间的使用都有实现.

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

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

否则,您可能必须为语法的递归元素实现特殊用途的解析器函数.您将需要实现使用此功能的低 - 层次 API FParsec的,你会明显地要实现这个功能使得它使用堆而不是堆栈的用于跟踪嵌套上下文和中间的解析结果.

归档时间：	13 年，9 月前
查看次数：	351 次
最近记录：	13 年，9 月前