# Fast context-free grammar parsing requires fast Boolean matrix multiplication Lillian LeeJournal of the ACM 49(1):1--15, 2002

In 1975, Valiant showed that Boolean matrix multiplication can be used for parsing context-free grammars (CFGs), yielding the asympotically fastest (although not practical) CFG parsing algorithm known. We prove a dual result: any CFG parser with time complexity $O\left($gn(3 - ε)), where g$is the size of the grammar and n is the length of the input string, can be efficiently converted into an algorithm to multiply$m-by- m$Boolean matrices in timeO\left(m\left(3 - \epsilon /3\right)\right). Given that practical, substantially sub-cubic Boolean matrix multiplication algorithms have been quite difficult to find, we thus explain why there has been little progress in developing practical, substantially sub-cubic general CFG parsers. In proving this result, we also develop a formalization of the notion of parsing.$

@article{Lee:02a, author = {Lillian Lee}, title = {Fast context-free grammar parsing requires fast {Boolean} matrix multiplication}, year = {2002}, pages = {1--15}, journal = {Journal of the ACM}, volume = {49}, number = {1} }

This material is based upon work supported in part by the National Science Foundation under Grant No. IRI-9350192, an NSF Graduate Fellowship, and an AT&T GRPW/ALFP grant. Any opinions, findings, and conclusions or recommendations expressed above are those of the author and do not necessarily reflect the views of the National Science Foundation.