1
$\begingroup$

I found this question What is the usage of CYK algorithm in the real world considering we have algorithms with a much better Time complexity? saying CYK Parsing algorithm can compute any Context Free Grammar in $O(n^3)$.

But this does not make sense because I cannot see how NonDeterministic Context Free grammar can be parsed in $O(n^3)$. Then, while reading Hopcroft and Ullman (2006) pages 304 I found:

In $O(n^3)$ time the algorithm constructs a table that tells whether w is in L $\in$ Note that when computing this running time the grammar itself is considered fixed and its size contributes only a constant factor to the running time which is measured in terms of the length of the string w whose membership in L is being tested.

So, the correct affirmation is: There is no way a NonDeterministic Context Free Grammar parsing tree can be built in $O(n^3)$ time, only its word membership can be determined in $O(n^3)$ time by the CYK algorithm. NonDeterministic Context-Free Grammars Parsing Trees can only be built in Exponential Time (worst case)?

Related:

  1. Chomsky Hierarchy and P vs NP
  2. What is the big-O (worst-case upper bound) for time and space requirement of the different Chomsky classes?
Improve this question
$\endgroup$

1 Answer 1

Reset to default
3
$\begingroup$

It depends what you mean by build a parse tree.

You can build a parse forest in $O(n^3)$ time and space. The forest represents all parse trees, even an infinite number of parse trees, because it is a graph, not a tree. From a parse forest, it is possible to produce a single parse tree in time linear to the size of the forest, and it is possible to iterate through all possible parses.

So if you either consider that "build a parse tree" means "find one of the possible parses" or if you consider that it means "build a datastructure which represents all possible parses", then you can certainly do that with a CYK grammar in $O(n^3)$.

If, on the other hand, you intend "build a parse tree" to mean "build all parse trees for a sentence", then it is not limited to exponential time; it is easy to write a grammar with an infinite number of possible parses for certain sentences.

Improve this answer
$\endgroup$
5
  • $\begingroup$ it is easy to write a grammar with an infinite number of possible parses for certain sentences, but this grammar is Context Free? $\endgroup$
    – user
    Commented Jul 7, 2019 at 4:05
  • 1
    $\begingroup$ @user: sure. $A\to A\mid a$ has an infinite number of derivations of $A\to^*a$. $\endgroup$
    – rici
    Commented Jul 7, 2019 at 4:08
  • $\begingroup$ If parsing (building the parsing tree) of a Deterministic Context-Free Grammar can be done in Deterministic Linear Time or Deterministic Polynomial Time where the n exponent = 1, i.e., n^1, with an LR(K) parser. Then, parsing NonDeterminisc Context Free Grammar can also be done with Deterministic Polynomial time with some other exponent of n other than 1? I know that parsing a NonDeterminisct Context-Free Grammar with Backtracking algorithm has exponential time. For example, consider some regular expression where the regex engine has to backtrack always. How can CKY be Polynomial? $\endgroup$
    – user
    Commented Jul 7, 2019 at 4:21
  • $\begingroup$ @user: because the CYK algorithm doesn't backtrack. It explores all alternatives in parallel, and it merges common derivation paths (in effect), leading to a polynomial time solution. $\endgroup$
    – rici
    Commented Jul 7, 2019 at 4:40
  • $\begingroup$ @user: also, regex engines never need to backtrack, if they are actually recognising regular languages (as opposed to the grimoire of irregular features which make up a modern regex libraries). Regular expressions can always be recognised online in linear time. Extracting captures is trickier (which is why many libraries backtracked) but it can be done. See Russ Cox's excellent RE2 library for a concrete example. $\endgroup$
    – rici
    Commented Jul 7, 2019 at 5:29

Your Answer

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

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