[antlr-interest] How does AST construction work?

Bryan Ewbank ewbank at gmail.com
Tue May 17 04:51:25 PDT 2005


Your reasoning is correct that the elements are appended into a list.

I'm not sure how you are printing the '2' you saw, but I'm pretty sure
the whole list was returned - the first element of the list is the
tree containing '2' as its singleton root, and the rest of the list is
not printed.

In C++, for example, you would use toStringTree() to generate the '2',
but toStringList() will generate the list of elements.  I'm sure there
are similar functions - might even be the same names - in other
languages, but I don't know.

The "problem" with ANTLR here is that there is a list at the top
level; you must wrap another node around the top level to get a tree. 
This was a stumbling block for me initially:

  foo: expr { ## = #( #["FOO",FOO], ## ); } ;
  expr : mexpr (PLUS mexpr)* SEMI! ;
  mexpr : atom (STAR atom)* ;

Calling expr() will produce a list of matching tokens; calling foo()
instead will return a tree (i.e., a list with one element) with the
internal node FOO.

On 5/17/05, Paul Johnson <gt54-antlr at cyconix.com> wrote:
> I tried this, and the returned tree just contains '2':
> 
> expr : mexpr (PLUS mexpr)* SEMI! ;
> mexpr : atom (STAR atom)* ;
> 
> -----
> > Main
> > 2+4*5;
>   2
> value is 2
> -----
> 
> At first sight, it seems to me that the returned list should actually
> have been ( 2 + 4 * 5 ) (with no root - or does the first parsed element
> become the root by default?)
> 
> My reasoning is simply that the first call to mexpr returns the list
> (2), then PLUS is appended, and the second call to mexpr returns the
> list (4 STAR 5). How is it that just a single '2' is returned?
> 
> Thanks -
> Paul


More information about the antlr-interest mailing list