Re: Parsing Algorithm for General CFGs

Yuen-Chang Sun <ycsun@ms7.hinet.net> writes:


> Actually what I really want to know is the known computational
> complexity of parsing general CFGs. I know there are O(n^3)
> algorithms.
> [General CFGs? I think it's n^3 unless you significantly restrict the
> grammars it can handle. -John]


I have several papers by Thomas Scho\:bel-Theuer which if I understand
correctly (and I may not!) imply the existence of an n^2 algorithm.
Unfortunately, the main one is in German and my German is too rusty
(and was probably never technical enough) for me to get through it at
anything faster than about a page per day. Moreover, some of the
other papers were still drafts in the copies I recieved, so the author
may have changed his views (and I apologize if I have spread incorrect
information).


However, prior to this breakthrough, I believe n^3 was the best known
bounds for general CFG's.


-Chris


*****************************************************************************
Chris Clark Internet : cfc@world.std.com
Compiler Resources, Inc. CompuServe : 74252,1375
3 Proctor Street voice : (508) 435-5016
Hopkinton, MA 01748 USA fax : (508) 435-4847 (24 hours)
------------------------------------------------------------------------------
Web Site in Progress: Web Site : http://world.std.com/~compres
--

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