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

Question

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?

Answer 1

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.

Answer 2

You can grant your parser more than one symbol lookahead. I am not sure whether the term "recursive descent" applies in all definitions, but there is likely no big difference in the actual implementation.

Consider this recursive-descent acceptor:

S(input : String, start : int) : int {
  if ( start + 1 >= input.length ) {
    return -1;
  }
  if ( input[start, start + 1] == "00" ) {
    int sub = S(input, start + 1)
    return sub != -1 && sub + 1 < input.length && input[sub + 1] == '1' 
           ? sub + 1 
           : -1
  }
  else if ( input[start, start + 1] == "01" ) {
    return start + 1
  }
  else {
    return -1
  }
}

input is the whole input string, start is the starting index of the portion the current call is supposed to match. -1 encodes that the (sub)word could not be parsed, otherwise the return value is the last consumed index. That is, input is generated by the grammar iff S(input,0) == input.length-1.