chapter 7

Name: Billy
NIM : 1801374785

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

Review Questions No .6-10 :

6. What associativity rules are used by APL?

In APL, all operators have the same level of precedence. Thus, the order of evaluation of operators in APL expressions is determined entirely by the associativity rule, which is right to left for all operators.

For example, in the expression : A × B + C

the addition operator is evaluated first, followed by the multiplication operator (* is the APL multiplication operator). If A were 3, B were 4, and C were 5, then the value of this APL expression would be 27.

7. What is the difference between the way operators are implemented in C++ and Ruby?

What sets Ruby apart from the C-based languages in the area of expressions is that all of the arithmetic, relational, and assignment operators, as well as array indexing, shifts, and bitwise logic operators, are implemented as methods. For example, the expression a + b is a call to the + method of the object referenced by a, passing the object referenced by b as a parameter.

8. Define functional side effect.

A side effect of a function, naturally called a functional side effect, occurs when the function changes either one of its parameters or a global variable. (A global variable is declared outside the function but is accessible in the function.)

9. What is a coercion?

Coercion was defined as an implicit type conversion that is initiated by the compiler. 

Type conversions explicitly requested by the programmer are referred to as explicit conversions, or casts, not coercions.

10. What is a conditional expression?

If-then-else statements can be used to perform a conditional expression assignment. For example, consider :

if (count == 0)

       average = 0;

else

       average = sum / count;

In the C-based languages, this code can be specified more conveniently in an assignment statement using a conditional expression, which has the form

expression_1 ? expression_2 : expression_3.

Problem Set  No .6-10 :

6. Should C’s single-operand assignment forms (for example, ++count) be included in other languages (that do not already have them)? Why or why not?

Yes C should, because it will ease the increment or even decrement while we use in looping rather than manually by the assigning, and also by using that we can easily know that it is not operation, instead it is an increment or decrement which is usually used in repetition.

7. Describe a situation in which the add operator in a programming language would not be

commutative.

It wouldn’t be commutative when it deals with the negative integers. Recall that we can consider subtraction as addition in which one of two operator is a negative integer.

8. Describe a situation in which the add operator in a programming language would not be associative.

It is not associative when it includes the other operator with higher precedence like the multiplication and division.

9. Assume the following rules of associativity and precedence for expressions:

Precedence Highest *, /, not

+, –, &, mod

– (unary)

=, /=, < , <=, >=, >

Lowest or, xor

Associativity Left to right

Show the order of evaluation of the following expressions by parenthesizing all sub expressions and placing a superscript on the right parenthesis to indicate order. For example, for the expression

a + b * c + d

the order of evaluation would be represented as

((a + (b * c)1)2 + d)3

a. a * b - 1 + c                  ((( a * b )1 - 1)2 + c )3
b. a*(b-1)/c mod d           ((( a * ( b - 1 )1 )2 / c )3 mod d )4
c. (a-b)/c&(d*e/a-3)         (((a - b)1 / c)2 & ((d * e)3 / a)4 - 3)5)6
d. -a or c = d and e           (( -a )1 or ( ( c = d )2 and e )3 )4
e. a>b xor c or d<=17      (((a > b)1 xor c)3 or (d <= 17)2 )4
f. –a + b                            (–( a + b )1 )2

10. Show the order of evaluation of the expressions of Problem 9, assuming that there are no precedence rules and all operators associate right to left.

(a) ( a * ( b – ( 1 + c )1 )2 )3
(b) ( a * ( ( b – 1 )2 / ( c mod d )1 )3 )4
(c) ( ( a – b )5 / ( c & ( d * ( e / ( a – 3 )1 )2 )3 )4 )6
(d) ( – ( a or ( c = ( d and e )1 )2 )3 )4
(e) ( a > ( xor ( c or ( d <= 17 )1 )2 )3 )4
(f) ( – ( a + b )1 )2

Chapter 6 Programming Language Concepts R Sebesta

Chapter 6 Programming Language Concepts R Sebesta

Nama: Billy
NIM: 1801374785

Review Questions

6. What are the advantages of user-defined enumeration types?

The advantages are readability and reliability.

7. In what ways are the user-defined enumeration types of C# more reliable than those of C++?

C# enumeration types are like those of C++, except that they are never coerced to integer. So, operations on enumeration types are restricted to those that make sense. Also, the range of values is restricted to that of the particular enumeration type.

8. What are the design issues for arrays?

 What types are legal for subscripts?

Are subscripting expressions in element references range checked?

When are subscript ranges bound?

When does allocation take place?

What is the maximum number of subscripts?

Can array objects be initialized?

Are any kind of slices supported?

9. Define static, fixed stack-dynamic, stack-dynamic, fixed heap-dynamic, and heap-dynamic arrays. What are the advantages of each?

   Static: subscript ranges are statically bound and storage allocation is static (before run-time)

Advantage: efficiency (no dynamic allocation).

            Fixed stack-dynamic: subscript ranges are statically bound, but the allocation is done at declaration time.

