Parsing Algorithm for General CFGs

Yuen-Chang Sun <>
18 Sep 1998 23:13: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: Yuen-Chang Sun <>
Newsgroups: comp.compilers,comp.theory,comp.programming
Date: 18 Sep 1998 23:13:26 -0400
Organization: DCI HiNet
Distribution: inet
Keywords: parse, theory

Could anybody please tell me the most efficient parsing algorithm you
know for general context- free grammars?

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]


Post a followup to this message

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