Chapter 4 Answers

Nama : Christian Gunawan
NIM : 1801384174

Kali ini saya akan menjawab assigntment #4 dari chapter 4 Programming Language Concepts R Sebesta E-book :

Review Questions#6-10 :

6. What is a state transition diagram?

A state transition diagram, or just state diagram, is a directed graph. The

nodes of a state diagram are labeled with state names.

7. Why are character classes used, rather than individual characters, for the letter and digit transitions of a state diagram for a lexical analyzer?

Lexical analyzer is interested only in determining that it is a name and is not concerned with which specific name it happens to be. Therefore, we define a character class named LETTER for all 52 letters and use a single transition on the first letter of any name.

8. What are the two distinct goals of syntax analysis?

There are two distinct goals of syntax analysis: First, the syntax analyzer must check the input program to determine whether it is syntactically correct. When an error is found, the analyzer must produce a diagnostic message and recover.

The second goal of syntax analysis is to produce a complete parse tree, or at least trace the structure of the complete parse tree, for syntactically correct input. The parse tree (or its trace) is used as the basis for translation.

9. Describe the differences between top-down and bottom-up parsers.

The two broad classes of parsers are top-down, in which the tree is built from the root downward to the leaves, and bottom-up, in which the parse tree is built from the leaves upward to the root.

10. Describe the parsing problem for a top-down parser.

if the current sentential form is

xA α

and the A-rules are A → bB, A → cBb, and A → a, a top-down parser must choose among these three rules to get the next sentential form, which could be xbBα , xcBbα, or xaα . This is the parsing decision problem for top-down parsers.

Problem Set#6-10 :

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.

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

a. aAcccbbc

Phrases:

      aAcccbbc, aAcccb, Ac, ccb, c_1, c_2

Simple phrases:

      Ac, c_1, c_2

Handle:

      Ac

b. AbcaBccb

Phrases:

            AbcaBccb, caBccb, aBcc, aBc, c_1

Simple Phrases:

            c_1

Handle:

            c_1

c. baBcBbbc

Phrases:

      baBcBbbc, aBcBbb, aBcBb, cBb

Simple Phrases:

      cBb

Handle:

      cBb

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.

Stack	Input	Action
0	id * (id + id) $	Shift 5
0id5	* (id + id) $	Reduce 6 (Use GOTO[0, F])
0F3	* (id + id) $	Reduce 4 (Use GOTO[0, T])
0T2	* (id + id) $	Reduce 2 (Use GOTO[0, E])
0T2*7	(id + id) $	Shift 7
0T2*7(4	id + id ) $	Shift 4
0T2*7(4id5	+ id ) $	Shift 5
0T2*7(4F3	+ id ) $	Reduce 6 (Use GOTO[4, F])
0T2*7(4T2	+ id ) $	Reduce 4 (Use GOTO[4, T])
0T2*7(4E8	+ id ) $	Reduce 2 (Use GOTO[4, E])
0T2*7(4E8+6	id ) $	Shift 6
0T2*7(4E8+6id5	) $	Shift 5
0T2*7(4E8+6F3	) $	Reduce 6 (Use GOTO[6, F])
0T2*7(4E8+6T9	) $	Reduce 4 (Use GOTO[6, T])
0T2*7(4E8	) $	Reduce 1 (Use GOTO[4, E])
0T2*7(4E8)11	$	Shift 11
0T2*7F10	$	Reduce 5 (Use GOTO[7, F])
0T2	$	Reduce 5 (Use GOTO[0, T])
0E1	$	Reduce 2 (Use GOTO[0, E])

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.

Stack	Input	Action
0	(id+id)*id $	Shift 5
0id5	* (id + id) $	Reduce 6 (Use GOTO[0, F])
0F3	* (id + id) $	Reduce 4 (Use GOTO[0, T])
0T2	* (id + id) $	Reduce 2 (Use GOTO[0, E])
0T2*7	(id + id) $	Shift 7
0T2*7(4	id + id ) $	Shift 4
0T2*7(4id5	+ id ) $	Shift 5
0T2*7(4F3	+ id ) $	Reduce 6 (Use GOTO[4, F])
0T2*7(4T2	+ id ) $	Reduce 4 (Use GOTO[4, T])
0T2*7(4E8	+ id ) $	Reduce 2 (Use GOTO[4, E])
0T2*7(4E8+6	id ) $	Shift 6
0T2*7(4E8+6id5	) $	Shift 5
0T2*7(4E8+6F3	) $	Reduce 6 (Use GOTO[6, F])
0T2*7(4E8+6T9	) $	Reduce 4 (Use GOTO[6, T])
0T2*7(4E8	) $	Reduce 1 (Use GOTO[4, E])
0T2*7(4E8)11	$	Shift 11
0T2*7F10	$	Reduce 5 (Use GOTO[7, F])
0T2	$	Reduce 5 (Use GOTO[0, T])
0E1	$	Reduce 2 (Use GOTO[0, E])

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.

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

<for_stmt> -> FOR '(' (<arith_expr>; <logic_expr>; <arith_expr>) ')'  <block>
  <block> -> <stmt> | '{' <stmt> {<stmt>} '}'