Re: Parsing Algorithm for General CFGs

corbett@lupa.Eng.Sun.COM (Robert Corbett)
19 Sep 1998 21:19:31 -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: corbett@lupa.Eng.Sun.COM (Robert Corbett)
Newsgroups: comp.compilers,comp.theory,comp.programming
Date: 19 Sep 1998 21:19:31 -0400
Organization: Sun Microsystems Computer Corporation
Distribution: inet
References: 98-09-076
Keywords: parse, theory

Yuen-Chang Sun <> wrote:
>Could anybody please tell me the most efficient parsing algorithm you
>know for general context- free grammars?

Check out the paper by Graham, Harrison, and Ruzzo in TOPLAS 2:3.

>Actually what I really want to know is the known computational
>complexity of parsing general CFGs. I know there are O(n^3)
>algorithms. Is there a O(n^2) or even better algorithm? And is there
>a lower bound? (I mean an absolute lower bound higher than O(n), of
>[General CFGs? I think it's n^3 unless you significantly restrict the
>grammars it can handle. -John]

Worst-case general context-free parsing has been shown to be at least
as fast as computing transitive closures. Computing transitive
closures has been shown to be as fast as matrix multiplication. The
asymtotically best algorithm for matrix multiplication I have seen is

There is a "hardest" context-free grammar. Parsing for any other
context-free grammar can be done in time that is at most a constant
multiple of the time required for the hardest context-free grammar.

Bob Corbett

Post a followup to this message

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