SPARK / Earley Parser question

[phil hunt]

On Wed, 26 Apr 2000 23:26:21 GMT, Stefan Franke <spamfranke at bigfoot.de> 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 <http://www.comuno.com/linux/parrot/intro.html> for details.

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