Parsing Algorithm for General CFGs

Yuen-Chang Sun <ycsun@ms7.hinet.net>
18 Sep 1998 23:13:26 -0400

          From comp.compilers
Related articles
Parsing Algorithm for General CFGs ycsun@ms7.hinet.net (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 cfc@world.std.com (Chris F Clark) (1998-09-22)
| List of all articles for this month |
From: Yuen-Chang Sun <ycsun@ms7.hinet.net>
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
course.)
[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.