2
$\begingroup$

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?

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

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

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Raphael Apr 15 '18 at 8:21
  • $\begingroup$ "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. $\endgroup$ – orlp Apr 15 '18 at 11:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.