# 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. – Pål GD 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. – Brent 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