Problem 1

Given the grammar below, follow the algorithm in the lecture notes to compute EPS, the set of nullible non-terminals. For each symbol, in the order added, show which grammar rule allowed you to add the symbol.

1.   S -> c A c
2.   S -> B C
3.   S -> d
5.   A -> a C A
6.   A -> a
7.   B -> b C B
8.   B -> C
9.   C -> c c C
10.  C -> epsilon

Problem 2

Using the Grammar from Problem 1 and the EPS you computed, follow the algorithm for FIRST from the notes to compute FIRST($\cdot$) for each grammar symbol. Write down, in order what you added and what rule allowed it. I'll get you started.

FIRST(a) = {a}, FIRST(b) = {b}, FIRST(c) = {c}, FIRST(d) = {d} : Initialization in Step 1 (these never change!)

                                        FIRST(S)      FIRST(A)      FIRST(B)      FIRST(C)
add c to FIRST(S) from Rule 1	           c

add d to FIRST(S) from Rule 3             c,d
	

	

	      
    

Problem 3

Using the Grammar from Problems 1 and 2 and the EPS and FIRST you computed, follow the algorithm for FOLLOW from the notes to compute FOLLOW($\cdot$) for each grammar non-terminal. Write down, in order what you added and what rule allowed it.

Problem 4

Continuing from the previous problems, write down the PREDICT sets for each grammar rule.