SPARK / Earley Parser question

phil hunt philh at
Wed Apr 26 20:03:03 EDT 2000

On Wed, 26 Apr 2000 23:26:21 GMT, Stefan Franke <spamfranke at> wrote:
>I'm designing a grammar with John Aycock's SPARK toolkit. 
>Earley's algorithm is said to be n^3 time bound in general, n^2 for
>unambiguous grammars and linear for most practical programming
>language grammars. 
>Are there some rules of thumbs which kind of rules should be avoided
>to retain linear complexity? 
>In particular, I wonder if using empty right-hand sides for rules has
>any disadvantages.
>Online references would be appreciated.

The rule of thumb I use is: code it the simplest way possible, and
only try to speed it up if it is too slow.

I use SPARK to build the parser for my Parrot program[*]. I find it is 
fast enough for my purposes -- compiles c. 150 lines of source per second 
on an AMD K6-2 running at 300MHz.

I'd suggest try it and see. If fast speed is really essential, you
might try using C/C++ and yacc instead.

(*) see <> for details.

***** Phil Hunt ***** send email to phil at *****
Moore's Law: hardware speed doubles every 18 months
Gates' Law: software speed halves every 18 months 

More information about the Python-list mailing list