对递归数据结构的解析

Question

我希望使用F#将字符串解析为递归数据结构。在这个问题中，我将给出一个简单的例子，这个例子切入了我想要做的事情的核心。

我想将嵌套方括号中的字符串解析为记录类型：

type Bracket = | Bracket of Bracket option

所以：

• "[]“-> Bracket None
• "[[]]“-> Bracket ( Some ( Bracket None) )
• “[]]”-> Bracket ( Some ( Bracket ( Some ( Bracket None) ) ) )

我想使用FParsec库中的解析器组合器来完成这个任务。以下是我到目前为止所拥有的：

let tryP parser = 
    parser |>> Some
    <|>
    preturn None

/// Parses up to nesting level of 3
let parseBrakets  : Parser<_> = 

let mostInnerLevelBracket = 
    pchar '[' 
    .>> pchar ']'
    |>> fun _ -> Bracket None

let secondLevelBracket = 
    pchar '['
    >>. tryP mostInnerLevelBracket
    .>> pchar ']'
    |>> Bracket

let firstLevelBracket = 
    pchar '['
    >>. tryP secondLevelBracket
    .>> pchar ']'
    |>> Bracket

firstLevelBracket

我甚至还做了一些测试：

open Expecto

[<Tests>]
let parserTests = 
[ "[]", Bracket None 
    "[[]]", Bracket (Some (Bracket None))
    "[[[]]]", Bracket ( Some  (Bracket (Some (Bracket None))))  ]
|> List.map(fun (str, expected) -> 
    str
    |> sprintf "Trying to parse %s"
    |> testCase
    <| fun _ -> 
    match run parseBrakets str with
    | Success (x, _,_) -> Expect.equal x expected "These should have been equal"
    | Failure (m, _,_) -> failwithf "Expected a match: %s" m
)
|> testList "Bracket tests"

let tests = 
[ parserTests ]
|> testList "Tests"

runTests defaultConfig tests

当然，问题是如何处理任意级别的嵌套--上面的代码只适用于3个级别。我想编写的代码是：

let rec pNestedBracket = 
    pchar '['
    >>. tryP pNestedBracket
    .>> pchar ']'
    |>> Bracket

但F#不允许这样做。

我是不是完全搞错了如何解决这个问题(我知道有更容易的方法来解决这个问题)？

Answer 1

您正在寻找FParsecs createParserForwardedToRef方法。由于解析器是值而不是函数，因此不可能进行相互递归或自递归解析，因此在定义解析器之前，必须在某种意义上声明解析器。

您的最终代码将以如下方式结束

let bracketParser, bracketParserRef = createParserForwardedToRef<Bracket>()
bracketParserRef := ... //here you can finally declare your parser
    //you can reference bracketParser which is a parser that uses the bracketParserRef

此外，我还将推荐本文，以便对解析器组合子有基本的理解。https://fsharpforfunandprofit.com/posts/understanding-parser-combinators/。JSON解析器的最后一节将讨论createParserForwardedToRef方法。

Answer 2

作为如何使用createParserForwardedToRef的一个例子，下面是我最近编写的一个小型解析器的片段。它分析括号之间空格分隔的整数列表(列表可以嵌套)，“整数”可以是小算术表达式，如1+2或3*5。

type ListItem =
    | Int of int
    | List of ListItem list

let pexpr = // ... omitted for brevity

let plist,plistImpl = createParserForwardedToRef()

let pListContents = (many1 (plist |>> List .>> spaces)) <|>
                    (many  (pexpr |>> Int  .>> spaces))

plistImpl := pchar '[' >>. spaces
                       >>. pListContents
                       .>> pchar ']'

我会把这作为对Thomas的回答的评论，但是注释不能包含格式良好的代码。去接受他的答案吧，我的回答只是为了充实他。