Advantage: space efficiency .

Stack-dynamic: subscript ranges are dynamically bound and the storage allocation is dynamic (done at run-time)

Advantage: flexibility (the size of an array need not be known until the array is to be used).

Fixed heap-dynamic: similar to fixed stack-dynamic: storage binding is dynamic but fixed after allocation (i.e., binding is done when requested and storage is allocated from heap, not stack).

Heap-dynamic: binding of subscript ranges and storage allocation is dynamic and can change any number of times.

Advantage: flexibility (arrays can grow or shrink during program execution).

10. What happens when a nonexistent element of an array is referenced in Perl?

If an r-value is required, undef is returned. If an l-value is required, the array is extended, then the newly created but undefined element is returned. No error is reported.

Problem Set

6. Explain all of the differences between Ada’s subtypes and derived types.

Ada’s subtype is compatible with its base type, so you can mix operands of the base type with operands of the base type. While Ada’s derived type is a completely separate type that has the same characteristics as its base type. We can’t mix operands of a derived type with operands of the base type.

7. What significant justification is there for the -> operator in C and C++?

The only justification for the -> operator in C and C++ is writability. It is slightly easier to write p -> q than (*p).q.

8. What are all of the differences between the enumeration types of C++ and those of Java?

In C++, an enumeration is just a set of named, integral constants. Also, C++ will implicitly convert enum values to their integral equivalent. In Java, an enumeration is more like a named instance of a class. You have the ability to customize the members available on the enumeration. Java will explicitly convert enum values to their integral equivalent.

9. The unions in C and C++ are separate from the records of those languages, rather than combined as they are in Ada. What are the advantages and disadvantages to these two choices?

Ada advantage:
Unconstrained variant records in Ada allow the values of their variants to change types during execution.

disadvantage:

The type of the variant can be changed only by assigning the entire record, including the discriminant. This disallows inconsistent records because if the newly assigned record is a constant data aggregate, the value of the tag and the type of the variant can be statically checked for consistency.

10. Multidimensional arrays can be stored in row major order, as in C++, or in column major order, as in Fortran. Develop the access functions for both of these arrangements for three-dimensional arrays.

Let the subscript ranges of the three dimensions be named min(1), min(2), min(3), max(1), max(2), and max(3). Let the sizes of the subscript ranges be size(1), size(2), and size(3). Assume the element size is 1.

Row Major Order:

 location(a[i,j,k]) = (address of a[min(1),min(2),min(3)]) + ((i-min(1))*size(3) + (j-min(2)))*size(2) + (k-min(3))

Column Major Order:

 location(a[i,j,k]) = (address of a[min(1),min(2),min(3)]) + ((k-min(3))*size(1) + (j-min(2)))*size(2) + (i-min(1))

Chapter 5 Programming Language Concepts R Sebesta

Chapter 5 Programming Language Concepts R Sebesta

Nama: Billy
NIM: 1801374785

Review Questions

6. What is the l-value of a variable? What is the r-value?

L-value is the address of a variable , because the address is what is required when the name of a variable appears in the left side of an assignment.

R-value is a name for a variable's value because it is what is required when the name of the variable appears in the right side of an assignment statement

7. Define binding and binding time.

A binding is an association between an attribute and an entity, such as between a variable and its type or value, or between an operation and a symbol.

Binding time is the time at which a binding takes place.

