SPARK / Earley Parser question
philh at vision25.demon.co.uk
Wed Apr 26 20:03:03 EDT 2000
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
>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
>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
More information about the Python-list