SPARK / Earley Parser question

[John Aycock]

Stefan Franke <spamfranke at bigfoot.de> wrote:
> I'm designing a grammar with John Aycock's SPARK toolkit. 

An excellent choice ;-) ;-)

> Are there some rules of thumbs which kind of rules should be avoided
> to retain linear complexity? 

The exact answer is in Earley's 1970 CACM paper.  As a rough guide, however,
an Earley parser has a fair bit in common with an LR parser, so LR grammars
with little in the way of lookahead required (i.e. things you might feed
to yacc or bison) will likely result in the best performance.  Lots of
ambiguity won't help matters either.  If blazing speed is a big issue
for your project, however, you probably don't want to be using SPARK; that's
not what it's designed for.

> In particular, I wonder if using empty right-hand sides for rules has
> any disadvantages.

No more so than for an LR parser.

I've also heard from people who've made a parser class in SPARK, then
subclassed it, rewriting selected rules in a less maintainable but
faster-to-parse fashion.  I don't have any personal experience doing
that, though.

John