# What is the usage of CYK algorithm in the real world considering we have algorithms with a much better Time complexity?

So considering CYK is O(n^3) and since we can just use LR(k) algorithms for DCFG's which they can check if a string is in the language in O(n) then whats the usage of CYK?

is it being used anywhere?

If I'm not mistaken(correct me If I'm wrong) the benefit of CYK is that since we can convert any CFG to CNF form therefore i guess we can apply this to non deterministic CFG's and also Inherently ambiguous grammars which are CFG

but are these really benefits? i mean whats the usage of using membership algorithm for Inherently ambiguous CFG's or non deterministic CFG's? where would we use a Inherently ambiguous CFG or non deterministic CFG ?!

Isn't the main usage of membership for compilers? which they already use LR algorithms?

• Answered on quora: quora.com/What-is-CYK-algorithm-used-for-practically. – Yuval Filmus Apr 14 '18 at 19:14
• You assume that the algorithm has (to have) practical relevance. Why? – Raphael Apr 15 '18 at 8:20
• Inherently ambiguous grammars: Only Languages can be Inherently ambiguous, while their grammars are always nondeterministic. – user Jul 6 '19 at 22:22

## 1 Answer

Here is one benefit:

Some grammars aren't LR(k). Then it's useful to have CYK or some other form of GLR parsing. GLR parsing is used in some compilers, where the most natural way to express the grammar leads to a grammar that isn't LR(k), or where ambiguities are resolved in a later pass (not part of the parser).

• Hm, but would you ever really prefer CYK over early except for didactic reasons? Not sure which parsing algorithms can be parellelized how well, that's one thought I'm having. – Raphael Apr 15 '18 at 8:21
• "Then it's useful to have CYK or some other form of GLR parsing." I would say some other form of general CFG parsing. GLR is one particular family of algorithms, but CYK or Earley are general parsing algorithms that aren't in the GLR family. – orlp Apr 15 '18 at 11:38