Parsing in to a recursive data structure

Question

I wish to parse a string in to a recursive data structure using F#. In this question I'm going to present a simplified example that cuts to the core of what I want to do.

I want to parse a string of nested square brackets in to the 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 the parser combinators in the FParsec library. Here is what I have so far:

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 some 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 is of course how to handle and arbitrary level of nesting - the code above only works for up to 3 levels. The code I would like to write is:

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

But F# doesn't allow this.

Am I barking up the wrong tree completely with how to solve this (I understand that there are easier ways to solve this particular problem)?

Thomas Devries · Accepted Answer · 2017-07-20T16:32:46.823

You are looking for FParsecs createParserForwardedToRef method. Because parsers are values and not functions it is impossible to make mutually recursive or self recursive parsers in order to do this you have to in a sense declare a parser before you define it.

Your final code will end up looking 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

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

Thanks Thomas - will mark as the answer once I've had a chance to work through it. — Lawrence, Jul 20 '17 at 16:28

score 4 · Answer 2 · answered Jul 21 '17 at 03:29

As an example of how to use createParserForwardedToRef, here's a snippet from a small parser I wrote recently. It parses lists of space-separated integers between brackets (and the lists can be nested), and the "integers" can be small arithmetic expressions like 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 ']'

P.S. I would have put this as a comment to Thomas Devries's answer, but a comment can't contain nicely-formatted code. Go ahead and accept his answer; mine is just intended to flesh his out.

Parsing in to a recursive data structure

2 Answers2

Linked