Analysis in a recursive data structure

Question

I want to parse a string in a recursive data structure using F #. In this question, I will give a simplified example that will shorten the core of what I want to do.

I want to parse a string of nested square brackets in a record type:

type Bracket = | Bracket of Bracket option 

So:

• "[]" → Bracket None
• "[[]]" → Bracket ( Some ( Bracket None) )
• "[[[]]]" → Bracket ( Some ( Bracket ( Some ( Bracket None) ) ) )

I would like to do this using parser combinators in the FParsec library. Here is what I still have:

 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 

I even have 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 

The problem, of course, is how to handle an arbitrary level of nesting - the above code only works for three levels. The code I would like to write:

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

But F # does not allow this.

I completely bark the wrong tree, how can I solve this (I understand that there are simpler ways to solve this particular problem)?

Answer 1

You are looking for the FParsecs createParserForwardedToRef method. Because parsers are values, not functions, it is impossible to make mutually recursive or self-recursive parsers to do this, you must, in a sense, declare a parser before defining it.

Your last code will look something like this.

 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 

I would also recommend this article for a basic understanding of parser combinators. https://fsharpforfunandprofit.com/posts/understanding-parser-combinators/ . The last section of the JSON parser talks about the createParserForwardedToRef method.

Answer 2

As an example of using createParserForwardedToRef , here is a snippet from a small parser that I wrote recently. It analyzes lists of spatially separated integers between brackets (and lists can be nested), and “integers” can be small arithmetic expressions such as 1+2 or 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 ']' 

PS I would put this as a comment on Thomas Devrius' answer, but a comment cannot contain nicely formatted code. Go and accept his answer; mine is just to lure him.