FeatureTreeTraversal

Feature - Additional tree traversal support

Tree traversal should be enhanced to support selective node order, downward node value propagation and non-destructive operation.

Rationale

The current API for parse tree traversal in Grammatica is defined by the Analyzer class (and any generated subclasses). It is based on the idea of creating and analyzing the parse tree at the same time, allowing the analyzer to reduce memory consumption by skipping or removing nodes at will.

When generating a second pass analyzer or when providing other analysis runs over the parse tree, the current Analyzer API isn't always so practical. In particular, it lacks support for the following features:

• Selective Node Order - The node visiting follows a strict top-down and left-to-right algorithm, leaving no room for omitting or changing the traversal order of sub-nodes in the tree.
• Downward Value Propagation - Once a parse tree has been built, subsequent analysis should be able to pre-define values for usage in child nodes. There is currently no support for this, as each parse tree analysis will re-create any child nodes (and values).
• Non-Destructive Operation - A new parse tree is always built by the analyzer, which would typically be unnecessary during secondary analysis runs. Ideally the same API should be possible to use for both the initial creation and subsequent analysis runs.
• Simplified Analysis Results - Results from the node analysis is currently stored inside an array in each parse tree node. This seems wasteful, since lots of parse tree nodes will be created without ever getting a value. Also, node values should be easier to retrieve and set during analysis.

Discussion

Introducing two new API:s might help to improve the situation:

• Traversal API - A new tree traversal API could be introduced, skipping all of the node creation semantics from the current Analyzer API. This traversal API could be called automatically from the generated analyzer, allowing the same tree traversal API to be used for all analysis passes. Doing changes to the generated parse tree would still require subclassing the generated Analyzer class, however.
• Value Stack API - Using some clever stack or tree data structure with built-in helper methods would perhaps allow the removal of node values from the parse tree nodes themselves. Doing so would allow parse tree analysis to propagate values either way, thereby resolving several issues at once.

The two ideas above must be worked out in detail however, in order to properly judge their viability and usefulness.