|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:||Yuen-Chang Sun <email@example.com>|
|Date:||18 Sep 1998 23:13:26 -0400|
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]
Return to the
Search the comp.compilers archives again.