8. After language design and implementation [what are the four times bindings can take place in a program?

-compile time (bind a variable to a type in C or Java)

-link time

-load time (bind a C or C++ static variable to a memory cell)

-run time (bind a nonstatic local variable to a memory cell)

9. Define static binding and dynamic binding.

A static binding is if it first occurs before run time and remains unchanged throughout program execution. A dynamic binding is if it first occurs during execution or can change during execution of the program.

10. What are the advantages and disadvantages of implicit declarations?

Advantages:

-Can make it easier for the programmer to write code, since he/she doesn’t have to also write the declarations

-Maintainability can be easier too, since the information about a variable’s type is not written down in a part of the program distant from where the variable is used

-Readability can be better since a reader can probably infer the variable’s name or its context

Disadvantage:

-Reliability will probably suffer since the programmer may not always realize the type that the compiler assigned a variable

Problem Set

6. Consider the following JavaScript skeletal program:

// The main program
var x;
function sub1() {
var x;
function sub2() {
. . .
}
}
function sub3() {
. . .
}
Assume that the execution of this program is in the following unit order:
main calls sub1
sub1 calls sub2
sub2 calls sub3
a. Assuming static scoping, in the following, which declaration
of x is the correct one for a reference to x?
i. sub1
ii. sub2
iii. sub3
b. Repeat part a, but assume dynamic scoping.

a. In sub1: sub1
    In sub2: sub1
    In sub3: main

b.In sub1: sub1
   In sub2: sub1
   In sub3: sub1.

7. Assume the following JavaScript program was interpreted using static-scoping rules. What value of x is displayed in function sub1? Under dynamic-scoping rules, what value of x is displayed in function sub1?

var x; function sub1() {

  document.write("x = " + x + "<br />");

}

function sub2() {

  var x;

  x = 10;

  sub1();

}

x = 5;

sub2();

*Static scope: x=5

Dynamic scope: x=10

8. Consider the following JavaScript program:

var x, y, z; function sub1() {

  var a, y, z;

  function sub2() {

    var a, b, z;

    . . .

  }

  . . .

}

function sub3() {

  var a, x, w;

  . . .

}

List all the variables, along with the program units where they are declared, that are visible in the bodies of sub1, sub2, and sub3, assum- ing static scoping is used.

*sub1: a(sub1) y(sub1) z(sub1) x(main) 
sub2: a(sub2) b(sub2) z(sub2) y(sub1) x(main) 
sub3: a(sub3) x(sub3) w(sub3) y(main) z(main)

9. Consider the following Python program:

x = 1; y = 3;

z = 5;

def sub1():

  a = 7;

  y = 9;

  z = 11;

  . . .

def sub2():

  global x;

  a = 13;

  x = 15;

  w = 17;

  . . .

  def sub3():

    nonlocal a;

    a = 19;

    b = 21;

    z = 23;

    . . .

. . .

List all the variables, along with the program units where they are declared, that are visible in the bodies of sub1, sub2, and sub3, assum- ing static scoping is used.

* Variable           Where Declared

In sub1:

a                     sub1

y                     sub1

z                     sub1

x                     main

In sub2:

a                     sub2

x                     sub2

w                    sub2

y                     main

z                     main

In sub3:

a                     sub3

b                     sub3

z                     sub3

w                    sub2

x                     sub2

y                     main

10. Consider the following C program:

void fun(void) {  int a, b, c; /* definition 1 */

  . . .

  while (. . .) {

    int b, c, d; /*definition 2 */   

. . .  à1

    while (. . .) {

int c, d, e; /* definition 3 */   

 . . . à 2

     }  

 . . .  -à3

    } 

. . .  à4

}

For each of the four marked points in this function, list each visible vari- able, along with the number of the definition statement that defines it.

* Point 1: a:1 b:2 c:2 d:2

Point 2: a:1 b:2 c:3 d:3 e:3

Point 3: a:1 b:2 c:2 d:2

Point 4: a:1 b:1 c:1

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.

Chapter 4 Concepts of Programming Languages, Robert W. Sebesta.  Lexical and Syntax Analysis

Nama : Billy
NIM   : 1801374785

Review Question:
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?

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

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

 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.

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.

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.

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

b. AbcaBccb

c. baBcBbbc

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])
–ACCEPT–

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.

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> -> for ‘(‘ [[<type>] <id> = <expr> {, [<type>] <id> = <expr>}] ; [<expr>] ; [<expr> {, <expr>}] ‘)’ ‘{‘ <stmt_list> ‘}’

<assign> → <id> = <expr> <id> → A | B | C <expr> → <expr> + <term> | <term> | - <factor> <term> → <term>*<factor> | <factor> <factor> → (<expr>)

Chapter 3 Concepts of Programming Languages, Robert W. Sebesta. Describing Syntax and Semantics

Nama : Billy
NIM   : 1801374785

Review Question:

6. Define a left-recursive grammar rule.
When a grammar rule has its left hand side (LHS) also appearing at the beginning of its right hand side (RHS), the rule is said to be left recursive. 

7. What three extensions are common to most EBNFs?
Three extensions are common to most EBNFs:
a. The first extension denotes an optional part of a RHS, which is delimited by brackets. For example: <if_stmt> -> if ( <expr> ) stmt [ else <stmt> ]
b. 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. For example: <ident_list> -> ident {, <ident> }
c. The third extension deals with multiple choice options. For example: <term> -> <term> ( *|/|% ) <factor>

8. Distinguish between static and dynamic semantics.
Static semantics is more on the legal forms of programs (syntax rather semantics) and is only indirectly related to the meaning of the programs during execution. Static semantics is so named because the analysis required checking these specifications can be done at compile time. Dynamic semantics is describing the meaning of the programs. Programmers need to know precisely what statements of a language do. Compile writers determine the semantics of a language for which they are writing compilers from English descriptions.

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

The use of predicates functions is to state the static semantic rules of the language.

10. What is the difference between a synthesized and an inherited attribute
The synthesized attributes are the result of the attribute evaluation rules, and may also use the values of the inherited attributes. The inherited attributes are passed down from parent nodes. In some approaches, synthesized attributes are used to pass semantic information up the parse tree, while inherited attributes help pass semantic information down it.
For instance, when constructing a language translation tool, such as a compiler, it may be used to assign semantic values to syntax constructions. Also, it is possible to validate semantic checks associated with a grammar, representing the rules of a language not explicitly imparted by the syntax.

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

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

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

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