9 May 2006 00:51:34 -0400

Related articles |
---|

Running Earley's Parser in O(n^3) zingard@mcmaster.ca (Daniel Zingaro) (2006-05-09) |

Re: Running Earley's Parser in O(n^3) kym@ukato.freeshell.org (russell kym horsell) (2006-05-11) |

From: | Daniel Zingaro <zingard@mcmaster.ca> |

Newsgroups: | comp.compilers |

Date: | 9 May 2006 00:51:34 -0400 |

Organization: | Compilers Central |

Keywords: | parse, question |

Posted-Date: | 09 May 2006 00:51:34 EDT |

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

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.