解析爲遞歸數據結構

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的示例，以下是我最近編寫的一個小解析器的一個片段。它解析括號內空格分隔整數的列表（並且列表可以嵌套），「整數」可以是小算術表達式，如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的回答的評論，但是評論不能包含很好格式的代碼。繼續並接受他的回答;我的意圖是要充實他的。