[antlr-interest] Exception tests eat performance?

mzukowski at yci.com mzukowski at yci.com
Wed Jan 7 09:14:49 PST 2004


There are other sources of exceptions which you would need to analyze the
code before knowing you could use goto.  For instance rules can have initial
actions, which are executed during syn preds and which could potentially
throw exceptions.  And when lookahead conditions aren't met we throw an
exception because remember the same code is used during syn preds and when
not in a syn pred.  So you would need a hook into the user exception
handling stuff so it would be handled a different way if you aren't
exceptioning out.

And of course you can't do this for java because of the lack of goto.  Maybe
you could get away with labeled breaks and continues, I haven't thought it
through yet.

This will be easier to experiment with in antlr 3 because writing code
generators will be template driven.

Monty

-----Original Message-----
From: Karl Meissner [mailto:meissnersd at yahoo.com] 
Sent: Wednesday, January 07, 2004 8:55 AM
To: antlr-interest at yahoogroups.com
Subject: [antlr-interest] Exception tests eat performance?


It seems that antlr uses exceptions in a lot of the generated parsers where
simple test will do. 
Everything that I have read is that an exceptions have a very high overhead
and it is undesirable 
to  generate them in a tight loop where they happen a lot. 

Exceptions are used so extensivly it would require a big rewrite to change
but I wanted to 
raise it as an issue

A very common piece of code in a parser is 

try {
  {
    match( SYM1 );
    match( SYM2 );
    match( SYM3 );
 }
} catch (RecognitionException)	{
  synPredMatched84 = false;
}

where match throws an exception if the next token is not the parameter. 
Since match is just
public virtual void  match(int t)
{
    if (LA(1) != t)
	throw new MismatchedTokenException(tokenNames, LT(1), t, false,
getFilename());
    else
	consume();
}


Using if based tests would be faster I think...

Something like this

bool Rule10() { 
  if( !Rule22() ) goto 	_RecognitionException_123:

  currentSym = SYM1; if ( LA( 1 ) != currentSym ) goto
_RecognitionException_123; consume(); 
  currentSym = SYM2; if ( LA( 1 ) != currentSym ) goto
_RecognitionException_123; consume(); 
  currentSym = SYM3; if ( LA( 1 ) != currentSym ) goto
_RecognitionException_123; consume(); 
    
  return true; 

  _RecognitionException_123:
    if (0 == inputState.guessing)
    {
      reportError(currentSym);
      consume();
      consumeUntil(tokenSet_27_);

      return true;  //attempt to recover in the calling rule
    }
    else //guessing
    {
	return false; 
    }
  }

I probably missed some the the code paths with predicate guessing and error
handling but 
I still think you can get the same behavior as the exception with a
combination of if, goto and
storing information into stack.   

And get a performance improvement....

Karl 
















__________________________________
Do you Yahoo!?
Yahoo! Hotjobs: Enter the "Signing Bonus" Sweepstakes
http://hotjobs.sweepstakes.yahoo.com/signingbonus

 

Yahoo! Groups Links

To visit your group on the web, go to:
 http://groups.yahoo.com/group/antlr-interest/

To unsubscribe from this group, send an email to:
 antlr-interest-unsubscribe at yahoogroups.com

Your use of Yahoo! Groups is subject to:
 http://docs.yahoo.com/info/terms/ 


 

Yahoo! Groups Links

To visit your group on the web, go to:
 http://groups.yahoo.com/group/antlr-interest/

To unsubscribe from this group, send an email to:
 antlr-interest-unsubscribe at yahoogroups.com

Your use of Yahoo! Groups is subject to:
 http://docs.yahoo.com/info/terms/ 




More information about the antlr-interest mailing list