# 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? – Yuval Filmus Nov 5 '14 at 17:17
• @Yuval, I think it should parse it, so I must be missing something. – meribold Nov 5 '14 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 '14 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. – meribold Nov 6 '14 at 14:32
• Where did you get that tree. I do not get much from that ABNF parser generator. The tree you give does not make much sense. But the string aaaaaa should parse and does not. But aaaa does parse. You are apparently right about powers of 2. The thing must be bugged. it parses only aa with S = "aa" / "a" [S] "a". Can you trace what the parser does? – babou Nov 6 '14 at 14:35

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. – meribold Nov 6 '14 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' – meribold Nov 6 '14 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. – meribold Nov 6 '14 at 15:30
• I do not see the point of exploring recursive descent, backtracking parser. – babou Nov 6 '14 at 15:30
• you are right about S = "a" S "a" / "aa" ... I tested too fast, and clicked on generate instead of parse. – babou Nov 6 '14 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[0]  = l[0]     w = aaaaaa    l = aSa
|          -- S->aSa works                                                                         | |     | |
6. tree:   The parser matches a after a:                                                       Result: w[6]  = l[6]     w = aaaaaa    l = aaaaaaSaaaaaa
7. tree:   The parser tries S->aSa again but there is no match!                                Result: w[7] != l[7]     w = aaaaaa    l = aaaaaaaSaaaaaaa
8. tree:   The parser tries S->aa but there is still no match!                                 Result: w[7] != l[7]     w = aaaaaa    l = aaaaaaaaaaaaaa
9. tree:   Backtracking after the last symbol that matched => Backtracking at l[7]             Result: w[7] != l[7]     w = aaaaaa    l = aaaaaaaaaaaa
10. tree:   Backtracking after the last symbol that matched => Backtracking at l[7]             Result: w[7] != l[7]     w = aaaaaa    l = aaaaaaaaaa
11. tree:   Backtracking after the last symbol that matched => Backtracking at l[7]             Result: w[7] != l[7]     w = aaaaaa    l = aaaaaaaa
12. tree:   Backtracking after the last symbol that matched => Backtracking at l[7]             Result: w[7] != l[7]     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[7].

• Finally got time to edit it! ;) – Sebbas Feb 20 '16 at 17:35