Assignment #7

Source:

Concepts of Programming Languages, Robert W. Sebesta.

Chapter 7: Expressions and Assignment Statements, page 342-344

By:
Name : Helena Natanael
NIM  : 1801380333

---

Review Question:

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.

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 is an implicit type of conversion only if they are widening (from a “smaller” type to a “larger” type). So int to float coercions are done across the assignment operator, but float to int coercions are not.

10. What is a conditional expression?
Conditional Expression is a logical feature of programming language which perform different actions based on true or false. 
In trinary, the format is statement ? action_1 (if true) : action_2 (if false).



Problem Sets:

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.

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)

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

                                      and
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)¹)² + d)³

1. a * b – 1 + c

( ( (a * b)¹– 1)² + c)³
2. a* ( b – 1) / c mod d
( ( (a* ( b – 1)¹ )²/ c )³ mod d)⁴
3. (a – b) / c & (d * e / a – 3)
( ( (a – b)¹/ c)² & ( ( (d * e)³ / a)⁴ – 3)⁵ )⁶
4. –a or c = d and e
( (–a)¹ or ( (c = d)² and e)³ )⁴
5. a > b xor c or d <= 17
( ( (a > b)¹ xor c)³ or (d <= 17)² )⁴
6. –a + b
( – (a + b)¹ )²

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 )¹ )² )³
b. ( a * ( ( b – 1 )² / ( c mod d )¹ )³ )⁴
c. ( ( a – b )⁵ / ( c & ( d * ( e / ( a – 3 )¹ )² )³ )⁴ )⁶
d. ( – ( a or ( c = ( d and e )¹ )² )³ )⁴
e. ( a > ( xor ( c or ( d <= 17 )¹ )² )³ )⁴
f. ( – ( a + b )¹ )²

Assignment #6

Source:

Concepts of Programming Languages, Robert W. Sebesta.

Chapter 6: Data Types, page 312-314

By:
Name : Helena Natanael
NIM  : 1801380333

---

Review Question:

6. What are the advantages of user-defined enumeration types?
Enumeration types can provide advantages in both readability and reliability. First is no arithmetic operations are legal on enumeration types; this prevents adding days of the week, for example. And second, no enumeration variable can be assigned a value outside its defined range.

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 array allocation take place?
• Are ragged or rectangular multidimensioned arrays allowed, or both?
• Can arrays be initialized when they have their storage allocated?
• What kinds of slices are allowed, if any?

9.Define static, fixed stack-dynamic, stack-dynamic, fixed heap-dynamic, and 
heap-dynamic arrays. What are the advantages of each?
A static array is one in which the subscript ranges are statically bound and storage allocation is static. The advantage of static arrays is efficiency: No dynamic allocation or deallocation is required.

A fixed stack-dynamic array is one in which the subscript ranges are statically bound, but the allocation is done at declaration elaboration time during execution. The advantage of fixed stack-dynamic arrays over static arrays is space efficiency.

A stack-dynamic array is one in which both the subscript ranges and the storage allocation are dynamically bound at elaboration time. The advantage of stack-dynamic arrays over static and fixed stack-dynamic arrays is flexibility.

A fixed heap-dynamic array is similar to a fixed stack-dynamic array, in that the subscript ranges and the storage binding are both fixed after storage is allocated. The advantage of fixed heap-dynamic arrays is flexibility the array’s size always fits the problem.

A heap-dynamic array is one in which the binding of subscript ranges and storage allocation is dynamic and can change any number of times during the array’s lifetime. The advantage of heap-dynamic arrays over the others is flexibility: Arrays can grow and shrink during program execution as the need for space changes.

10.What happens when a nonexistent element of an array is referenced 
in Perl?
A reference to a nonexistent element in Perl yields undef, but no error is reported.


Problem Sets:

6.Explain all of the differences between Ada’s subtypes and derived types.
A derived type is a new type that is based on some previously defined type with which it is not equivalent, although it may have identical structure. Derived types inherit all the properties of their parent types. Consider the following example:
type Celsius is new Float;
type Fahrenheit is new Float;

