Recursive-Descent Predictive Parser for $S \rightarrow 0S1\ |\ 01$

I am having difficulty with one of the exercises in the Dragon Book:


Exercise 2.4.1(c): Construct recursive-descent parsers, starting with
the following grammars:


$$S \rightarrow 0S1\ |\ 01$$

Yet, for constructing a feasible parser, it is required that for two productions $A \rightarrow \alpha\ |\ \beta$, their FIRST sets are disjoint. But since:


$$FIRST(0S1) = \{ 0 \} \hspace{2em}\&\hspace{2em} FIRST(01) = \{ 0 \}$$

this is not the case. How does one proceed here? Just state it is not feasible due to the stated conflict or is there alternative approach, like modfying the grammar?

You may need to modify the grammar. In general this is not necessarily possible (not every CFG is an LL(k) grammar - the class suitable for recursive descent predictive parsing). In this case we can modify the grammar to:

$$\begin{align*}
&\mathtt{1.} & S &\rightarrow 0SA \\
&\mathtt{2.} & S &\rightarrow \varepsilon \\
&\mathtt{3.} & A &\rightarrow 1 \\
\end{align*}$$

Then we have an unambiguous first and follow set for each combination of terminal and non-terminal. So the parsing table looks something like:

$$\begin{array}{l|l|l}
& 0 & 1 \\ \hline
S & \mathtt{1.} & \mathtt{2.} \\ \hline
A & & \mathtt{3.} \\
\end{array}$$

This gives an LL(1) grammar - one that can be parsed with one symbol of lookahead. It is possible to parse the original grammar without modification using 2 symbols of lookahead (making it an LL(2) grammar), Raphael explains that approach excellently in his answer.

The details are all in the dragon book of course (what isn't!), and better explained there than I can do here.

StackExchange Computer Science Q#6479, answer score: 2