Re: Earley... (Chris Clark USG)
4 Jun 1997 22:52:54 -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: (Chris Clark USG)
Newsgroups: comp.compilers
Date: 4 Jun 1997 22:52:54 -0400
Organization: Digital Equipment Corporation - Marlboro, MA
References: 97-05-252 97-05-304
Keywords: parse

I looked up Tomita on the web found the parser I was mentioning.
From the text at,

> Task:
> Parse natural language sentences with given LR(0) grammars by an
> algorithm invented 1985 by Masaru Tomita (CMU)
> Description:
> The software constructs LR(0) parsing tables for arbitrary
> context free grammars, which you specify. It then processes
> any input you give it and displays the resulting parse forest
> and optionally the parse stack as well. The parse tables are
> also shown, if you requests it, since reference is made to
> them in the parse stack. One difference between this and
> Tomita's original algorithm is this algorithm has been
> modified into a dynamic programming algorithm, capable of
> handling all CFG's including cyclic grammars.

Although this is not *exactly* Earley's algorithm, the claims seem to
be approximately the same. Moreover, the use of an LR automaton
internally should remove much of the constant overhead.

-Chris Clark

Post a followup to this message

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