解析为递归数据结构

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

Answer 2

作为如何使用 createParserForwardedToRef 的示例，这是我最近编写的一个小型解析器的片段。它解析括号之间 space 分隔的整数列表（并且列表可以嵌套），并且 "integers" 可以是小型算术表达式，例如 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 ']'

P.S。我会把它作为对 Thomas Devries 的回答的评论，但评论不能包含格式良好的代码。继续接受他的回答；我的只是为了充实他。

解析为递归数据结构

Parsing in to a recursive data structure

f#

fparsec