[antlr-interest] syntactic predicates vs. backtrack=true
Daniels, Troy (US SSA)
troy.daniels at baesystems.com
Wed Feb 6 14:30:39 PST 2008
> -----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
>
More information about the antlr-interest
mailing list