[antlr-interest] open-ended speed question: order of magnitude comparison?

Terence Parr parrt at cs.usfca.edu
Wed Nov 19 10:11:26 PST 2003


Hi Tripp,

My only general comment about

>> Does anyone have a rough, order of magnitude, back of the
>> 	envelope, rule of thumb, etc. idea about the (runtime, lexing and
>> 	parsing and what-not) speed difference between a parser
>> 	generated with ANTLR, with one of the LALR(1) tools, or by hand
>> 	(by someone competent but not necessarily wizardly)?

is this: the theoretical complexity is linear for ANTLR's basic LL and 
yacc-n-friends LR-based stuff.  So, the thing you're fighting is the 
constant on the front.  That is, how fast can you spin in a for-loop or 
walk thru a state-machine.  Back in the 80's, tom pennello who works 
with deremer (inventor of LALR) did an LALR to x86 machine code 
generator.  That damn thing was FAST!

Also note that people use syntactic predicates with ANTLR to overcome 
limitations in LL or to handle nasty filth like C++.  This pushes you 
past linear and into potentially exponential complexity.  LALR parsers 
with actions reduce to LL in the worst case; they ain't much stronger 
than LL and sans predicates are much weaker, but they will always be 
linear.

Your constant may vary ;)

Terence


On Tuesday, November 18, 2003, at 03:24 PM, Tripp Lilley wrote:

>
> In another thread, John "Lingua Idiota" Mitchell wrote:
>
>> For example, if very high speed is so important then what the hell are
>> you doing using any "language" that needs such complexity to lex, 
>> parse,
>> understand, and act upon to solve the problem? I.e., why aren't you
>> using a purpose specific, fixed, highly normalized language that's
>> extremely easy to robustly deal with rapidly?
>
>
> I was searching for some really open-ended information on ANTLR
> performance (and, generally, performance of automatically-generated
> recognizers/parsers) when I stumbled on this. I was planning on posting
> this question anyway, but John's comment is of particular relevance to 
> it.
>
> The question, and then some qualifiers:
>
> 	Does anyone have a rough, order of magnitude, back of the
> 	envelope, rule of thumb, etc. idea about the (runtime, lexing and
> 	parsing and what-not) speed difference between a parser
> 	generated with ANTLR, with one of the LALR(1) tools, or by hand
> 	(by someone competent but not necessarily wizardly)?
>
> Now, to qualify that question:
>
> 	- I realize it's entirely open-ended and very much dependant on
> 	  unique characteristics of the grammar being recognized that
> 	  would either make it a "good" fit for automated recognition or a
> 	  "good" fit for hand coding.
>
> 	- As John's post suggests, some languages optimized for easy
> 	  parsing would be... parsed easily :-) which also implies that
> 	  writing a "more" efficient parser would be eas{y,ier}.
>
> However, in my particular application (or, at least, the application 
> I'm
> considering), I don't really have control over the "languages" that 
> would
> be recognized, and therefore their "parsability" characteristics.
>
> Furthermore, the entire point of my wanting to use generators is to not
> have to hand-code the parsers for each new language I encounter in the
> application (and there would be plenty). Moreover, I want the people
> extending my application to not have to hand-code new parsers as they
> expand the system (and writing new parsers is definitely an integral 
> part
> of expanding the system).
>
> Finally, I'm hoping to be able to use the generated parsers to do
> 'realtime' (for some values of "realtime") recognition of instances of 
> the
> languages.
>
> So, I realize that's entirely broad and open-ended. I'm not looking for
> any definitive statements, just general wisdom along the lines of 
> "well,
> no, you're screwed" or "you could probably do it" or "yeah, no problem,
> performance is comparable for all but the tightest languages 
> hand-coded by
> the most wizardly of parser mages".
>
> Thanks!
>
> - t.
>
>
>
>
>
>
> Your use of Yahoo! Groups is subject to 
> http://docs.yahoo.com/info/terms/
>
>
>
--
Professor Comp. Sci., University of San Francisco
Creator, ANTLR Parser Generator, http://www.antlr.org
Co-founder, http://www.jguru.com
Co-founder, http://www.knowspam.net enjoy email again!
Co-founder, http://www.peerscope.com pure link sharing




 

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




More information about the antlr-interest mailing list