# The class of grammars recognizable by backtracking recursive-descent parsers

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?

• By any chance, do you mean LL(*)? – user114966 Aug 7 '20 at 19:35
• 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 – rici Aug 7 '20 at 21:43
• @Dmitry having a peek into the paper $\text{LL}(\star)$ would indeed qualify for the strict superset, thank you. – user35443 Aug 8 '20 at 10:18
• @rici Would you be able to point me to an example grammar that is not deterministic but parsable with a backtracking parser? – user35443 Aug 8 '20 at 10:21