解析为递归数据结构

劳伦斯

我希望使用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＃不允许这样做。

我是否完全以错误的方式解决问题（我知道有解决此特定问题的简便方法）？

托马斯·德弗里斯

您正在寻找FParsecscreateParserForwardedToRef方法。由于解析器是值而不是函数，因此无法进行相互递归或自递归解析器来执行此操作，从某种意义上讲，必须在定义解析器之前声明它。

您的最终代码将最终看起来像这样

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

本文收集自互联网，转载请注明来源。

如有侵权，请联系 [email protected] 删除。