[antlr-interest] Article against TreeWalkers

[mental at rydia.net]

Quoting Andrew Bell <andrew.bell.ia at gmail.com>:

> But aren't you parsing input _text_.  Isn't what this is all
> about?  What do DOWN and UP do here?  Is there a token in the
> input called UP or DOWN?

It's just a notional thing; they don't actually exist as tokens in
the grammar or in any real way in ANTLR.

It might help if you imagined an ordinary (1-d) rule where each
token were succeded by a navigation operation:

For example:

 a : A B C ;

could (notionally) be written:

 a : A NEXT B NEXT C NEXT ;

NEXT simply indicates the normal behavior of advancing to the next
token.

However, when your tokens happen to be nodes in a tree, there are
additional navigation possibilities.  You could still use NEXT to
advance to the next sibling token (i.e. node), but you also have:

 * UP - moves to the parent of the current node

 * DOWN - moves to the first child of the current node

This is a bit like the way that zippers unravel a tree into a
sequence of navigation operations, though through a different axis.

A 1-d sequence is simply a special case of a large family of data
structures.  In principle, given appropriate navigation primitives,
this approach to parsing could be generalized to pretty much any
acyclic data structure.

> You aren't really parsing a tree, you are building a tree.
> You are parsing a 1-D input and producing a tree output, right?
> What am I missing here?

In this case he really is talking about parsing one tree directly
and outputting another.

-mental