Copyright © 2006 Gradiance Corporation.

 

 

     

Top-Down Parsing

 

 

 

Predictive and LL parsing.

 

1.  

Create a predictive parsing table for the following grammar with productions numbered 1-6.

  1. S → AB
  2. S → B
  3. A → aA
  4. A → ε
  5. B → bB
  6. B → ε

Indicate which of the following statements is true about one of the entries of your table. 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(B,$) = 5

 

 b) 

T(A,b) = 3

 

 c) 

T(S,a) = both 1 and 2

 

 d) 

T(A,a) = 3

 

 

 

 

 

2.  

Construct the predictive parsing table for this LL(1) grammar: 

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

Then, identify the correct table entry from the list below. Note, T(X,Y) is the production with which variable X will be expanded, when the lookahead symbol is Y. Also, "T(X,Y) = error" means that there is no production with which to expand X on lookahead Y.

 

 

 

 a) 

T(C,d) = error

 

 b) 

T(B,b) = B → b

 

 c) 

T(A,b) = A → a

 

 d) 

T(D,e) = D → d

 

 

 

 

 

3.  

Construct the predictive parsing table for this LL(1) grammar: 

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

Then, identify the correct table entry from the list below. Note, T(X,Y) is the production with which variable X will be expanded, when the lookahead symbol is Y. Also, "T(X,Y) = error" means that there is no production with which to expand X on lookahead Y.

 

 

 

 a) 

T(E,e) = E → e

 

 b) 

T(B,c) = error

 

 c) 

T(D,$) = error

 

 d) 

T(B,$) = B → ε