2017-07-20 16 views
5

Ich möchte eine Zeichenfolge in einer rekursiven Datenstruktur # Verwendung von F analysieren. In dieser Frage werde ich ein vereinfachtes Beispiel vorstellen, das den Kern dessen, was ich tun möchte, aufzeigt.Parsing in einer rekursiven Datenstruktur

Ich möchte auf die Satzart eine Reihe von verschachtelten eckigen Klammern analysieren:

type Bracket = | Bracket of Bracket option 

So:

  • "[]" ->Bracket None
  • „[[]] "->Bracket (Some (Bracket None))
  • "[[[]]]" ->Bracket (Some (Bracket (Some (Bracket None))))

Ich möchte dies mit den Parser-Kombinatoren in der FParsec-Bibliothek tun. Hier ist, was ich bisher:

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 

Ich habe sogar einige Expecto Tests:

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 

Das Problem ist natürlich, wie und beliebige Ebene der Verschachtelung zu handhaben - den obigen Code funktioniert nur für auf 3 Ebenen. Der Code, den ich wiewürde zu schreiben ist:

let rec pNestedBracket = 
    pchar '[' 
    >>. tryP pNestedBracket 
    .>> pchar ']' 
    |>> Bracket 

Aber Fis dies nicht zulässt.

Bin Belle ich den falschen Baum komplett mit bis wie diese zu lösen (ich verstehe, dass es einfachere Wege, dieses spezielle Problem zu lösen)?

Antwort

5

Sie suchen FParsecs createParserForwardedToRef Methode. Da Parser Werte und keine Funktionen sind, ist es nicht möglich, wechselseitig rekursive oder selbstrekursive Parser zu erstellen. Um dies zu tun, müssen Sie in gewissem Sinne einen Parser deklarieren, bevor Sie ihn definieren.

Ihr endgültiger Code wird so etwas wie diese

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 

Auch am Ende aussehen würde ich diesen Artikel für grundlegendes Verständnis der Parser Kombinatoren empfehlen. https://fsharpforfunandprofit.com/posts/understanding-parser-combinators/. Der letzte Abschnitt über einen JSON-Parser spricht über die createParserForwardedToRef Methode.

+0

Dank Thomas - wird als Antwort markieren, wenn ich eine Chance auf Arbeit durch sie gehabt haben. – Lawrence

2

Als Beispiel dafür, wie createParserForwardedToRef zu verwenden, hier ist ein Ausschnitt aus einem kleinen Parser ich kürzlich schrieb. Es analysiert Listen von durch Leerzeichen getrennten Ganzzahlen in Klammern (und die Listen können verschachtelt sein), und die "Ganzzahlen" können kleine arithmetische Ausdrücke wie 1+2 oder 3*5 sein.

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. Ich hätte dies Thomas Devries 'Antwort als Kommentar hinzugefügt, aber ein Kommentar kann keinen schön formatierten Code enthalten. Geh voran und akzeptiere seine Antwort. meins ist nur dazu gedacht, sein Leben zu füllen.

Verwandte Themen