Recursions in Parsers

[ghost]

Hello there,

I know TCA is where most of your efforts are these days, but I've been rewatching your parsing collection and have run into a block. I'm hoping you can get me past that. I'm curious, how should one handle mutually recursive parsers? For example:

let value = oneOf([
    double.map(Value.number),
    array.map { _, elements, _ in Value.array(elements) }
])

let array = zip(
    literal("["),
    zeroOrMore(value, separatedBy: literal(",")),
    literal("]")
)

(Think of this as a simplified JSON.) Arrays have zero or more elements and those elements can also be arrays. The compiler (correctly) complains about a circular reference here. How does one typically get around this type of issue? It's sure to come up frequently even with relatively simple DSLs, like expressions.

Thanks for any pointers on this.

[mbrandonw]

Hey @tapcast-kevin, good question!

We really hope to get back to parsers soon, there's still so much left to talk about, including this recursion problem. I'll sketch out a simplified example of how to do recursive parsing and maybe you can extrapolate it to your use case.

Say you had this recursive enum:

indirect enum List {
  case empty
  case cons(Int, List)
}

And you wanted to parse strings like "1,2,3,4" into it. You can actually construct a parser that calls itself, you just have to express the parser as a function and make sure to call itself lazily:

let eol = Parser<Void> { str in str == "" ? () : nil }

func listParser() -> Parser<List> {
  oneOf([
    // If there is nothing left to parse then we can end with the `.empty` List
    eol.map { .empty },

    // If there's stuff left to parse then we can parse off a single int and 
    // an (optional) delimiter, and then `flatMap` onto that so that we 
    // can lazily run the parser again
    zip(int, oneOf([literal(","), eol]))
      .flatMap { head, _ in
        listParser().map { tail in .cons(head, tail) }
    }
  ])
}

And then to use it:

let p = listParser()
print(p.run("1,2,3").match!)

Hope that helps!

(NB: these code samples are based off where we left off in episode 64)

[mbrandonw]

Whoa, also I just realized that computed properties can be recursive, and so you don't even listParser to be a function:

let eol = Parser<Void> { str in str == "" ? () : nil }

var listParser: Parser<List> {
  oneOf([
    eol.map { .empty },
    zip(int, oneOf([literal(","), eol]))
      .flatMap { head, _ in
        listParser
          .map { tail in .cons(head, tail) }
    }
  ])
}

Only strange thing is that Swift has this warning even though the recursion is safe :/

[ghost]

Thanks @mbrandonw! I'm getting closer, but I need to study this a bit more to fully grok it. Thanks for the pointer

[ghost]

I ended up writing a similar "parsing" system for reading binary data from a mutable instance of Data (NSData). There wasn't any recursion to deal with, so that kept things simple. That exercise greatly increased my understanding of zip, map, flatMap, and even contraMap (pullbacks that I used for going in the other direction; writing binary). After that exercise, I came back to this problem and your solution now makes sense to me AND it works too! ;) I have a simple JSON parser in not much code, which is amazing to me. I have wanted to dive into this (combinator) style of parsing for a while, but it has been so foreign to my OOP/imperative/LALR mindset. Thanks again for the help and all of the videos!

[mbrandonw]

@tapcast-kevin this is really awesome to hear, I'm glad stuff is clicking!

(pullbacks that I used for going in the other direction; writing binary)

Interesting! When we get back into parsing episodes (hopefully a few months from now) we will be discussing the idea of "invertible parsing", which is the ability to simultaneously parse and print. Sounds like you are experimenting with something similar, which is cool!

[ghost]

I'm not there yet, but I'm working my way in that direction. That is indeed a fascinating topic.