Parsing recursive data structures

Using Swift
,
1

@stephencelis @mbrandonw I've been playing with some of the Parser Combinator stuff y'all have introduced on point free and I was wondering if you guys had ideas on how to create a parser for a recursive data structure without creating circular references when declaring the parser.

Say I have a simple format that encodes ints as "int<integer_value>done" and lists as "list<element>...done" where lists can contain other lists.

I would represent the data structure for this in swift as an enum like this:

enum Node {
  case int(Int)
  indirect case list([Node]
}

And declare a parser for Nodes like this: (assuming many extensions covered in your videos)

let intNode = Parser
  .skip("int")
  .take(.int)
  .skip("done")
  .map { Node.int($0) }

let listNode = Parser
  .skip("list")
  .take(node.zeroOrMore())
  .skip("done")
  .map { Node.list($0) }

let node = Parser
  .oneOf(intNode, listNode)

These parsers aren't instantiable, due to the circular references through list -> node -> list. Any ideas on how to address this sort of error?

2

Hi @rauhul, I'm not sure this is the best place for these kinds of discussions. I believe this forum is for general Swift questions. Feel free to reach out to us via email to ask questions.

To answer your question you just need to introduce a bit of laziness in your parser:

var listNode: Parser<Substring, Node> {
  Parser
    .skip("list")
    .take(node.zeroOrMore())
    .skip("done")
    .map { Node.list($0) }
}

You can find more info here: Recursions in Parsers · Issue #63 · pointfreeco/episode-code-samples · GitHub :slightly_smiling_face:

1 Like
3

Feel free to reach out to us via email to ask questions.

Sounds good, thanks for the GitHub link as well :)