Dragon book 4.4.5 exercise?

S → aSa | aa
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, try S → aSa first.

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


The devise shall be:

aaaaaa → aSa

aaaaa→ aaSaa

aaaa→ aaaSaaa

... until devise as aSa fail when

aa→ aaaaSaaaa

Try S→aa right now, the most inner devise be match, but the 2nd devise is unmatch(extra aaaa after S→aa)

For 2nd devise, turn to try S→aa production, It match but unmatch on 3th again

Walk along the trackback, eventually back to

aaSaa

When try S→aa at this level, the routine finish as a successe match.

Then,why the book ask that aaaaaa cannot be recognize?

• Yes, I've always thought the book is in error in this. Aug 22 '21 at 14:56
• @vonbrand: See my answer for a very simple program which demonstrates the correctness of the Dragon Book (for this exercise). (I think this example was known before the Dragon Book was written, and I've also seen it mentioned in descriptions of PEG parsing.)
– rici
Sep 16 '21 at 2:28

When you look at the parser's process, you see the entire text to be parsed, and naturally make judgements based on that knowledge. But that's not the way the parser works. So your strategy makes it easy for you to parse utterances, but not easy for you to understand the parser.

Remember that the question is about a recursive descent parser with backtracking. In a RD parser, each non-terminal has a parsing procedure; that procedure which attempts each possible production for that non-terminal in order. If a production matches, the procedure returns success. Otherwise, it resets the input cursor and tries the next production. If no production succeeds, it returns failure, and its caller will perform the next fallback.

A good way to actually understand a parser (in my opinion) is to write one in some concrete programming language. Or, if you are trying to educate a class, to encourage your students to do that. In this simple case, you should be able to write the parser in a few minutes. (Instrumenting it so that you can see what's going on takes only a little bit longer, but I'll leave that as an exercise.)

Here's a quick Python implementation which uses a seekable I/O object to allow fallback. (io.StringIO will work, for example.)

def match_a(inp):

def match_end(inp):

def match_S(inp):
fallback = inp.tell()
if match_a(inp) and match_S(inp) and match_a(inp): return True
inp.seek(fallback)
if match_a(inp) and match_a(inp): return True
return False

def match(inp):
return match_s(inp) and match_end(inp)


So we can give it a quick try and see if the Dragon Book's question is valid:

for n in range(17):
print(n, match(io.StringIO('a' * n)))

0 False
1 False
2 True
3 False
4 True
5 False
6 False
7 False
8 True
9 False
10 False
11 False
12 False
13 False
14 False
15 False
16 True


As advertised, it works with $$aa$$, $$aaaa$$ and $$aaaaaaaa$$, and fails on $$aaaaaa$$. Since I ran it a bit extra, there's actually a pretty good hint about what language is being recognised here. (Interestingly, it's not a context-free language.)

OK, what's going on? Again, you could get some more information by instrumenting the parser and examining the log of calls and returns. I'm going to try to explain the failure to parse $$aaaaaa$$ in narrative, but if you have any doubts, do try adding logging to the sample code. (The call and result log is at the end of the question, but it is quite long.)

First of all, note that at no point does the parser know anything about what's coming in the input stream, not even how long it is. It only knows about the next character. So the first thing it does (since it always tries $$S\to a S a$$ first) is to recursively call itself until that production fails, which will happen on the seventh recursion, not the third one. That's the point where the $$S$$ recogniser is called at the end of input. After the first alternative fails, that instance will then fall back to trying $$S\to a a$$, but since the parser has reached the end of input, that one will fail, too.

So then the seventh recursion reports failure back to the sixth recursion, which falls back to $$S\to a a$$. That also fails, because there is now only one available $$a$$. So now it falls back to the fifth recursion, which attempts its next alternative ($$S\to a a$$), which this time works because there are two $$a$$s at the current input.

That allows the fifth recursion to return success to its caller, the fourth recursion, which can then try to complete the $$S\to a S a$$ production by reading the last $$a$$. Alas, that doesn't work because after the $$S$$ succeeded, it left the input buffer at the end. So now the fourth recursion again resets the input cursor and tries its next alternative ($$S\to a a$$), which of course will work, so the fourth recursion can report success back to the third recursion.

