The Parse Tree

Mathias edited this page Jan 26, 2011 · 4 revisions
Clone this wiki locally

parboiled can optionally build a parse tree during the rule execution phase. Looking at the parse tree can give you a better understanding of how your parser digested a given input and is therefore especially helpful during parser development and debugging.

The parse tree created by parboiled consists of immutable object instances satisfying the Node interface. Apart from basic tree node functionality (parent, children) this interface defines a node name (the label), start/end locations for matched input text and a custom value object. There are a few utility classes defining static convenience methods for efficiently working with parse trees (and trees/graphs in general), namely ParseTreeUtils, TreeUtils and GraphUtils.

One important thing to keep in mind is that parse tree nodes are immutable, i.e. once they have been constructed there is no way to change anything about them. In particular this means that their sub node structure and their value object reference cannot be altered. (Even though their value object, should it be mutable, might still accept changes.) One consequence is that the whole parse tree is built bottom up, starting with the leaf nodes. In general, if parse tree building is enabled, each rule that successfully matched creates a parse tree node that has the nodes created by the successfully matched sub rules as children. A rule that did not match creates no parse tree node. In that regard the parse tree can be thought of as “the record of matched rules”. parboiled sets the value field of a parse tree node to the top element of the value stack at the time of the node construction. So looking at the parse tree value objects can give you a clue of how your parser works with the value stack.
Maybe the most useful thing to do with a parse tree is to print it using the static printNodeTree method of the ParseTreeUtils class.

Enabling Parse Tree Building in Java

You enable parse tree building by decorating your parser class with a @BuildParseTree annotation. You can then fine-tune parse tree and -branch creation by using the @SuppressNode, @SuppressSubnodes and @SkipNode annotations on your rule methods.

Enabling Parse Tree Building in Scala

parboiled for Scalas Parser trait has a boolean flag called “buildParseTree” that needs to be set to true before the root rule is being built in order to enable parse tree building. The easiest way to do this is to append “.withParseTreeBuilding()” to the constructor call of your parboiled for Scala parser. Similar to parboiled for Java you can then fine-tune the parse tree creation by passing one of the defined case objects derived from Parser#RuleOption to the “rule” call of your rule creation method.