Chapter 4 : Problem Set

Q6 : Given the following grammar and the right sentential form, draw a parse tree and show the phrases and simple phrases, as well as the handle.

S → AbB _ bAc A → Ab _ aBB B → Ac _ cBb _ c

a. aAcccbbc

b. AbcaBccb

c. baBcBbbc

A   :

a. S -> AbB -> aBBbB -> aAcBbB -> aAccBbbB -> aAcccbbc

b. S -> AbB -> AbcBb -> AbcAcb -> AbcaBBcb -> AbcaBccb

c. S -> bAc -> baBBc -> baBcBbc -> baBcBbbc

Q7 : Show a complete parse, including the parse stack contents, input string, and action for the string id * (id + id), using the grammar and parse table in Section 4.5.3.

A   :

Q8 : Show a complete parse, including the parse stack contents, input string, and action for the string (id + id) * id, using the grammar and parse table in Section 4.5.3.

A   :

Q9 : Write an EBNF rule that describes the while statement of Java or C++. Write the recursive-descent subprogram in Java or C++ for this rule.

A   :

While :

while-statement <= while(expression) statement
do-statement     <= do statement while (expression);

Recursive-descent subprogram :

<initializer> -> "{" <designator> { <designator> } = <expression> "}"

Q10 : Write an EBNF rule that describes the for statement of Java or C++.

A     :  “for-statement <= for(;;) statement”