Fast context-free grammar parsing requires fast Boolean matrix multiplication
Lillian Lee
Journal 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($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\; time$ O(m(3\; -\; \epsilon /3))$.\; 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.$

• paper (pdf)
• talk slides
• ACM site
• arxiv site

@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.