Return to Answer

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}$$

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

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.

You 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:

$$1. \; S\rightarrow 0SA$$ $$2. \; S \rightarrow \varepsilon\;\;\;\;\;$$ $$3. \;A \rightarrow 1\;\;\;\;\;$$

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

  | 0 | 1
==========
S | 1.| 2.
----------
A |   | 3. 

The details are all in the dragon book of course (what isn't!), and better explained there than I can do here. Apologies for the ugly table, SE doesn't support table markup.

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}$$

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

You 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:

$$1. \; S\rightarrow 0SA$$ $$2. \; S \rightarrow \varepsilon\;\;\;\;\;$$ $$3. \;A \rightarrow 1\;\;\;\;\;$$

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

  | 0 | 1
==========
S | 1.| 2.
----------
A | 3.| 

The details are all in the dragon book of course (what isn't!), and better explained there than I can do here. Apologies for the ugly table, SE doesn't support table markup.

You 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:

$$1. \; S\rightarrow 0SA$$ $$2. \; S \rightarrow \varepsilon\;\;\;\;\;$$ $$3. \;A \rightarrow 1\;\;\;\;\;$$

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

  | 0 | 1
==========
S | 1.| 2.
----------
A |   | 3. 

The details are all in the dragon book of course (what isn't!), and better explained there than I can do here. Apologies for the ugly table, SE doesn't support table markup.