# 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$