Archive for Oktober 2014
Chapter 4
Name : Romy Hermawan
NIM : 1801378902
Class : LD001
Lecturer: Ir. Tri Djoko Wahjono,M.Sc
REVIEW QUESTION
6. What is a state transition diagram?
Answer:
A state transition diagram, or just 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.
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.
Answer:
-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. What are two distinct goals of syntax analysis?
Answer:
to detect syntax errors in a given program and to proccedure a parse tree, or possibly only the information required to build such a tree, for given program.
Answer:
to detect syntax errors in a given program and to proccedure a parse tree, or possibly only the information required to build such a tree, for given program.
9. Describe the differences between top-down and bottom-up parsers?Answer:
syntax analyzers are either top-down, meaning they construct left most derivations and a parse tree in top-down order, which mean the tree is built from the root downward to leaves.
bottom-up meaning case they construct the reverse of a rightmost derivation and a parse tree in bottom-up order which mean the parse tree is built from leaves upward to the root.
syntax analyzers are either top-down, meaning they construct left most derivations and a parse tree in top-down order, which mean the tree is built from the root downward to leaves.
bottom-up meaning case they construct the reverse of a rightmost derivation and a parse tree in bottom-up order which mean the parse tree is built from leaves upward to the root.
10. Describe the parsing problem for a top-down parser.
Answer:
1. Only judges grammaticality.
2. Stops when it finds a single derivation.
3. No semantic knowledge employed.
4. No way to rank the derivations.
5. Problems with left-recursive rules.
6. 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.
a. aAcccbbc
b. AbcaBccb
c. baBcBbbc
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 content, input string, and action for the string id * (id+id),using the grammar and parse table in section 4.5.3
Answer:
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.
Answer:
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> ‘}’
Chapter 3
Name : Romy Hermawan
NIM : 1801378902
Class : LD001
Lecturer: Ir. Tri Djoko Wahjono,M.Sc
6. Define a left-recursive grammar rule
Answer:
A left-recursive grammar rule means that when a grammar rule has its left-hand side(LHS) also appearing at the beginning of its right hand side(RHS) so therefore the rule is said to be left-recursive.
7. What three extensions are common to most EBNF’s?
Answer:
-The first one is denotes an optional part of an RHS, which is delimited by brackets.
-The second extension is the use of braces in an RHS to indicate that the enclosed part can be repeated indefinitely or left out altogether.
-The third common extension deals with multiple-choice options.
-The second extension is the use of braces in an RHS to indicate that the enclosed part can be repeated indefinitely or left out altogether.
-The third common extension deals with multiple-choice options.
8. Distinguish between static and dynamic semantics
Answer:
The static semantics defines restrictions on the structure of valid texts that are hard or impossible to express in standard syntactic formalism.And The dynamic semantics (also known as execution semantics) of a language defines how and when the various constructs of a language should produce a program behavior.
9. What purpose do predicates serve in an attribute grammar?
Answer:
Predicate functions, which state the static semantic rules of the language, are associated with grammar rules. A false predicate function value indicates a violation of the syntax or static semantics rules of the language.
10. What is the difference between a synthesized and an inherited attribute?
Answer:
-A synthesized attribute associated with the nonterminals <var> and <expr>. It is used to store the actual type, int or real, of a variable or expression. In the case of a variable, the actual type is intrinsic.
-An inherited attribute associated with the nonterminal <expr>. It is used to store the type, either int or real, that is expected for the expression, as determined by the type of the variable on the left side of the assignment statement
PROBLEM SET
6. Using the grammar in Example 3.2, show a parse tree and a leftmost
derivation for each of the following statements:
a. A = A * (B + (C * A))
b. B = C * (A * C + B)
c. A = A * (B + (C))
Answer:
a. A = A * (B + C * A))
<assign> → <id> = <expr>
→ A = <expr>
→ A = <expr> * <expr>
→ A = <id> * <expr>
→ A = A * <expr>
→ A = A * ( <expr> )
→ A = A * ( <expr> + <expr>)
→ A = A * ( <id> + <expr>)
→ A = A * ( B + (<expr>)
→ A = A * ( B + (<expr> * <expr>))
→ A = A * ( B + (<id> * <expr>))
→ A = A * ( B + (C * <expr>))
→ A = A * ( B + (C * <id> )
→ A = A * ( B + (C * A))
b. B = C * (A * C + B)
<assign> → <id> = <expr>
→ B = <expr>
→ B = <id> * <expr>
→ B = C * <expr>
→ B = C * ( <expr> )
→ B = C * ( <id> * <expr>)
→ B = C * ( A * <expr>)
→ B = C * ( A * <id> + <expr>)
→ B = C * ( A * C + <expr>)
→ B = C * ( A * C + <id>)
→ B = C * ( A * C + B)
c. A = A * (B + (C))
<assign> → <id> = <expr>
→ A = <expr>
→ A = <id> * <expr>
→ A = A * <expr>
→ A = A * (<expr>)
→ A = A * ( <id> + <expr>)
→ A = A * ( B + <expr>)
→ A = A * ( B + (<expr>))
→ A = A * ( B + (<id>))
→ A = A * ( B + (C))
7. Using the grammar in Example 3.4, show a parse tree and a leftmost
derivation for each of the following statements:
a. A = ( A + B ) * C
b. A = B + C + A
c. A = A * (B + C)
d. A = B * (C * (A + B))
Answer:
a. A = ( A + B ) * C
<assign> → <id> = <expr>
→ A = <expr>
→ A = <term>
→ A = <term> * <term>
→ A = <factor> * <term>
→ A = (<expr>) * <term>
→ A = (<term>) * <term>
→ A = (<term>+ <term>) * <term>
→ A = (<factor> + <term>) * <term>
→ A = (<id> + <term>) * <term>
→ A = ( A + <term>) * <term>
→ A = ( A + <factor>) * <term>
→ A = ( A + <id>) * <term>
→ A = ( A + B ) * <term>
→ A = <expr>
→ A = <term>
→ A = <term> * <term>
→ A = <factor> * <term>
→ A = (<expr>) * <term>
→ A = (<term>) * <term>
→ A = (<term>
→ A = (<factor> + <term>) * <term>
→ A = (<id> + <term>) * <term>
→ A = ( A + <term>) * <term>
→ A = ( A + <factor>) * <term>
→ A = ( A + <id>) * <term>
→ A = ( A + B ) * <term>
→ A = ( A + B ) * C
b. A = B + C + A
<assign> → <id> = <expr>
→ A = <expr>
→ A = <expr> + <term>
→ A = <expr> + <term> + <term>
→ A = <term> + <term> + <term>
→ A = <factor> + <term> + <term>
→ A = <id> + <term> + <term>
→ A = B + <term> + <term>
→ A = B + <factor> + <term>
→ A = B + <id> + <term>
→ A = B + C + <term>
→ A = B + C + <factor>
→ A = B + C + <id>
→ A = B + C + A
→ A = <expr>
→ A = <expr> + <term>
→ A = <expr> + <term> + <term>
→ A = <term> + <term> + <term>
→ A = <factor> + <term> + <term>
→ A = <id> + <term> + <term>
→ A = B + <term> + <term>
→ A = B + <factor> + <term>
→ A = B + <id> + <term>
→ A = B + C + <term>
→ A = B + C + <factor>
→ A = B + C + <id>
→ A = B + C + A
c. A = A * (B + C)
<assign> → <id> = <expr>
→ A = <expr>
→ A = <term>
→ A = <term> * <factor>
→ A = <factor> * <factor>
→ A = <id> * <factor>
→ A = A * <factor>
→ A = A * ( <expr> )
→ A = A * ( <expr> + <term> )
→ A = A * ( <term> + <term> )
→ A = A * ( <factor> + <term> )
→ A = A * ( <id> + <term> )
→ A = A * ( B + <term> )
→ A = A * ( B + <factor> )
→ A = A * ( B + <id> )
→ A = A * ( B + C )
→ A = <expr>
→ A = <term>
→ A = <term> * <factor>
→ A = <factor> * <factor>
→ A = <id> * <factor>
→ A = A * <factor>
→ A = A * ( <expr> )
→ A = A * ( <expr> + <term> )
→ A = A * ( <term> + <term> )
→ A = A * ( <factor> + <term> )
→ A = A * ( <id> + <term> )
→ A = A * ( B + <term> )
→ A = A * ( B + <factor> )
→ A = A * ( B + <id> )
→ A = A * ( B + C )
d. A = B * (C * (A + B))
<assign> → <id> = <expr>
→ A = <expr>
→ A = <term>
→ A = <term> * <factor>
→ A = <factor> * <factor>
→ A = <id> * <factor>
→ A = B * <factor>
→ A = B * ( <expr> )
→ A = B * ( <term>)
→ A = B * ( <term> * <factor>)
→ A = B * ( <factor> * <factor>)
→ A = B * ( <id> * <factor>)
→ A = B * ( C * <factor>)
→ A = B * ( C * ( <expr> ) )
→ A = B * ( C * ( <expr> + <term> ) )
→ A = B * ( C * ( <term> + <term> ) )
→ A = B * ( C * ( <factor> + <term> ) )
→ A = B * ( C * ( <id> + <term> ) )
→ A = B * ( C * (A + <term> ) )
→ A = B * ( C * (A + <factor> ) )
→ A = B * ( C * (A + <id> ) )
→ A = B * ( C * (A + B ) )
→ A = <expr>
→ A = <term>
→ A = <term> * <factor>
→ A = <factor> * <factor>
→ A = <id> * <factor>
→ A = B * <factor>
→ A = B * ( <expr> )
→ A = B * ( <term>)
→ A = B * ( <term> * <factor>)
→ A = B * ( <factor> * <factor>)
→ A = B * ( <id> * <factor>)
→ A = B * ( C * <factor>)
→ A = B * ( C * ( <expr> ) )
→ A = B * ( C * ( <expr> + <term> ) )
→ A = B * ( C * ( <term> + <term> ) )
→ A = B * ( C * ( <factor> + <term> ) )
→ A = B * ( C * ( <id> + <term> ) )
→ A = B * ( C * (A + <term> ) )
→ A = B * ( C * (A + <factor> ) )
→ A = B * ( C * (A + <id> ) )
→ A = B * ( C * (A + B ) )
3. Prove that the following grammar is ambiguous:
<S> => <A>
<A> => <A> + <A> | <id>
<id> => a | b | c
Answer:
There are several other characteristics of a grammar that are sometimes useful in determining whether a grammar is ambiguous.1 They include the following: (1) if the grammar generates a sentence with more than one leftmost derivation and (2) if the grammar generates a sentence with more than one rightmost derivation.
The grammar above is ambiguous because the sentence
A = B + C + A
has two distinct parse trees.The grammar specifies slightly less syntactic structure.
9. Modify the grammar of Example 3.4 to add a unary minus operator that
has higher precedence than either + or *.
Answer:
<assign> → <id> = <expr>
<id> → A | B | C
<expr> → <expr> - <term>
<expr> + <term>
| <term>
<term> → <term> * <factor>
| <factor>
<factor> → ( <expr> )
| <id>
5. Describe, in English, the language defined by the following grammar:
<S> => <A> <B> <C>
<A> => a <A> | a
<B> => b <B> | b
<C> => c <C> | c
Answer:
Chapter 2
Name : Romy Hermawan
NIM : 1801378902
Class : LD001
Lecturer: Ir. Tri Djoko Wahjono,M.Sc
REVIEW QUESTIONS
6. What hardware
capability that first appeared in the IBM 704 computer
strongly affected the
evolution of programming languages? Explain why
Answer:
The
Hardware Capability that IBM 704 had is
the indexing and floating-point.Its capabilities prompted the development of
Fortran because it was able to support floating-point operations hardware.
7. In what year was the
Fortran design project begun?
Answer:
May
1954
8. What was the primary
application area of computers at the time Fortran
was designed?
Answer:
Mathematics
9. What was the source
of all of the control flow statements of Fortran I?
Answer:
They
were based on 704 Instructions
10. What was the most
significant feature added to Fortran I to get Fortran
II?
Answer:
The
Independent Compilation of Subroutines
