# If a parser can parse a non-deterministic grammar, is the parser non-deterministic?

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

• No, if your parser tries every branch, we would not call the parser non-deterministic. Jul 22 '13 at 18:32
• Note that polynomial time and space is nothing special (for context-free grammars); do you know the CYK algorithm?
– Raphael
Jul 23 '13 at 5:32
• @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. Jul 23 '13 at 22:47
• @Brent In that case, you may be interested in Earley parsing as well ast this and this question for some perspective.
– Raphael
Jul 29 '13 at 7:45

## 1 Answer

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.

• 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. Jul 22 '13 at 23:41
• @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. Jul 23 '13 at 22:50