[antlr-interest] Questions about ANTLR tree parsers

[Bryan Ewbank]

Hi Suman, welcome to the list...

On 10/29/05, Suman Karumuri <mansuk at gmail.com> wrote:
> Hi ,
>
> 1) Can anyone explain me what this action does. I have taken this
> example from the calc.g file in antlr examples.
>
> expr :  expr1        { ## = #(#[EXPR,"expr"],##); }    ;

This means
(1) Create a new EXPR node
(2) Place the current version of the output tree for this rule
    as the only child of that node
(3) Use that new tree as the output tree for this rule

If this is not working, make sure you have buildAST=true; it might
do weird things otherwise.


> 2) There are no docs on how to write the grammar for a tree parser.
> >From what i have read and understood, this is the conclusion i have
> reached:
>
> " A parser grammar is shows associativity and precedence where as the
> tree parser grammar is the grammar
> - Without associativity
> - Without precedence
> - Without delimiting characters.
> "
>
> Is that correct?

Please take a look at the PDF manual; there's a chapter about tree grammars.

I think what you say is correct, though I would say it like this:

- A tree HAS NO ASSOCIATIVITY, and NO PRECEDENCE; just shape.
- A tree has only those tokens you placed in it.

What you built in the parser (or previous tree grammar) is what you have.

Said another way, you don't (typically) build a tree like this:
	#(+ A B C)
Instead, you build this:
	#(+ #(+ A B) C)
Therefore, associativity is implied in the tree.

The same is true for precedence; you don't produce a tree that looks like this:
	#(EXPR A * B + C)
But rather whichever is needed for correct processing:
	#(* A #(+ B C) )
	#(+ #(* A B) C)
Or something like this if you'd rather not use trees (though this is ANTRL, and
ANTLR does trees :-)
	#(EXPR * A + B C )
	#(EXPR + * A B C )	

> 3) I have a problem grouping multiple trees as a single node from a
> rule.For example in the below grammar:
>
> program :       stmt;
>
> stmt    :       expr EOL
>         |!      v:VAR EQUALS s:expr EOL
>         { #v.setType(VAR_NAME); #stmt = #(#EQUALS, #s, #v); }
>         |       PRINT^ expr EOL!
>         |       WHILE^ cond sl:stmt_lst { #sl.setType(STMT_LIST);}
>
> stmt_lst:       BEGIN! (EOL!)* (stmt)* END! (EOL!)*
>
> expr : // This is an expression
>
> I want the statement list to be a subtree of while root. But the above
> set type does not seem to work. Am i  missing something important?

Hmm.  I think so.  You are overwriting the first element in stmt_lst,
rather than
introducing a collector node.  Try replacing stmt_lst with this:

	stmt_list:	BEGIN^ (EOL!)* (stmt)* END! (EOL!)*
			{ ##.setType(STMT_LIST); }

Also remove the action on the WHILE line...

The problem is that the original grammar left the stmt_lst as a list of
siblings, rather than a tree with a single root.  Not a problem, really, until
it's used.  Drawing what this grammar does to a WHILE:

	#(WHILE cond STMT_LIST s2 s3 ... sN)
		// s1 type is replaced with STMT_LIST

With the changed stmt_list rule:

	#(WHILE cond #(STMT_LIST s1 s2 ... sN) )

>
> 4) How is this rule in parser translated to tree parser?
>		program = (stmt)*
> But in the tree parser this doesn't seem to work:
>		program = #(stmt)*

I don't understand this question, so have to say "what do you mean?"  A tree
parser's rules have to match trees, rather than be sequences of tokens; but
there's not enough in the fragments to see what you are trying to do.