Copyright © 2006 Gradiance Corporation.

 

 

     

FIRST AND FOLLOW

 

 

 

Construction of FIRST and FOLLOW sets for grammars.

 

1.  

Compute the FOLLOW set for each variable of this grammar: 

 
S → ABCDE
A → a
B → b | ε
C → c
D → d | ε
E → e | ε
 

Then, identify the correct value for one of these variables from the list below.

 

 

 

 a) 

FOLLOW(A) = {b}

 

 b) 

FOLLOW(A) = {a, b, c}

 

 c) 

FOLLOW(C) = {d, e, $}

 

 d) 

FOLLOW(D) = {d, e, $}

 

 

 

 

 

2.  

Consider the grammar: 

S → AaAb | BbBa
A → ε
B → ε

Compute FIRST for all grammar symbols and FOLLOW for all nonterminals. Identify the statement below that is not true.

 

 

 

 a) 

a is in FIRST(S)

 

 b) 

a is in FIRST(a)

 

 c) 

B is in FIRST(S)

 

 d) 

ε is in FIRST(A)

 

 

 

 

 

3.  

Here is an LL(1) grammar that generates all and only the strings with an equal number of a's and b's:

  1. S → aB
  2. S → bA
  3. S → ε
  4. A → bAA
  5. A → aS
  6. B → aBB
  7. B → bS

Find the FIRST and FOLLOW sets for each of the variables. Then, construct the LL(1) parsing table for the grammar. Finally, indicate which of the following statements is true. Note: we use the notation T(X,c) to represent (by its number) the production used to expand variable X when c is the lookahead. $ is the lookahead that represents the end of the input. T(X,c) = error means there is no correct choice of expansion.

 

 

 

 a) 

T(S,$) = error

 

 b) 

FOLLOW(B) = {a,b}

 

 c) 

FIRST(B) = {a,b,ε}

 

 d) 

T(A,a) = 5

 

 

 

 

 

4.  

Compute the FOLLOW set for each variable of this grammar: 

 
S → ABCDE
A → a
B → b | ε
C → c | ε
D → d
E → e | ε
 

Then, identify the correct value for one of these variables from the list below.

 

 

 

 a) 

FOLLOW(C) = {d}

 

 b) 

FOLLOW(A) = {B, b, c, d}

 

 c) 

FOLLOW(A) = {b}

 

 d) 

FOLLOW(A) = {a, b, c, d}

 

 

 

 

 

5.  

Here is an ambiguous grammar for strings with two kinds of balanced parentheses, round and square: 

     S → (S) | [S] | SS | ε

Which of the following is not in FOLLOW(S)?

 

 

 

 a) 

)

 

 b) 

$

 

 c) 

(

 

 d) 

ε