Difference between Earley and Chart Parsers

Hello,


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

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