|Parsing Algorithm for General CFGs email@example.com (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 firstname.lastname@example.org (Chris F Clark) (1998-09-22)|
|From:||corbett@lupa.Eng.Sun.COM (Robert Corbett)|
|Date:||19 Sep 1998 21:19:31 -0400|
|Organization:||Sun Microsystems Computer Corporation|
Yuen-Chang Sun <email@example.com> 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.
Return to the
Search the comp.compilers archives again.