It is often said that memoization brings the complexity of recursive-descent parsersfrom exponential to polynomial. However, I had a hard time finding an example grammarthat triggers the exponential case.Because recursive descent parsers cannot (naturally) deal with left-recursion,the example should not contain left-recursive rules.BTW, I'm familiar with PEG and Packrat parsers, and I'm not looking for examplesin the that domain. To be more precise, can someone please give me a non-left-recursive context-free grammar that triggers exponential behaviour?
Example of context-free grammar that triggers exponential behaviour without memoization in RD parsers
time complexity;parsing;exp time algorithms
Here is a grammar that should meet your specification, though itgenerates the very simple language $a^+(b+c)$.  (A simpler grammar has been added below)$S \rightarrow ab \mid aBb \mid ac \mid aCc$$B \rightarrow a \mid aB \mid aBB$$C \rightarrow a \mid aC \mid aCC$  How was it built:I started from the grammar$\{S \rightarrow S S \mid a\}$ which is very ambiguous, so that trying allparses of a string $a^n$ takes exponential time.I put it in Greibach Normal Form, so as to remove any left recursion,giving$S \rightarrow a \mid aB$$B \rightarrow a \mid aB \mid aBB$  Then I introduced $C$ to duplicate the possibilities of derivation,with $b$ or $c$ as end marker to discover at the very end whether Ishould have been using $B$ or $C$ as non-terminal in my derivation,i.e,, whether the first rule to apply was $S \rightarrow aBb$ or $S\rightarrow aCc$. But if the choice of rule made at the very beginningwas wrong, the backtracking process will have first to try all parsingpossibilities for the string of $a$, which has exponential cost.Since the recursive descent has to try first one of the two rules,there will always be a string (requiring the other rule) that takesexponential time to parse, because of the useless backtracking with the wrong non-terminal.Memoisation brings this down to cubic time. Naive memoisation will make it $O(n^4)$, but a bit of currification can correct that to cubic time.A simpler solution (thought of later)All that matters in the above grammar is to force an early choice ofthe terminal marker $b$ or $c$, while having that choice checked only at the endof the parsing process.Hence the following grammar is enough to get the desired exponentialbehaviour. Actually it is a (renaming) homomorphic image of the firstgrammar above, and leads to exactly the same computation up to thatrenaming.$S \rightarrow ab \mid aXb \mid ac \mid aXc$$X \rightarrow a \mid aX \mid aXX$  The rules $S \rightarrow ab \mid ac$ are not actually necessary forour purpose, but that is minor. Removing them would change the language to $aa^+(b+c)$. Then, it is also possible to remove the initial $a$ in the rules $S \rightarrow aXb \mid aXc$ without introducing left recursion, thus getting back the initial language $a^+(b+c)$. But the grammar is no longer in Greibach normal form (which was not a requirement of the problem). This gives a solution with only 5 rules:$S \rightarrow Xb \mid Xc$$X \rightarrow a \mid aX \mid aXX$  