On Jun 15, 2009, at 12:46 PM, Peter Goodman wrote:
>> Here's an example. This builds proper ASTs for additive expressions:
>>
>> add : atom ('+'^ atom)* ;
>>
>
> How does ^ work in the above context? Does it root the tree at the
> '+' with all child atoms?
The ^ is an operator that says "make that node the root of a new
subtree with the previous root as first child. So, each time through
the loop, the tree gets a little bit taller. You can find out a
little bit more here:
http://www.antlr.org/wiki/display/ANTLR3/Tree+construction
But I crammed most of my description into the language reference guide
book.
> The following is a pictorial explanation of
> my automatic reduction rule as well as my non-excludable and raise
> children operator.
>
> Given the grammar:
>
> Atom
> : -<number> /* note: this is a non-excludable */
> ;
>
> Additive
> : ^Additive '+' Atom
> : Atom
> ;
>
> And the sequence of tokens: 1 + 2 + 3, the untransformed parse tree
> appears as:
>
> Additive
> / | \
> Additive + Atom
> / | \ |
> Additive + Atom 3
> | |
> Atom 2
> |
> 1
>
> The automatic reductions raise up the numbers in place of the Atom
> as follows, and the '+' tokens are dropped as they are excludable:
>
> Additive
> / \
> Additive 3
> / \
> Additive 2
> |
> 1
>
> And finally the ^ raises the children of the two lower Additives up
> into the root Additive:
>
> Additive
> | | |
> 1 2 3
>
> The actual process does not involve distinct phase, this is all simply
> done as the parse tree is being built. Terrence, does the ^ operator
> in ANTLR work in a similar fashion?
That's interesting. In my case, I build ASTs as I parse; no parse tree
created. I think it's very easy to think of ^ as just creating a new
root node, pushing down the old root. It's surprising how much of a
grammar it works for.
Ter
_______________________________________________
PEG mailing list
PEG@lists.csail.mit.edu
https://lists.csail.mit.edu/mailman/listinfo/peg
