[antlr-interest] syntactic predicates vs. backtrack=true

[Daniels, Troy (US SSA)]

> -----Original Message-----
> From: antlr-interest-bounces at antlr.org 
> [mailto:antlr-interest-bounces at antlr.org] On Behalf Of Johannes Luber
> Sent: Tuesday, February 05, 2008 9:06 AM
> To: Mark Volkmann
> Cc: antlr-interest
> Subject: Re: [antlr-interest] syntactic predicates vs. backtrack=true
> 
> Mark Volkmann schrieb:
> > Thanks! I learned some new things by reading that. I'm 
> still a little 
> > confused though. In section 12.2 of the book (page 300 in 
> my copy) it
> > says:
> > 
> > "ANTLR also supports an auto-backtracking feature whereby ANTLR 
> > inserts syntactic predicates on the left edge of every alternative."
> > 
> > So it seems to me that these rules are equivalent in both 
> behavior and 
> > performance.
> > 
> > foo
> > options { backtrack = true; }
> >   : option1
> >   | option2
> >   | option3
> >   ;
> > 
> > foo
> >   : (option1)=> option1
> >   | (option2)=> option2
> >   | option3
> >   ;
> > 
> > If this is true then I think I prefer using backtrack 
> because it adds 
> > less clutter to the rule.
> > 
> 
> I'm not sure if that is the only tradeoff here, but Ter can 
> answer this better than I can here.
> 

Once advantage is that you can make an explicit syntactic predicate
terminate much quicker to evaluate than the full expression.  Consider a
rule for a java language parser that matches where you actually begin to
define a class or interface.  A plausible way to write this is

classOrInterfaceWithPredicate
	: (classModifier* CLASS) => classDefinition
	| (classModifier* INTERFACE) => interfaceDefinition
	;

classOrInterfaceWithBacktracking { backtrack = true; }
	: classDefinition
	| interfaceDefinition
	;

With backtracking, it would parse the entire class (possibly thousands
of symbols), then determine that it was a class and redo the parse with
actions enabled.  With an explicit predicate, once if finds the "class"
token (almost certainly in the first 5 tokens), it knows that this will
match a class and can restart immediately.

Troy

> Johannes
>