2
$\begingroup$

I've written a recursive-descent parser generator, and I'm trying to classify it (call me a cowboy coder if you must). According to wikipedia, S → 0S0 | 1S1 | ε, which checks for an even-length palindrome, is a non-deterministic grammar. My parser generator can handle this grammar. Does that mean my parser is non-deterministic?

To be honest, I'm not even sure that it's proper to try to classify it like this. It doesn't really match the description of a pushdown automata, since it passes data up and down through the stack (parameters, passed by reference, which may be modified). If anyone would be interested in taking a closer look at it, I'd be most grateful. It handles left recursion and ambiguous grammars in (I believe) polynomial time and space. https://github.com/coder0xff/parlex

$\endgroup$
  • 1
    $\begingroup$ No, if your parser tries every branch, we would not call the parser non-deterministic. $\endgroup$ – Pål GD Jul 22 '13 at 18:32
  • 1
    $\begingroup$ Note that polynomial time and space is nothing special (for context-free grammars); do you know the CYK algorithm? $\endgroup$ – Raphael Jul 23 '13 at 5:32
  • $\begingroup$ @Raphael, I've read the CYK algorithm page on wikipedia so have a general understanding. In contrast, the algorithm I've written is top down, and doesn't require that the grammar be in Chomsky normal form. $\endgroup$ – Brent Jul 23 '13 at 22:47
  • $\begingroup$ @Brent In that case, you may be interested in Earley parsing as well ast this and this question for some perspective. $\endgroup$ – Raphael Jul 29 '13 at 7:45
2
$\begingroup$

No, it doesn't mean that. A non-deterministic algorithm is one that uses non-determinism. You're not using non-determinism; your algorithm is completely deterministic.

Here's what's tripped you up. You can recognize a non-deterministic grammar using a deterministic algorithm. Similarly, you can recognize whether a word is accepted by a non-deterministic finite automaton (NFA) using a deterministic algorithm (e.g., simply convert the NFA to a DFA, then check whether the DFA accepts the word). So, no, just because the grammar is non-deterministic does not mean that we should call your parsing algorithm non-deterministic.

$\endgroup$
  • 4
    $\begingroup$ The parser would need to be nondeterministic IF it were to run on a pushdown. That's what makes the grammar non-deterministic. However, once you go to Turing Machines the nondeterminism doesn't give you any extra power. $\endgroup$ – jmite Jul 22 '13 at 23:41
  • 1
    $\begingroup$ @jmite, thanks for clarification. As I wondered in my original question, it doesn't make sense to classify my parser this way, because it isn't a pushdown automata at all. $\endgroup$ – Brent Jul 23 '13 at 22:50

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.