MCS-388 Homework 2 (Spring 2008)

Due: February 29, 2008

Eliminate all left recursion (direct and indirect) from the following grammar:
```
S -> S a | B c | d
B -> S e | f
```
For the following grammar
```
S -> ( L ) | a
L -> S T
T -> ε | , L
```
1. Construct the FIRST and FOLLOW sets.
2. Construct the predictive parsing table.
3. Show (in the style of Figure 4.21, p. 228) the actions of the predictive parser on input ((a,a),a).
Is the following grammar LL(1)? Explain how you know. Also, if the grammar is not LL(1), write an LL(1) grammar for the same language.
```
S -> a | b C
C -> S | a d
```