A non-school issue, but it appears in the Dragon book (Compiled: Principles, Methods and Tools) in the exercise:
Grammar:
S :: = aSa | aa
generates all strings of length length except an empty string.
a) Build a recursive descent parser with a countdown for this grammar that tries an alternative aSa before aa. Show that the procedure for S succeeds at 2, 4, or 8 a, but fails at 6 a. b) What language does your parser recognize?
I'm at a dead end. It seems that if 4 a is recognized as S, and two a between S is recognized, then 6 a should be recognized. I tried to implement a parser in C, but this one recognizes all the even numbers a. This is not an inability to recognize 6 a. What does this exercise mean?
/* AC implementation of Exercise 4.13 in the Dragon Book */ /* The grammar: S ::= aSa | aa */ /* Construct a recursive-descent parser with backtracking for this grammar that tries the alternative aSa before aa. Show that the procedure for S succeeds on 2, 4, or 8 a's, but fails on 6 a's. */ #include <string.h> #include <stdio.h> int S(const char *str, int start, int end); int aSa(const char *str, int start, int end); int aa(const char *str, int start, int end); /* returns 1 if a match, 0 otherwise */ int S(const char *str, int start, int end) { if(aSa(str, start, end)) return 1; else if(aa(str, start, end)) return 1; return 0; } /* returns 1 if a match, 0 otherwise */ int aSa(const char *str, int start, int end) { int len = end - start; if (len < 3) return 0; if(str[0] != 'a') return 0; if (!S(str, start+1, end-1)) return 0; if(str[len-1] != 'a') return 0; return 1; } /* returns 1 if a match, 0 otherwise */ int aa(const char *str, int start, int end) { int len = end - start; if(len != 2) return 0; if(str[0] == str[1] && str[0] == 'a') return 1; return 0; } int main() { char str[20]; printf("Enter a string: \n"); scanf("%s", str); int match = S(str, 0, strlen(str)); if(match) printf("The string %s matches\n", str); else printf("The string %s does not match\n", str); return 0; }