Example of context-free grammar that triggers exponential behaviour without memoization in RD parsers It is often said that memoization brings the complexity of recursive-descent parsers
from exponential to polynomial. However, I had a hard time finding an example grammar
that 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 examples
in the that domain. To be more precise, can someone please give me a non-left-recursive 
context-free grammar that triggers exponential behaviour?
Here is a grammar that should meet your specification, though it
generates 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 all
parses 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 I
should 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 beginning
was wrong, the backtracking process will have first to try all parsing
possibilities 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 takes
exponential 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 of
the terminal marker $b$ or $c$, while having that choice checked only at the end
of the parsing process.

Hence the following grammar is enough to get the desired exponential
behaviour. Actually it is a (renaming) homomorphic image of the first
grammar above, and leads to exactly the same computation up to that
renaming.

$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 for
our 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$