[antlr-interest] syntactic predicates and exceptions

Terence Parr parrt at cs.usfca.edu
Tue Oct 18 08:31:35 PDT 2005


Howdy,

Many people have complained about the fact that ANTLR uses exceptions  
for backtracking and it's slow in many languages and many grammars.   
For v3 I was thinking of changing to be return values and lots of IF  
checks everywhere...ugly but fast.

Then i realized last night that it's not so easy.  We use exceptions  
for throwing exceptions right?  All the support code for match,  
matchAny, blah blah throws exceptions, which would trigger rewinding  
the backtracking predicate in v2.  How can we use exceptions for  
error conditions and not for guessing?  Do people propose that we  
duplicate the support library code or put IFs everywhere in the  
support code, perhaps slowing all cases down?

Perhaps looking at javacc output (which avoids exceptions for  
backtracking I think) would be useful.  I don't like a mixed model.   
Remember, normal case you want exceptions and backtracking case you  
don't.  Pretty messy support code if you ask me.  Easy to say "get  
rid of exceptions", but now when it comes to doing it I don't see a  
clean solution.  I also hate the idea that even when not backtracking  
you'll see code like this everywhere (ugly and slower):

if ( !match(ID) ) {code inserted to clean up; return false;} //  
indicate error if guessing

instead of the current

match(ID);

Note: java can use a try/finally for the cleanup code but other  
languages will need perhaps a goto or to duplicate cleanup code at  
*all* exit sites...ick.

Ideas for implementing backtracking without exceptions?

Ter


More information about the antlr-interest mailing list