It is easy to show that there exists a grammar that can be parsed by a recursive-descent parser with backtracking but is not an $\text{LL}(k)$ grammar (consider any grammar with a production featuring two alternatives starting with $k$ occurrences of the same terminal).

My question is the following: Is there an identifiable strict superset of $\bigcup_{k \in \mathbb{N}} \text{LL}(k)$ grammars that can be parsed by a backtracking recursive-descent parser, regardless of complexity?

If yes, is the maximal superset also identifiable?

  • $\begingroup$ By any chance, do you mean LL(*)? $\endgroup$ – user114966 Aug 7 '20 at 19:35
  • $\begingroup$ Any deterministic grammar can be parsed by an LL parser with backtracking, although it could take exponential time if you don't do a clever implementation. That's not a maximal superset, though $\endgroup$ – rici Aug 7 '20 at 21:43
  • $\begingroup$ @Dmitry having a peek into the paper $\text{LL}(\star)$ would indeed qualify for the strict superset, thank you. $\endgroup$ – user35443 Aug 8 '20 at 10:18
  • $\begingroup$ @rici Would you be able to point me to an example grammar that is not deterministic but parsable with a backtracking parser? $\endgroup$ – user35443 Aug 8 '20 at 10:21

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.