Re: Parsing Algorithm for General CFGs

Chris F Clark <>
22 Sep 1998 01:12:26 -0400

          From comp.compilers

Related articles
Parsing Algorithm for General CFGs (Yuen-Chang Sun) (1998-09-18)
Re: Parsing Algorithm for General CFGs corbett@lupa.Eng.Sun.COM (1998-09-19)
Re: Parsing Algorithm for General CFGs (Chris F Clark) (1998-09-22)
| List of all articles for this month |

From: Chris F Clark <>
Newsgroups: comp.compilers,comp.theory,comp.programming
Date: 22 Sep 1998 01:12:26 -0400
Organization: The World Public Access UNIX, Brookline, MA
Distribution: inet
References: 98-09-076
Keywords: parse, theory

Yuen-Chang Sun <> 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

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


Chris Clark Internet :
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 :

Post a followup to this message

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