解析递归数据结构

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

我甚至有一些Expecto测试:

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方法.