# Recursive descent parser with backtracking for the grammar $S \rightarrow aSa\ |\ aa$

Can someone enlighten me why a recursive descent parser with backtracking that tries the productions $S \rightarrow aSa$ and $S \rightarrow aa$ (in that order) does not recognize the language formed by the grammar $S \rightarrow aSa\ |\ aa$.

It appears to only parse words from the language $\{a^{2^n}\ |\ n \ge 1 \}$.

I generated such a parser using this ABNF Parser Generator with the production rule S = "a" S "a" / "aa" and the parser does not recognize the word aaaaaa, for example.

I would expect it to use the production $S \rightarrow aSa$ until the concatenation of the parse tree's terminal nodes from the left starts with 7 a's, and then go up the parse tree choosing the production $S \rightarrow aa$ instead until the tree looks like this:

   S
/ | \
a  S  a
/ | \
a  S  a
/ \
a   a

• Why do you think it can't parse this word? Nov 5, 2014 at 17:17
• @Yuval, I think it should parse it, so I must be missing something. Nov 5, 2014 at 20:09
• Ah, now the question makes more sense; thanks for the edit! If what you write is true (I did not check) the generator seems to have a bug. (Or it is not specified for your grammar; I think this is unlikely since the grammar is elementary and unambiguous.
– Raphael
Nov 5, 2014 at 23:25
• @Raphael, I edited the question again (hopefully without changing the meaning). I'm actually tasked to explain why such a parser doesn't recognize the word aaaaaa. Nov 6, 2014 at 14:32
• @babou, That's just the parse tree I'd expect to be constructed for aaaaaa. Nov 6, 2014 at 14:44

It's actually a property of the "singleton match strategy" usual in naive implementations of recursive descent parsers with backtracking.

The trick here is to realise that many backtracking parsers use what we call a singleton match strategy, in which as soon as the parse function for a rule finds a match, it returns. In general, parse functions need to return a set of putative matches. Just try working it through, and you'll see that a singelton match parser misses some of the possible derivations.

Also, this image available in this answer on StackOverflow will help to visualize what's happening in the case you exemplified: This is not much of an answer, but the parse trees do not fit the normal comments.

Your grammar $S \rightarrow aSa\ |\ aa$ should parse the string $aaaaaa$.

But the parse tree has the following form:

      S
/|\
/ S \
/ /|\ \
/ / S \ \
/ / / \ \ \
a a a   a a a


or if you prefer this presentation, with the terminals on different lines

     S
/ | \
a  S  a
/ | \
a  S  a
/ \
a   a


I checked that the ABNF parser generator does not seem to work, but I do not know how to trace what it does.

It indeed seems to recongnize the set $\{a^{2^n}\ |\ n \ge 1 \}$ wich is not what the grammar defines.

It is a bit surprising to have such an elaborate site around a buggy parser, which furthermore uses a totally uninteresting parsing technique.

After a further look at it:

I think I found one source of the problem. The square brackets mean optional.

So your grammar should be written either S = "a" S "a" / "aa" or S = "a" [S] "a". Then it seems to work correctly.

But the system is apparently lost when having twice the same rule in different forms. I am not sure why.

I did not find a page explaining these syntactic issues for specifying the grammar.

I still consider that buggy.

• Ouch. Yeah. I don't know what I was thinking when I wrote that parse tree. I'll edit my question and paste yours. Nov 6, 2014 at 15:07
• I did find another recursive descent, backtracking parser generator with an online demo here and it shows the same behaviour with this rule: S ::= 'a'<S>'a' | 'a''a' Nov 6, 2014 at 15:18
• It still doesn't parse aaaaaa when using S = "a" S "a" / "aa", but you seem to be right about the brackets. Nov 6, 2014 at 15:30
• I do not see the point of exploring recursive descent, backtracking parser. Nov 6, 2014 at 15:30
• you are right about S = "a" S "a" / "aa" ... I tested too fast, and clicked on generate instead of parse. Nov 6, 2014 at 15:35

I wrote a very simple implementation of this parser in C++ (see below), and it has the same issue. This seems to be because whenever the function s1() for the production $S \rightarrow aSa$ returns true, s() will immediately return and never try s2() (the function implementing $S \rightarrow aa$) for that node of the parse tree.

Consider parsing the word aaaaaa again. At one point, the parse tree will look like this:

   S
/ | \
a  S  a
/ | \
a  S  a    <--
/ | \
a  S  a
/ \
a   a


Then, s() will return true for the S-node at the 3rd level and the production $S \rightarrow aa$ will never be considered here, but instead one level higher, resulting in:

   S
/ | \
a  S  a
/ \
a   a


I tend to consider this an issue with my implementation and not with backtracking recursive descent parsers in general, though.

#include <iostream>

char* next;
bool term(char token) {
if (*next != '\0')
return *next++ == token;
else
return false;
}

bool s();
bool s1() {
return term('a') && s() && term('a');
}
bool s2() {
return term('a') && term('a');
}
bool s() {
auto save = next;
return s1() or (next = save, s2());
}

int main(int argc, char* argv[]) {
next = "aaaaaa";
if (s() && *next == '\0') {
std::cout << "match";
}
else
std::cout << "no match";
}


## It is a feature not a bug

Have a close look at when & where backtracking occurs:

     1.           2.          3.          4.          5.          6.          7.          8.          9.          10.         11.         12.

S            S           S           S           S           S           S           S           S           S           S           S
/ | \        / | \       / | \       / | \       / | \       / | \       / | \       / | \       / | \       / | \       / | \       / | \
a  S  a      a  S  a     a  S  a     a  S  a     a  S  a     a  S  a     a  S  a     a  S  a     a  S  a     a  S  a     a  S  a     a  S  a
/ | \       / | \       / | \       / | \       / | \       / | \       / | \       / | \       / | \       / | \       /   \
a  S  a     a  S  a     a  S  a     a  S  a     a  S  a     a  S  a     a  S  a     a  S  a     a  S  a     a  S  a     a     a
/ | \       / | \       / | \       / | \       / | \       / | \       / | \       / | \       / | \
a  S  a     a  S  a     a  S  a     a  S  a     a  S  a     a  S  a     a  S  a     a  S  a     a  S  a
/ | \       / | \       / | \       / | \       / | \       / | \       / | \       /   \
a  S  a     a  S  a     a  S  a     a  S  a     a  S  a     a  S  a     a  S  a     a     a
/ | \       / | \       / | \       / | \       / | \       /   \
a  S  a     a  S  a     a  S  a     a  S  a     a  S  a     a     a
/ | \       / | \       / | \       /   \
a  S  a     a  S  a     a  S  a     a     a
/ | \       /   \
a  S  a     a     a

w[] = 'aaaaaa'  //input
l[] = ''        //current tree leafs

1. tree:   The parser starts with the start symbol S and tries first alternative S->aSa:       Result: w  = l     w = aaaaaa    l = aSa
|          -- S->aSa works                                                                         | |     | |
6. tree:   The parser matches a after a:                                                       Result: w  = l     w = aaaaaa    l = aaaaaaSaaaaaa
7. tree:   The parser tries S->aSa again but there is no match!                                Result: w != l     w = aaaaaa    l = aaaaaaaSaaaaaaa
8. tree:   The parser tries S->aa but there is still no match!                                 Result: w != l     w = aaaaaa    l = aaaaaaaaaaaaaa
9. tree:   Backtracking after the last symbol that matched => Backtracking at l             Result: w != l     w = aaaaaa    l = aaaaaaaaaaaa
10. tree:   Backtracking after the last symbol that matched => Backtracking at l             Result: w != l     w = aaaaaa    l = aaaaaaaaaa
11. tree:   Backtracking after the last symbol that matched => Backtracking at l             Result: w != l     w = aaaaaa    l = aaaaaaaa
12. tree:   Backtracking after the last symbol that matched => Backtracking at l             Result: w != l     w = aaaaaa    l = aaaa


The crucial point here is that the parser backtracks after the position, where the last matching character was found. That's why it "jumps" from tree 11 with l = aaaaaaaa to the 12th tree with l = aaaa by using S -> aa at l.

• Finally got time to edit it! ;) Feb 20, 2016 at 17:35