4
$\begingroup$

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?

$\endgroup$
7
$\begingroup$

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$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.