再帰的なデータ構造を解析する

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の答えにこれをコメントとして書きますが、コメントにはきれいにフォーマットされたコードを入れることはできません。彼の答えを受け入れてください。私はちょうど彼の肉を肉にしようとしています。