It is known that any fast CFG parsing algorithm can be turned into a fast boolean matrix multiplication algorithm.

So if CFG parsing was n^2, so is boolean matrix multiplication :)

See http://arxiv.org/abs/cs/0112018

One important note is that this holds for general grammars that can contain everything. If the grammar is restricted somehow, for example to lr(k) then the best complexity is linear (there are even parsers that manage both LR(n) in linear time and general parsing in cubic).

I'm confused by this argument. To show that

> if CFG parsing was n^2, so is boolean matrix multiplication

wouldn't you need to show that any boolean matrix multiplication can be turned into CFG parsing (and not the converse)?

Great question, I just learned something.

A boolean matrix multiplication problem can be turned into a CFG problem. Therefore, an algorithm that solves CFG problems can be turned into an algorithm that solves boolean matrix multiplication.

Sorry, yes, i deleted a line accidentally, but it turns out you can show both directions, and to prove a tight bound, you need to show they reduce to each other without changing the complexity class.