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>} '}'

Chapter 3 Answers

Nama : Christian Gunawan
NIM : 1801384174

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

Review Questions #6-10 :
6. Define a left-recursive grammar rule.

When a grammar rule has its LHS also appearing at the beginning of its RHS, the rule is said to be left recursive. This left recursion specifies left associativity.

7. What three extensions are common to most EBNFs?

Three extensions are commonly included in the various versions of EBNF.
The first of these 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. This extension allows lists to be built with a single rule, instead of using recursion and two rules.

The third common extension deals with multiple-choice options. When a single element must be chosen from a group, the options are placed in parentheses and separated by the OR operator, |.

8. Distinguish between static and dynamic semantics.

The static semantics of a language is only indirectly
related to the meaning of programs during execution; rather, it has to do
with the legal forms of programs (syntax rather than semantics).

Dynamic semantics is a perspective on natural language semantics that emphasises the growth of information in time. It is an approach to meaning representation where pieces of text or discourse are viewed as instructions to update an existing context with new information, with an updated context as result.

9. What purpose do predicates serve in an attribute grammar?

Predicates in attribute grammar states the static semantic rules a language needs to follow. A false value in predicates indicates that there is an invalid syntax or static semantics and determines whether an action is allowed or not.

10. What is the difference between a synthesized and an inherited attribute?

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

expected_type—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-10 :
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))  

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

<assign> => <id>=<expr>

=>  A=<expr>

=> A=<term>

=> A=<term>*<factor>

=> A=<factor>*<factor>

=>  A=(<expr>)*<factor>

=>  A=(<expr>+<term>)*<factor>

=>  A=(<term>+<term>)*<factor>

=>  A=(<factor>+<term>)*<factor>

=>  A=(<id>+<term>)*<factor>

=>  A=(A+<term>)*<factor>

=>  A=(A+<factor>)*<factor>

=>  A=(A+<id>)*<factor>

=>  A=(A+B)*<factor>

=>  A=(A+B)*<id>

=>  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=A+<term>+<term>

=>  A=A+<factor>+<term>

=>  A=A+<id>+<term>

=>  A=A+C+<term>

=>  A=A+C+<factor>

=>  A=A+C+<id>

=>  A=A+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)

d. A = B * (C * (A + B))

<assign> => <id>=<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))

8. Prove that the following grammar is ambiguous:
<S> → <A>
<A> → <A> + <A> | <id>
<id> → a | b | c

A grammar is ambiguous if there are two different trees for derivation of same expression. Expressed in more formal way, a grammar is ambiguous if fr(T)=fr(T’) implies T <> T’. fr(T) means a frontier of a tree, which specifies the leaves of a tree. Therefore, if two trees have same frontiers and the grammar is ambiguous, the trees will be structurally different.

Moreover, two trees for a derivation of an expression are structurally different if the grammar allows both left and right growing of the tree.

For the grammar of this problem and the expression a=a+b+c there are two different leftmost derivations:

<S>-><A>

-> <A>+<A>

-> <A>+<A>+<A>

-> <id>+<A>+<A>

-> a+<A>+<A>

-> a+<id>+<A>

-> a+b+<A>

-> a+b+<id>

-> a+b+c

Or 

<S>-><A>

-><A>+<A>

-><id>+<A>

->a+<A>

->a+<A>+<A>

->a+<id>+<A>

->a+b+<A>

->a+b+<id>

->a+b+c

9. Modify the grammar of Example 3.4 to add a unary minus operator that
has higher precedence than either + or *.

<assign> => <id>=<expr>

<id> => A|B|C

<expr> => <expr>+<term> | <term> | - <factor>

<term> => <term>*<factor> | <factor>

<factor> => (<expr>) | <id>

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

All sentences consisting of one or more a’s followed by one or more b’s followed by one or more c’s