Copyright © 2006 Gradiance Corporation.

Grammatical Derivations and Parse Trees

---

---

Leftmost, rightmost derivations and their relationship to parse trees of a CFG.

---

1.	Here is a grammar for postfix expressions using the common four binary arithmetic operators: S → SS+ | SS- | SS* | SS/ | a Find a leftmost derivation for the terminal string aa+a/a*. Then, identify one of the steps (left-sentential forms) in the derivation from the list below.

a)

SS+S/S*

b)

Sa*

c)

aS/a*

d)

aa+S*

2.	The parse tree below represents a rightmost derivation according to the grammar S → AB, A → aS|a, B → bA. Which of the following is a right-sentential form in this derivation?

a)

aSB

b)

aABba

c)

aabAba

d)

abaAbA

3.	Here is a parse tree that uses some unknown grammar G. Which of the following productions is surely one of those for grammar G?

a)	S → AB
b)	B → AS
c)	S → AbA
d)	A → SB

4.	The parse tree below represents a leftmost derivation according to the grammar S → AB, A → aS|a, B → bA. Which of the following is a left-sentential form in this derivation?

a)

aaABBB

b)

aSbA

c)

aabAba

d)

aaBB

5.	Here is a grammar for postfix expressions using the common four binary arithmetic operators: S → SS+ | SS- | SS* | SS/ | a Find a rightmost derivation for the terminal string aa/a+a-. Then, identify one of the steps (right-sentential forms) in the derivation from the list below.

a)

aS/a+a-

b)

aS/a+S-

c)

SS+a-

d)

aa/S+S-

6.	Here is a grammar for postfix expressions using the common four binary arithmetic operators: S → SS+ | SS- | SS* | SS/ | a Find a leftmost derivation for the terminal string aa-aa/+. Then, identify one of the steps (left-sentential forms) in the derivation from the list below.

a)

SSa/+

b)

aa-SS+

c)

aS-S+

d)

aS-aS/+

7.	Here is a grammar for postfix expressions using the common four binary arithmetic operators: S → SS+ | SS- | SS* | SS/ | a Find a rightmost derivation for the terminal string aa*aa-+. Then, identify one of the steps (right-sentential forms) in the derivation from the list below.

a)

SSa-+

b)

aa*SS-+

c)

aS+

d)

SaS-+