[antlr-interest] Re: Exception tests eat performance?

[lgcraymer]

Tom--

The problem is that syntactic predicates are implemented through
exceptions and that larger grammars tend to have enough ambiguities
(some due to the approx-LLk algorithm) to require a sizeable number of
syntactic predicates so that the resultant applications throw lots of
exceptions.

Ter's LL-regular analysis (which includes "under the hood" left
factoring) will cut down on the number of synpreds in application
grammars, but probably not eliminate them.

Syn preds also lead to redundant computation--first you traverse rules
in "guessing" mode and then in "action" mode to do the actual tree
construction and action execution.  That is also expensive.

There are two optimization approaches which would work to cut down
synpred overhead.  One of these is to "log" a record of parsed tokens
when guessing and then to process that log as soon as a parse has been
committed to.  The alternative is to implement synpreds as function
calls and to inline any rules called (recursion-to-iteration
transformation might be desirable) by the synpred.  Some additional
analysis might serve to generate minimal synpreds.  I haven't a clue
as to which approach would lead to better performance, but I think
that the second approach could be implemented within ANTLR 2 with 2-3
weeks of solid work--it's mostly adding a second walk through the
custom graph which ANTLR uses internally.  Having dug into ANTLR 2
internals, though, I think that I'll wait for ANTLR 3.

Cheers!

--Loring


--- In antlr-interest at yahoogroups.com, Tom Moog <tmoog at p...> wrote:
> 
> I thought java exceptions were expensive only if they
> were thrown, and that try blocks were relatively
> cheap.  One would think that in the worst case they
> would just require pushing an exception handler address
> onto a stack (on entering the try block) and popping it
> off on exit - or is this the overhead you're talking about ?


 

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/