Parsing CFLs (simulating PDA vs CYK algorithm)

Question

We can simulate the PDA and parse the language with the following operations (vaguely):

1. Read the input symbol and top of stack - $O(1)$
2. Check all the transition rules (must check all for non-determinism) - $O(|Transition rules|)$
3. Update the stack and the set of states - $O(1)$

Due to non-determinism, the problem size increases and so does the complexity.

However, for deterministic context free languages, the complexity of this algorithm seems to be $O(n|Transition rules|)$ which is linear.

The complexity of CYK algorithm is $O(n^3|G|)$. From various sources it seems that the complexity of CYK algorithm is polynomial for deterministic languages. http://people.csail.mit.edu/madry/docs/linear.pdf

$|Transition rules|$ has a maximum value of around $|G|$ I think.

So, is this method really better than the CYK algorithm for deterministic CFLs or am I making a mistake in my analysis? If so, then where?

I'm assuming that $|G|$ = Number of production rules in grammar.

Answer 1

Wikipedia mentions that the class of deterministic context-free languages can be parsed in linear time, using an LR parser. In contrast, the fastest algorithm for parsing general context-free languages, Valiant's modification of the CYK algorithm, runs in time $O(n^\omega)$ (where $\omega$ is the matrix multiplication constant), and there is evidence due to Lee that any practical implementation of Valiant's algorithm will run in time proportional to $n^{2.43}$ at best (substitute $\epsilon = 3-2.81$ in Lee's paper; here $2.81$ is the exponent of Strassen's algorithm), and in time proportional to $n^3$ for most values of $n$ occurring in practice.

Context-free grammars used in practice tend to be deterministic, precisely because DCFLs can be parsed faster than CFLs. Indeed, even more restricted variants are commonly used (LALR languages) for reasons of efficiency.