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

Jim Idle jimi at temporal-wave.com
Tue Feb 5 12:24:54 PST 2008



> -----Original Message-----
> From: Andreas Bartho [mailto:andreas.bartho at inf.tu-dresden.de]
> Sent: Tuesday, February 05, 2008 12:19 PM
> To: Mark Volkmann
> Cc: antlr-interest at antlr.org
> Subject: Re: [antlr-interest] syntactic predicates vs. backtrack=true
> 
> Hi Mark,
> 
> > To me this statement implies that the backtrack option is just a
> > shortcut for inserting syntactic predicates.
> 
> That's right.
> 
> > Doesn't that mean that
> > these rules are equivalent in both behavior and
> > performance?
> 
> Not necessarily. Consider, for example, C#'s typedeclaration rule:
> 
> typedeclaration
>      :   classdeclaration
>      |   structdeclaration
>       ...
>      ;
> 
> With backtracking on, this becomes:
> 
> typedeclaration
>      :   (classeclaration) => classdeclaration
>      |   (structdeclaration) => structdeclaration
>       ...
>      ;
> 
> This is an awful lot of overhead. To distinguish the alternatives one
> would only need to check for a special keyword. This can be done by
> manually specifying a syntactic predicate.
> 
> typedeclaration
>      :   (attributes? classmodifiers? PARTIAL? CLASS) =>
> classdeclaration
>      |   (attributes? structmodifiers? PARTIAL? STRUCT) =>
> structdeclaration
>      ....
>      ;
> >  ;

Not the best example though as you dont need backtracking or 
predicates to parse C#, other than the one that the spec ordains ;-)

Jim



More information about the antlr-interest mailing list