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)?
Dank Thomas - wird als Antwort markieren, wenn ich eine Chance auf Arbeit durch sie gehabt haben. – Lawrence