Problem Set Chapter 4 (Programming Language Concept)

Posted by : Andreas Kwan Rabu, 29 Oktober 2014

6. 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.

Answer :

S → AbB bAc A → Ab aBB B → Ac cBb c a.

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

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

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

7. 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.
Answer :

8. 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.
Answer :

9. 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.
Answer :

<while_stmt> -> WHILE ‘(‘ (<arith_expr> | <logic_expr>) ‘)’

<block> <block> -> <stmt> | ‘{‘ <stmt> {<stmt>} ‘}’
10. Write an EBNF rule that describes the for statement of Java or C++. Write the recursive-descent subprogram in Java or C++ for this rule.
Answer :

Assume the following non-terminals are given: <type>, <id>, <literal>, <assign>, <expr>, and <stmt_list>.

<for> -> for ‘(‘ [[<type>] <id> = <expr> {, [<type>] <id> = <expr>}] ; [<expr>] ; [<expr> {, <expr>}] ‘)’ ‘{‘ <stmt_list> ‘}’