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

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