.net - FParsec 中的尾递归-6ren

.net - FParsec 中的尾递归

转载作者：行者123 更新时间：2023-12-01 05:13:56

24

4

我遇到了具有两个递归分支的解析器的问题。为了更容易地演示问题，我使用了来自 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/

24

4

0

文章推荐： python - 在 Linux Mint 16 上安装适用于 Python 的 cx_Oracle

文章推荐： jquery - 使用 jQuery 通过滑动来制作动画

文章推荐： php - 使用ajax提交结帐表单

fparsec - 为什么 FParsec 使用列表？
我想我会尝试使用 FParsec 编写一个快速解析器并很快意识到 many 返回一个列表是一个严重的性能问题。然后我在文档中发现了一个使用 ResizeArray 的替代方法: let manyA2
f# - FParsec:如何在 fparsec 中解析日期(新手)
我正在使用 Bill Casarin关于如何使用 fparsec 解析分隔文件的帖子，我正在简化逻辑以了解代码的工作原理。我正在将多行分隔文档解析为 Cell 列表结构(目前)，其中 Cell 是字符
使用 FParsec 解析字符串文字？
我想使用 FParsec 解析字符串文字。 “字符串文字”是指介于开头和结尾引号之间的内容(在我的例子中是单引号): 'Please, switch off your mobile phone' 我目
f# - FParsec 标识符与关键字
对于带有关键字的语言，需要发生一些特殊的技巧以防止例如“if”被解释为标识符和“ifSomeVariableName”在 token 流中成为关键字“if”后跟标识符“SomeVariableName
使用 FParsec 解析日期和时间
在简单的查询语言中，我想识别日期和时间文字，最好不使用分隔符。例如， CreationDate = 2013-05-13 5:30 PM 我可以使用组合器来检测基本语法(例如， yyyy-MM-dd
f# - fparsec 中的位置信息
我的 AST 模型需要携带位置信息(文件名、行、索引)。是否有任何内置方式来访问这些信息？从引用文档中，流似乎带有位置，但我更喜欢我不必为了保存位置而实现虚拟解析器，并在任何地方添加它。提前致谢最
f# - FParsec 在很多方面都失败了
我有这个测试程序: open FParsec let test p str = match run p str with | Success(result, _, _) -> pr
parsing - FParsec:如何保存解析器成功的文本
为了在后面的步骤中创建更好的错误消息，我想保存解析器成功的位置以及文本。获取位置似乎很容易(因为有 getPosition 解析器)，但我不知道如何访问文本。假设我有这种类型来保存位置 type S
f# - FParsec 无法识别类型的构造函数
以下顶级 XML 解析器定义返回错误 The value or constructor ‘TOP_LEVEL_RECORD’ is not defined. … let xTop_Level, xTo
f# - 对空格敏感的 FParsec
我正在尝试使用 FParsec 实现一个对空格敏感的解析器，并且我从定义一个函数的第一步开始，该函数将解析以 n 开头的文本行。空格字符。这是我到目前为止所拥有的: let test: Parser
parsing - FParsec 选择以意想不到的方式表现
我计划将 FParsec 用于我的一个更大项目的原型(prototype)。所以我决定通过下面列出的测试程序来获得我对这个库的第一次体验。但似乎通过使用 fparsec 'choice' 函数组合我的
f# - FParsec:保留行号和列号
例如，从给定解析器中提取行号和列号以便将它们添加到 AST 中的最佳方法是什么？谢谢! 最佳答案您可以使用 getPosition，这是一个不消耗任何输入并返回当前位置的解析器。例如: type
parsing - FParsec 中的递归语法
我决定查看 FParsec，并尝试为 λ 表达式编写解析器。事实证明，渴望使递归解析变得困难。我该如何解决这个问题？代码: open FParsec type λExpr = | Varia
parsing - FParsec - 解析器序列
假设我有一些文字: a = "foobarbaz" b = "foobar" c = "foo" d = "rubbish" e = "foobazbar" 以及分别用于字符串 'foo'、'bar'
f# - fparsec - 限制应用解析器的字符数
我遇到一个问题，在流的解析过程中，我通过多次(按顺序)应用特定的解析器来指出需要解析下 N 个字符的位置。 (剥离玩具)示例: 17 0 then let! v
parsing - FParsec 中的示例语法超出了示例范围？
我正在寻找一些用 FParsec 编写的示例语法，这些语法超出了项目存储库中的示例。我发现这非常好grammar of GLSL ，但这是我找到的唯一样本。我需要的是类似于 C 或 JavaScri
parsing - FParsec - 解析器序列
假设我有一些文字: a = "foobarbaz" b = "foobar" c = "foo" d = "rubbish" e = "foobazbar" 以及分别用于字符串 'foo'、'bar'
f# - fparsec - 限制应用解析器的字符数
我遇到一个问题，在流的解析过程中，我通过多次(按顺序)应用特定的解析器来指出需要解析下 N 个字符的位置。 (剥离玩具)示例: 17 0 then let! v
f# - fparsec 解析字符串序列
我有一个用户输入文本，如“abc,def,ghi”。我想解析它以获取字符串列表 ["abc", "def"]. 我试过了 let str : Parser = many1Chars (noneOf "
.net - FParsec 中的尾递归
我遇到了具有两个递归分支的解析器的问题。为了更容易地演示问题，我使用了来自 the article written by Luca Bolognese 的 lambda 演算的简单语法。例如: ::

首页

博学

6Ren·AI

商城

.net - FParsec 中的尾递归