The types of variables of these two derived types are not equivalent, although their structures are identical. Furthermore, variables of both types are not type equivalent with any other floating-point type. Derived types can also include range constraints on the parent type, while still inheriting all of the parent’s operations.

On the other hand Ada subtype is a possibly range-constrained version of an existing type. A subtype is type equivalent with its parent type. Ada’s derived types are very different from Ada’s subrange types.
For example, consider the following type declarations:
type Derived_Small_Int is new Integer range 1..100; subtype Subrange_Small_Int is Integer range 1..100;
Variables of both types, Derived_Small_Int and Subrange_Small_Int, have the same range of legal values and both inherit the operations of Integer.

However, variables of type Derived_Small_Int are not compatible with any Integer type. On the other hand, variables of type Subrange_Small_Int are compatible with variables and constants of Integer type and any subtype of Integer.

7. What significant justification is there for the -> operator in C and C++?
The justification of –> operator in c and c++ is writability. In c ++ there are 2 ways a pointer record can be used to reference a field in that record. 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 Java they can include fields, constructors, and methods. The possible values of an enumeration are the only possible instances of the class. All enumeration types inherit toString, as well as a few other methods. An array of the instances of an enumeration type can be fetched with the static method values. The internal numeric value of an enumeration variable can be fetched with the ordinal method. No expression of any other type can be assigned to an enumeration variable. Also, an enumeration variable is never coerced to any other type.

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?
The advantage: Unconstrained variant records in Ada allow the values of their variants to change types during execution. 

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

Assignment #5

Source:

Concepts of Programming Languages, Robert W. Sebesta.

Chapter 5: Names, Bindings, and Scopes, page 235-240

By:
Name : Helena Natanael
NIM  : 1801380333

---

Review Question:

6. What is the l-value of a variable? What is the r-value?
The l-value of variable is the address of a variable because the address is required when the name of a variable appears in the left side of an assignment. 
The r-value of variable is a variable’s value because it 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. While the time at which a binding takes place is called binding time.

8. After language design and implementation [what are the four times bindings can take place in a program?]
The compile time binding, the load time binding, the link time binding, the run time binding.

9. Define static binding and dynamic binding.
A static binding is when the binding occurs before run time begins and remains unchanged throughout program execution. If the binding first occurs during run time or can change in the course of program execution, it is called dynamic binding.

10. What are the advantages and disadvantages of implicit declarations?
The advantage of implicit declarations is that simple in naming conventions. In this case, the compiler or interpreter binds a variable to a type based on the syntactic form of the variable’s name. While the disadvantage of implicit declarations is it can be detrimental to reliability because they prevent the compilation process from detecting some typographical and programmer errors.


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

ii. sub2
sub2: sub1

iii. sub3
sub3: main

b. Repeat part a, but assume dynamic scoping.
i. sub1
sub1: sub1
ii. sub2
sub2: sub1
iii. sub3
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 scoping rule = 5
dynamic scoping rule = 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, assuming
static scoping is used.

Variable                       Where Declared
In Sub1:
a                                             Sub1
y                                             Sub1
z                                             Sub1
x                                             Main
In Sub2:
a                                             Sub2
b                                             Sub2
z                                             Sub2
y                                             Sub1
x                                             Main
In 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, assuming
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 variable,
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

Assignment #4

Source:

Concepts of Programming Languages, Robert W. Sebesta.

Chapter 4: Lexical and Syntax Analysis, page 199-201

By:
Name : Helena Natanael
NIM  : 1801380333

---

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

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 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, whether it's syntactically correct or not, and if an error is found, the analyzer must create a diagnostic message. However, the syntax analyzer must create an error list because it's possible to find many errors during a single analysis of the input program. So when it finds an error, it saves the diagnostic message and go on checking. If it is not done well, error recovery may create more errors, or at least more error messages. 

Second, it has 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 difference is in the making of parsers. 