Let's take stock here. The current call stack contains three recursions, each one waiting for $$S$$ to return, and a fourth recursion, which is about to report that it matched $$S\to a a$$ with the fourth and fifth input character. You and I can see that that's not the correct parse -- there aren't enough input characters left to satisfy the pending recursive calls -- but the parser is unaware of that.

The third recursion can read the last $$a$$, letting it satisfy $$S\to a S a$$ (covering the third through the sixth input character) so it returns success. And that's wrong, because the correct parse needs to match $$S\to a a$$ at the third position. But that correct parse will never be found, because once a matching production is found, the rest of the alternatives will never be tried.

Thus, when the third recursion returns to the second recursion, the second recursion finds that it can't complete $$S\to a S a$$. But it has no way of telling the third recursion to try some other alternatives. It doesn't even know that the third recursion had some untried alternatives. All it can do is fail itself, falling back to $$S\to a a$$. That will work, and the first recursion will then complete $$S\to a S a$$, but it will complete at position 4. So the top-level recogniser will reject the parse, since it didn't match the entire input.

In other words, the parse will only succeed when the parser happens to backtrack to the second production at precisely the right stack depth, so that the next time it backtracks is also at precisely the right stack depth, and so on until it backtracks at precisely the middle of the input (without ever being able to know that it's at the middle). That might be enough of a hint to construct an argument by induction. (But part b of that question is marked with a star, so the Dragon authors didn't feel it was trivial.)

Here's the call trace for the parse of $$aaaaaa$$; since I did this in Python, positions count from 0, not 1. (I guess I could have started with 1, but I didn't. It shouldn't be too hard to reproduce the log, though.)

Trying {S_ -> S $} at 0 Trying {S -> a S a} at 0 Trying 'a' at 0 Matched 'a' at 0 Trying {S -> a S a} at 1 Trying 'a' at 1 Matched 'a' at 1 Trying {S -> a S a} at 2 Trying 'a' at 2 Matched 'a' at 2 Trying {S -> a S a} at 3 Trying 'a' at 3 Matched 'a' at 3 Trying {S -> a S a} at 4 Trying 'a' at 4 Matched 'a' at 4 Trying {S -> a S a} at 5 Trying 'a' at 5 Matched 'a' at 5 Trying {S -> a S a} at 6 Trying 'a' at 6 Failed 'a' at 6 Failed {S -> a S a} at 6 Trying {S -> a a} at 6 Trying 'a' at 6 Failed 'a' at 6 Failed {S -> a a} at 6 Failed {S -> a S a} at 5 Trying {S -> a a} at 5 Trying 'a' at 5 Matched 'a' at 5 Trying 'a' at 6 Failed 'a' at 6 Failed {S -> a a} at 5 Failed {S -> a S a} at 4 Trying {S -> a a} at 4 Trying 'a' at 4 Matched 'a' at 4 Trying 'a' at 5 Matched 'a' at 5 Matched {S -> a a} at 4 Trying 'a' at 6 Failed 'a' at 6 Failed {S -> a S a} at 3 Trying {S -> a a} at 3 Trying 'a' at 3 Matched 'a' at 3 Trying 'a' at 4 Matched 'a' at 4 Matched {S -> a a} at 3 Trying 'a' at 5 Matched 'a' at 5 Matched {S -> a S a} at 2 Trying 'a' at 6 Failed 'a' at 6 Failed {S -> a S a} at 1 Trying {S -> a a} at 1 Trying 'a' at 1 Matched 'a' at 1 Trying 'a' at 2 Matched 'a' at 2 Matched {S -> a a} at 1 Trying 'a' at 3 Matched 'a' at 3 Matched {S -> a S a} at 0 Trying$ at 4
Failed $at 4 Failed {S_ -> S$} at 0
'a' * 6 : Fail

• That the first alternative ($S \to a S a$) matches doesn't mean the second one doesn't have to be tried. Sep 17 '21 at 14:45
• @vonbrand: That's true (for general parsing), but it doesn't reflect the backtracking algorithm which Aho, Ullman et al. describe. I believe my code is a faithful implementation of the modification of Figure 4.13 indicated in the paragraphs which immediately follow.
– rici
Sep 17 '21 at 16:44