[antlr-interest] Problems with AST construction

[Loring Craymer]

The steps you need to take are to first expand the
elements of primary:

primary
    :
    Identifier
    |
        primary
        (
             invocation_rest
             |
                  increment_rest
        )
    ;

and from this, Identifier is the non-recursive form,
so

primary
    :
    Identifier
    (
         invocation_rest
         |
              increment_rest
    )*
    ;


--- Andreas Bartho <andreas.bartho at inf.tu-dresden.de>
wrote:

> Hello,
> 
> I'm currently trying to remove left recursion from a
> large Grammar (C#). 
> I've run into some problems, however, and would be
> grateful for any help.
> 
> This is an edited excerpt of the grammar.
> 
> primary : 	Identifier | invocation | increment;	
> 	
> invocation :	primary invocation_rest;
> 	
> increment  :	primary increment_rest;	
> 
> invocation_rest : '(' '.'? ')';
> 	
> increment_rest : '++';	
> 
> Identifier :   'a'..'z'*;
> 
> 
> An AST for i()() should look like (Invocation
> (Invocation Identifier '(' 
> ')' ) '(' ')' ).
> There are rules not displayed here that can refer to
> either primary or 
> invocation/increment.
> 
> 
> To remove left recursion I have experimented with
> repetition operators, 
> but to no avail.
> 
> A grammar like the following works, but only for
> this toy example.
> 
> primary : 	primary_rec | Identifier;	
> 	
> primary_rec :	Identifier (invocationrest |
> incrementrest)*;	
> 
> invocation :	primary invocationrest;
> 	
> increment  : 	primary	'++';	
> 	
> invocationrest : '(' '.'? ')' ;
> 
> incrementrest :	'++';	
> 
> Identifier: 'a'..'z'*;
> 
> Once the grammar gets bigger, ANTLR runs into
> problems, because it can't 
> decide, for example, whether it should match an
> invocationrest in rule 
> primary_rec or in rule invocation.
> 
> Using right-recursion seems to work:
> 
> tokens {
> 	Invocation;
> 	Increment;
> }
> 
> primary : primary_start primary_rec*;	
> 	
> primary_start :	Identifier;
> 	
> primary_rec :	invocation_rest	| increment_rest;	
> 
> 
> invocation
> 	:	primary_start invocation_rec
> 	->	^(Invocation primary_start invocation_rec)
> 	;
> 	
> invocation_rec
> 	:	primary_rec invocation_rec
> 	//makes AST right associative
> 	//->	^(Invocation primary_rec invocation_rec)
> 	|	invocation_rest
> 	;	
> 			
> invocation_rest : '(' '.'? ')';
> 
> increment
> 	: 	primary_start increment_rec
> 	->	^(Increment primary_start increment_rec)	
> 	;	
> 
> increment_rec
> 	:	primary_rec increment_rec
> 	//makes AST right associative	
> 	//->  ^(Increment primary_rec increment_rec)
> 	|	increment_rest
> 	;	
> 		
> increment_rest : '++';	
> 
> Identifier :   'a'..'z'*;
> 
> The problem is that due to the right-recursion the
> resulting trees are 
> right-associative, yielding a tree like (Invocation
> Identifier 
> (Invocation '(' ')' '(' ')' ) )
> Furthermore, the trees must also be created when
> rule 'primary' is 
> called, leaving only 'primary_rec' for tree
> construction. But I just 
> don't get iterative AST construction to work here.
> Does anyone have an idea?
> 
> Andreas
> 



       
____________________________________________________________________________________
Choose the right car based on your needs.  Check out Yahoo! Autos new Car Finder tool.
http://autos.yahoo.com/carfinder/