3
$\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?

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

1 Answer 1

Reset to default
5
$\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).

Improve this answer
$\endgroup$
2
  • $\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, 2018 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, 2018 at 11:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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