[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