Re: Earley...

Darius Blasband (darius@phidani.be) wrote:


> I'd be interested in any experience or technical information about
> Earley's parsing algorithm. More specifically:


> - How does one explain the huge difference between the theoretical
> complexity (often linear or quadratic, cubic worst case) and
> the real performance (quite bad, if I recall)


Earley is linear when parsing grammars that other linear parsers can
handle. It suffers a large constant factor (maybe 10 - 100) because
it builds state sets on the fly rather than precompiling them.


Yacc can enumerate all possible state sets for LALR grammars
so the generated parser only has to deal with state set indeces.


I wrote an instruction recognizer using an Earley parser because
I didn't want the recognizer complaining that the machine description
wasn't LALR. Writing machine descriptions is hard enough without
having to fight the grammar. The performance was acceptable, and
in a modern compiler with all the performance hits of global
flow analysis, graph coloring register allocators, and instruction
schedulers, probably no one would notice if you scrapped Bison and
used an Earley parser.


Alan Wendt
--

Return to the comp.compilers page.
Search the comp.compilers archives again.