The grammar $S\rightarrow a\:S\:a \mid \: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\rightarrow a \:a$ first, then we shall only recognize the string $aa$. Thus, any reasonable recursive-descent parser will try $S\rightarrow a\: S\: a$ first.
- Show that this recursive-descent parser recognizes inputs $aa$, $aaaa$, and $aaaaaaaa$, but not $aaaaaa$.
- What language does this recursive-descent parser recognize?
The following exercises are useful steps in the construction of a "Chomsky Normal Form" grammar from arbitrary grammars, as defined in Question $4.4.8$.
