4
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ 1. Is what method better than CYK parsing? 2. I think you might be making a faulty assumption: just because the language $L$ is a deterministic context-free language and $G$ is a grammar for $L$ doesn't mean that $G$ is unambiguous and corresponds to a deterministic PDA; it just means that there exists some other grammar $G'$ with those properties. 3. See also en.wikipedia.org/wiki/GLR_parser#Advantages and en.wikipedia.org/wiki/Deterministic_context-free_language, if you want an algorithm that's efficient for deterministic CFLs. $\endgroup$ – D.W. Oct 13 '16 at 5:36
  • $\begingroup$ I don't think your description works for NPDA. You can not properly implement non-deterministic automata. Well, short of exploring the whole reachable state space, which is rarely efficient. Hence, other parsing algorithms shine. $\endgroup$ – Raphael Oct 13 '16 at 8:08
  • 2
    $\begingroup$ Then you should state right at the start that you only inspect DPDAs. Anyway, my point is that your language is imprecise. How do you implement step 2? It can be done in constant time! Which "set of states" in step 3? (This is what made me think your algorithm was supposed to work for NPDAs.) $\endgroup$ – Raphael Oct 13 '16 at 13:42
  • 2
    $\begingroup$ No need for hash tables; just encode alphabet as numbers $0..k$ and states as numbers $0..q$ and use a plain old matrix. That works with or without non-determinism. $\endgroup$ – Raphael Oct 13 '16 at 15:02
  • 1
    $\begingroup$ @aste123 What you're missing is that CFG parsing is sub-$O(n^3)$ even for nondeterministic grammars, and that you can have a single method that is linear on deterministic grammars and still sub-$O(n^3)$ on all other CFGs. $\endgroup$ – reinierpost Oct 14 '16 at 11:33
5
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ This answer doesn't state the complexity of Valiant's algorithm when applied to deterministic grammars. It isn't $O(n)$, but a variant can be designed that is. $\endgroup$ – reinierpost Oct 14 '16 at 11:37
  • $\begingroup$ @reinierpost Valiant's algorithm uses matrix multiplication, so I doubt that it can exploit determinacy. Perhaps a different algorithm does. $\endgroup$ – Yuval Filmus Oct 14 '16 at 12:13

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.