Top-down: the tree is built from the root downward to the leaves
Bottom-up: the tree is built from the leaves upward to the root.

10. Describe the parsing problem for a top-down parser.
I usually use the bottom-up parsers, and I rarely use top-down parser, because it takes more concern and focus to make it correctly, there's bigger chance of bad parsing or skipped leaves in top-down parser. It also would be confusing if it comes to bad grammar/ambiguous grammar.


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
S → AbB → aBBbB → aAcBbB → aAccBbbB → aAcccbbc

Phrases: aAcccbbc, aAcccb, Ac, ccb, c, c.

Simple Phrases: Ac, c, c

Handle: Ac

b. AbcaBccb
S → AbB → AbcBb → AbcAcb → AbcaBBcb → AbcaBccb

Phrases: AbcaBccb, caBccb, aBcc, aBc, c

Simple Phrases: c

Handle: c

c. baBcBbbc
S →  bAc → baBBc → baBcBbc → 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.

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.
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> ‘}’

Assignment #3

Source:

Concepts of Programming Languages, Robert W. Sebesta.

Chapter 3: Describing Syntax and Semantics, page 162-164

By:
Name : Helena Natanael
NIM  : 1801380333

---

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. This left recursion specifies left associativity. 

7. What three extensions are common to most EBNFs?
Extended Backus-Naur Forms has three common extensions:

1. The first extension denotes an optional part of an right hand side (RHS), which is delimited by brackets. 2. 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. 
3. 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?
An attribute grammar consists of a grammar, a set of attributes, a set of attribute computation functions, and a set of predicates, which together describe static semantics rules. So predicates is a part of attribute grammar which is without the predicates, there would be no attribute grammar.

10. What is the difference between a synthesized and an inherited attribute
The difference between Synthesized and Inherited attribute is :
Synthesized attributes are used to pass semantic information up a parse tree, in the other hand inherited attributes pass semantic information down and across a tree.


Problem Set:

6. Using the grammar in Example 3.2, show a parse tree and a leftmost derivation for each of the following statements:

Grammar in Example 3.2:
<assign> → <id> = <expr>
<id>       → A | B | C
<expr>   → <id> + <expr>
                   | <id> * <expr>
                   | ( <expr>

a. A = A * (B + (C * A))
Parse Tree:

Leftmost Derivation:
<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)
Parse Tree:

Leftmost Derivation:
<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))
Parse Tree:

Leftmost Derivation:
<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:

Grammar in Example 3.4:
<assign> → <id> = <expr>
<id>       → A | B | C
<expr>   → <expr> + <term>
                    | <term>
<term>   → <term> * <factor>
                    | <factor>
<factor> → ( <expr> )
                    | <id>

 a. A = ( A + B ) * C
Parse Tree:

Leftmost Derivation:
<assign> → <id> = <expr>
               → A = <expr>
               → A = <term>
               → A = <term> * <term>  
               → A = <factor> * <term>
               → 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 + B ) * <term>    
               → A = ( A + B ) * <factor> 
               → A = ( A + B ) * <id> 
               → A = ( A + B ) * C


b. A = B + C + A
Parse Tree:

Leftmost Derivation:
<assign> → <id> = <expr>
               → A = <expr>
               → A = <expr> + <term>
               → A = <term> + <term>
               → A = <factor> + <term>
               → A = <id> + <term>
               → A = B + <term>
               → A = B + <term> + <factor>
               → A = B + <factor> + <factor>
               → A = B + <id> + <factor>
               → A = B + C + <factor>             
               → A = B + C + <id>
               → A = B + C + A


c. A = A * (B + C)
Parse Tree:

Leftmost Derivation:
<assign> → <id> = <expr>
               → A = <expr>
               → A = <term> 
               → A = <factor> * <term> 
               → 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))
Parse Tree:

Leftmost Derivation:
<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 ) )

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

The grammar is ambiguous because there's 2 different parse trees can be made from grammar above.

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

It means all sentences consisting of one or more a, then a is followed by one or more b and then also followed by one or more c.