Re: Earley...

clark@quarry.zk3.dec.com (Chris Clark USG)
4 Jun 1997 22:52:54 -0400

          From comp.compilers
Related articles
Earley... darius@phidani.be (Darius Blasband) (1997-05-22)
Re: Earley... vannoord@let.rug.nl (1997-05-25)
Re: Earley... lijnzaad@ebi.ac.uk (Philip Lijnzaad) (1997-05-27)
Re: Earley... alan@ezlink.com (Alan L. Wendt) (1997-05-30)
Re: Earley... clark@quarry.zk3.dec.com (1997-06-04)
| List of all articles for this month |
From: clark@quarry.zk3.dec.com (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,
http://www.de.relator.research.ec.org/resources/tom


> 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.