Q&A Assignment #6 Chapter 4 Review Questions & Problem Set

Name : Vina Melinda

NIM  : 1801380106

Untuk kali ini saya akan menjawab Assignment #6 Problem Set dan Review Questions dari Chapter 4 dari Sebesta.

Review Questions:

6. Q: What is a state transition diagram?

A: State diagram, is a directed graph. The nodes of a state diagram are labeled with state names. The arcs are labeled with the input characters that cause the transitions among the states. An arc may also include actions the lexical analyzer must perform when the transition is taken.

State diagrams of the form used for lexical analyzers are representations

of a class of mathematical machines called finite automata. Finite automata

can be designed to recognize members of a class of languages called regular

languages. Regular grammars are generative devices for regular languages.

The tokens of a programming language are a regular language, and a lexical

analyzer is a finite automaton.

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

A: Suppose we need a lexical analyzer that recognizes only arithmetic expressions,including variable names and integer literals as operands. Assume that the variable names consist of strings of uppercase letters, lowercase letters, and digits but must begin with a letter. Names have no length limitation. The first thing to observe is that there are 52 different characters (any uppercase or lowercase letter) that can begin a name, which would require 52 transitions from the transition diagram’s initial state. However, a 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. Q: What are the two distinct goals of syntax analysis?

A: 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. In this case, recovery means it must get back to a normal state and
continue its analysis of the input program. This step is required so that the
compiler finds as many errors as possible during a single analysis of the input
program. If it is not done well, error recovery may create more errors, or at
least more error messages. 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. Q: Describe the differences between top-down and bottom-up parsers.

A: Parsers are categorized according to the direction in which they build parse trees. Top-down parsers is in which the tree is built from the root downward to the leaves. While bottom-up parsers, in which the parse tree is built from the leaves upward to the root.

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

A: 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. Q: 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) FIRST(aB) = {a}, FIRST(b) = {b}, FIRST(cBB) = {c}, Passes the test

(b) FIRST(aB) = {a}, FIRST(bA) = {b}, FIRST(aBb) = {a}, Fails the test

(c) FIRST(aaA) = {a}, FIRST(b) = {b}, FIRST(caB) = {c}, Passes the test

5. – aaAbb



Phrases: aaAbb, aAb, b

Simple phrases: b

Handle: b

-bBab



Phrases: bBab, ab

Simple phrases: ab

Handle: ab

c. aaAbBb: -

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

Grammar:

1. E → E + T

2. E → T
3. T → T * F
4. T → F
5. F → (E)
6. F → id

Parse Table (pg. 196)

Complete parse:

Stack Content	Input String	Action
0	id * (id + id) $	Shift 5
0id5	* (id + id) $	Reduce 6, Goto(0, F)
0F3	* (id + id) $	Reduce 4, Goto(0, T)
0T2	* (id + id) $	Reduce 2, 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, Goto(4, F)
0T2*7(4T2	+ id) $	Reduce 4, Goto(4, T)
0T2*7(4E8	+ id) $	Reduce 2, Goto(4, E)
0T2*7(4E8+6	id) $	Shift 6
0T2*7(4E8+6id5	) $	Shift 5
0T2*7(4E8+6F3	) $	Reduce 6, Goto(6, F)
0T2*7(4E8+6T9	) $	Reduce 4, Goto(6, T)
0T2*7(4E8	) $	Reduce 1, Goto(4, E)
0T2*7(4E8)11	$	Shift 11
0T2*7F10	$	Reduce 5, Goto(7, F)
0 T 2	$	Reduce 5, Goto(0, T)
0 E 1	$	Reduce 2, Goto(0, E)
- ACCEPT -

8. Q: 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: Grammar:

1.      E -> E + T

2.      E -> T

3.      T -> T * F

4.      T -> F

5.      F -> ( E )

6.      F -> id

Parse table: please note that S4 in row state 0 should be under ( , instead of under *.

No	Stack	Input	Action
1	0	( id + id ) * id $	Shift 4
2	0 ( 4	id + id ) * id $	Shift 5
3	0 ( 4 id 5	+ id ) * id $	Reduce 6, Goto(4, F)
4	0 ( 4 F 3	+ id ) * id $	Reduce 4, Goto(4, T)
5	0 ( 4 T 2	+ id ) * id $	Reduce 2, Goto(4, E)
6	0 ( 4 E 8	+ id ) * id $	Shift 6
7	0 ( 4 E 8 + 6	id ) * id $	Shift 5
8	0 ( 4 E 8 + 6 id 5	) * id $	Reduce 6, Goto(6, F)
9	0 ( 4 E 8 + 6 F 3	) * id $	Reduce 4, Goto(6, T)
10	0 ( 4 E 8 + 6 T 9	) * id $	Reduce 1, Goto(4, E)
11	0 ( 4 E 8	) * id $	Shift 11
12	0 ( 4 E 8 ) 11	* id $	Reduce 5, Goto(0, F)
13	0 F 3	* id $	Reduce 4, Goto(0, T)
14	0 T 2	* id $	Shift 7
15	0 T 2 * 7	id $	Shift 5
16	0 T 2 * 7 id 5	$	Reduce 6, Goto(7, F)
17	0 T 2 * 7 F 10	$	Reduce 3, Goto(0, T)
18	0 T 2	$	Reduce 2, Goto(0, E)
19	0 E 1	$	Accept

9. Q: 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_stmt> -> WHILE ‘(‘ (<arith_expr> | <logic_expr>) ‘)’ <block> <block> -> <stmt> | ‘{‘ <stmt> {<stmt>} ‘}’

10. Q: 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.

A: 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> ‘}’