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

Improve this question
$\endgroup$
4
  • 1
    $\begingroup$ No, if your parser tries every branch, we would not call the parser non-deterministic. $\endgroup$
    – John Kemeny
    Commented Jul 22, 2013 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
    Commented Jul 23, 2013 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
    Commented Jul 23, 2013 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
    Commented Jul 29, 2013 at 7:45

1 Answer 1

Reset to default
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.

Improve this answer
$\endgroup$
2
  • 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$
    – Joey Eremondi
    Commented Jul 22, 2013 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
    Commented Jul 23, 2013 at 22:50

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.