Re: Earley...

"Alan L. Wendt" <>
30 May 1997 23:15:09 -0400

          From comp.compilers

Related articles
Earley... (Darius Blasband) (1997-05-22)
Re: Earley... (1997-05-25)
Re: Earley... (Philip Lijnzaad) (1997-05-27)
Re: Earley... (Alan L. Wendt) (1997-05-30)
Re: Earley... (1997-06-04)
| List of all articles for this month |

From: "Alan L. Wendt" <>
Newsgroups: comp.compilers
Date: 30 May 1997 23:15:09 -0400
Organization: EZLink Internet Access Fort Collins Colorado
References: 97-05-252 97-05-292
Keywords: parse

Darius Blasband ( 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

Post a followup to this message

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