<p>Here is a grammar that should meet your specification, though it
generates the very simple language $a^+(b+c)$.  <em>(A simpler grammar has been added below)</em></p>

<p>$S \rightarrow ab \mid aBb \mid ac \mid aCc$<br>
$B \rightarrow a \mid aB \mid aBB$<br>
$C \rightarrow a \mid aC \mid aCC$  </p>

<p>How was it built:</p>

<p>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.</p>

<p>I put it in Greibach Normal Form, so as to remove any left recursion,
giving</p>

<p>$S \rightarrow a \mid aB$<br>
$B \rightarrow a \mid aB \mid aBB$  </p>

<p>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.</p>

<p>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.</p>

<p>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.</p>

<hr>

<p><strong>A simpler solution</strong> (thought of later)</p>

<p>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.</p>

<p>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.</p>

<p>$S \rightarrow ab \mid aXb \mid ac \mid aXc$<br>
$X \rightarrow a \mid aX \mid aXX$  </p>

<p>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:</p>

<p>$S \rightarrow Xb \mid Xc$<br>
$X \rightarrow a \mid aX \mid aXX$  </p>

CC BY-SA 3.0
2014-05-13T09:33:47.070Z
2014-05-14T08:51:43.457Z
2014-05-14T08:51:43.457Z
babou
<p>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.</p>

<p>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?</p>

<time-complexity><parsing><exp-time-algorithms>
Example of context-free grammar that triggers exponential behaviour without memoization in RD parsers
Wickoo
# Example of context-free grammar that triggers exponential behaviour without memoization in RD parsers

(Asked by: username_0 on 2014-05-11)

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?

**Tags:** time-complexity, parsing, exp-time-algorithms


---

## 1 answers

### Answer by username_1 on 2014-05-13. Score: 7 | Accepted answer

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$


---

