NIM: 1801382963
Kali ini saya akan menjawab Assignment #4 dari Chapter 4 Programming Language Concepts R Sebesta
Review Questions
6. What is
a state transition diagram?
*A state
transition diagram is a type of diagram used in computer science and related
fields to describe the behavior of systems. State diagrams require that the
system described is composed of a finite number of states.
7. Why are
character classes used, rather than individual characters, for the letter and
digit transitions of a state diagram for a lexical analyzer?
* 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. 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. 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 St 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.
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 St 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. Describe
the differences between top-down and bottom-up parsers.
*Bottom-up
parsing is a strategy for analyzing unknown data relationships that attempts to
identify the most fundamental units first, and then to infer higher-order
structures from them. It attempts to build trees upward toward the start
symbol.
Top-down
parsing is a strategy of analyzing unknown data relationships by hypothesizing
general parse tree structures and then considering whether the known
fundamental structures are compatible with the hypothesis.
10. Describe
the parsing problem for a top-down parser.
*The
parsing problems for a top-down parser:
-Only
judges grammaticality.
-Stops when
it finds a single derivation.
-No
semantic knowledge employed.
-No way to
rank the derivations.
-Problems with
left-recursive rules.
-Problems with ungrammatical sentences.
Problem Set
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. Acccbbc
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.
*<while_stmt> -> WHILE '(' (<arith_expr> | <logic_expr>) ')' <block>
<block> -> <stmt> | '{' <stmt> {<stmt>} '}'
