Running Earley's Parser in O(n^3)

Hello,


I'm looking for some insight into one aspect of Earley's 1970 article
dealing with his famous context-free parsing algorithm:


An efficient context-free parsing algorithm
Jay Earley
February 1970
Communications of the ACM, Volume 13 Issue 2




In section 4, Earley gives some tips for how to implement the
algorithm. In particular, I am wondering about points (3) and (4).
The algorithm can be implemented without keeping these lists, and I
can see that they reduce the time necessary to scan through state
sets, whether it be for the purpose of looking for an already existing
item, or looking for items that can be created by the completer.


Are these extra lists necessary, though, to preserve the O(n^3)
running time of the algorithm? If they are left out, then every time
you wanted to add a new item, you could linearly search the current
state set to ensure it did not exist; and when running a completer
step after parsing grammar rule N, you could scan through the fth
state set, looking for all productions where the "dot is before the
nonterminal N".


I also don't fully understand the time analysis in section 5, and why
exactly it is O(n^3), so any insight into this is also most appreciated.


Thanks.
Dan

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