Re: Parsing Algorithm for General CFGs

Yuen-Chang Sun <ycsun@ms7.hinet.net> 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
>course.)
>[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
O(n^2.48).


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.


Sincerely,
Bob Corbett
--

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