why recursive decent parser can not parse the aaaaaa EX(4.4.5) Ullman ravisethi

Question

The grammar S -> a S a | a a generates all even-length strings of a's. We can devise a recursive-descent parser with backtrack for this grammar. If we choose to expand by production S -> aa first, then we shall only recognize the string aa. Thus, any reasonable recursive-descent parser will try S -> aSa first.

Show that this recursive-descent parser recognizes inputs aa, aaaa, and aaaaaaaa, but not aaaaaa.

Answer 1

According to me, the first condition for Recursive Decent Parser is that given grammar should not be Left Recursive and Non-deterministic. but here in question given grammar is non-deterministic so we need to convert that using left factoring and we'll get S->aS', S'->Sa|a and this will work I guess.

Answer 2

I'll paraphrase myself from this other answer.

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

Quoting this answer by Dr Adrian Johnstone:

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, the images available in this answer will help you visualize what's happening in the case you exemplified.

Answer 3

The parser will try to invoke match(a);S();match(a); at first rather than match(a);match(a); as described in the problem. And note that as you try to recursively invokeS() inside the block match(a);S();match(a);, you have only invoked match(a) once, the 'a' symbol in the end is not consumed.