Is there a context-free language that can be expressed with an unambiguous grammar but can't be expressed with a grammar that would result in linear-time backtracking recursive descent parsing?

The motivation for this question is the fact that backtracking recursive descent parsing has a bad reputation for worst-case exponential runtime. This is presented as the reason for using other, more complicated parsing algorithms like LL, LR, packrat etc.

However, as I've been trying to hunt down a practical example of worse-than-linear parsing time for backtracking recursive descent parser, I've seen no reasonable examples.

The examples I've seen are often a deliberately bad grammar for a simple language, and the same language can be recognised by some other grammar.

So, of course, some grammars result in worse than linear time backtracking recursive descent parsing, but is the same true for (unambiguous) languages?


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.