Difference between Earley and Chart Parsers

gschmidt2@ra.rockwell.com (Greg Schmidt)
1 Dec 2000 13:35:14 -0500

          From comp.compilers

Related articles
Difference between Earley and Chart Parsers gschmidt2@ra.rockwell.com (2000-12-01)
Re: Difference between Earley and Chart Parsers philip.fortomas@virgin.net (Philip Fortomas) (2000-12-18)
| List of all articles for this month |

From: gschmidt2@ra.rockwell.com (Greg Schmidt)
Newsgroups: comp.compilers
Date: 1 Dec 2000 13:35:14 -0500
Organization: Compilers Central
Keywords: parse, question
Posted-Date: 01 Dec 2000 13:35:13 EST


I've recently been experimenting with Early's parsing algorithm. I'm
also aware of chart parsers which appear to be similiar but I have not
researched them. As I understand it, both Early and Chart parsing
both have O(G*n^3) complexity (for ambiguous grammars) and O(G*n^2)
for non-ambiguous grammars so I'm wondering what, if anything, is the
significant difference between the two. Note: G is a constant that
depends upon the particular grammar.

My guess is that at some level they are equivalent. Perhaps the main
difference between the two is the constant factor G. Early builds
state sets top down using a closure operation (among others) whereas
the chart parser appears to be more bottom up (i.e. here's a token,
now let's see what production it advances). So intuitively, it seems
that the chart parser might be more efficient since it is working
bottom up and is not performing the closure operation. Or maybe there
really is no free lunch and there are some grammars for which Early is
better and others where the chart parser is better (in terms of the
constant factor G).

Does anyone have any insights on this?

-- Greg
e-mail: gschmidt2@ra.rockwell.com

Post a followup to this message

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