Prentice-Hall     Addision-Wesley

Copyright © 2007 Gradiance Corporation.

 

Gradiance Online Accelerated Learning

 

 

 

 

 

     

Parse Trees --- Additional Questions

 

 



1.  

Consider the grammar G:

S → SS, S → ab

Which of the following strings is a word of L(G) AND is the yield of one of the parse trees for grammar G in the figure below?

http://www.gradiance.com/phmu/pictures/ullman_6parsetrees.gif

 

 

 

 a) 

ababab

 

 b) 

SababSabS

 

 c) 

ababababab

 

 d) 

abababababababab

 

 

 

 

 

2.  

Consider the grammar G:

S → abS, S → ab

Which of the following strings is a word of L(G) AND is the yield of one of the parse trees for grammar G in the figure below?

http://www.gradiance.com/phmu/pictures/ullman_6parsetrees.gif

 

 

 

 a) 

abababS

 

 b) 

ababababab

 

 c) 

abababababab

 

 d) 

ababababababab

 

 

 

 

 

3.  

Consider the grammar:

S → SS, S → ab

Identify in the list below the one set of parse trees which includes a tree that is NOT a parse tree of this grammar?

http://www.gradiance.com/phmu/pictures/ullman_6parsetrees.gif

 

 

 

 a) 

{(e)}

 

 b) 

{(b),(d)}

 

 c) 

{(c),(f)}

 

 d) 

{(d),(f)}

 

 

 

 

 

4.  

The parse tree below represents a leftmost derivation according to the grammar

S → AB, A → aS|a, B → bA

http://www.gradiance.com/phmu/pictures/ullman_parsetree1g.gif

Which of the following is a left-sentential form in this derivation?

 

 

 

 a) 

aaBba

 

 b) 

aSbA

 

 c) 

AbA

 

 d) 

aaBB