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

[Andreas Bartho]

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
     ....
     ;

The whole stuff after the keyword isn't processed any longer.

Please that for the example backtracking might not be necessary at all. 
I haven't tested it yet. But it illustrates the point.

Andreas Bartho


If not, can someone explain how they differ at runtime?
> Note that I'm specifying the backtrack option on a specific rule, not
> on the entire grammar.
> 
> foo
> options { backtrack = true; }
>  : option1
>  | option2
>  | option3
>  ;
> 
> foo
>  : (option1)=> option1
>  | (option2)=> option2
>  | option3
>  ;
>