Suppose I need a parser to handle tree-like input (e.g. scala.xml.Elem) instead of strings. I would like to use the parser combinators from this article. If I linearize the input tree I can write such a parser easily.
type Parser[A] = seq: Seq[Elem] => List[(A,Seq[Elem])]
I can add parsers return, failure, item, etc. and finally write my parsers on top of them.
Now I wonder if I can make a parser without linearizing the input tree. Is it possible ?
Great question. It is absolutely possible to do this, and I've been looking for a tool that does it for a while.
I think the key is that the structure of your tree will be reflected in your primitive combinators. For instance, the primitive item parser is tied to the [] container type, and provides the ability to sequentially walk down a list by first/resting it. return and failure do not depend on the [] container type, so they shouldn't have to be changed to support tree parsing.
You'll need to replace it with one or more combinators that allow you to traverse a tree. I would guess that you'd want one combinator to let you move between siblings (i.e. children of the same parent node, at the same depth), and a second combinator to allow you to go deeper into the tree.
What I'm not sure about is whether you'll need duplicate combinators to correspond to capture the patterns of sequencing, alternation, lookahead, and so on. Having to implement each of those twice could get pretty obnoxious.
nextbro to move to the next sibling and oldson to move to the "oldest" child -- are what I am thinking of.
<a><a1/><a2/></a>.