## April 7, 2013

### KBP chapter 7

Review Questions

Rickvian Aldi / 02PCT / 1601253441
Assignment By Mr. Tri Djoko Wahjono

1. Define operator precedence and operator associativity.

-The operator precedence rules for expression evaluation partially define
the order in which the operators of different precedence levels are evaluated.

-An operator can have either left or right associativity, meaning that when
there are two adjacent operators with the same precedence, the left operator is
evaluated first or the nright operator is evaluated first, respectively.

2. What is a ternary operator?

-ternary, meaning it has three operands.

3. What is a prefix operator?

-means they precede their operands.

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

10. What is a conditional expression?

-is a if-then-else that has more convinient form :

expression_1 ? expression_2 : expression_3
where expression_1 is interpreted as a Boolean expression.

If expression_1 evaluates to true, the value of the whole expression is the
value of expression_2;
otherwise, it is the value of expression_3.

13. In JavaScript, what is the difference between == and ===?

== is equality relational operator
=== is similiar to == but prevent their operands from being coerced.

14. What is a mixed-mode expression?

-language that allow expressions is whether an operator can have operands of
different types.

15. What is referential transparency?

-A program has the property of referential transparency if any two
expressions in the program that have the same value can be substituted for one
another anywhere in the program, without affecting the action of the program.

20. How does C support relational and Boolean expressions?
relational :
-for example, inequality, the C-based languages use !=

boolean :
-Highest postfix ++, --
unary +, -, prefix ++, --, !
*, /, %
binary +, -
<, >, <=, >=
=, !=
&&
Lowest ||

21. What is the purpose of a compound assignment operator?

-A compound assignment operator is a shorthand method of specifying a
commonly needed form of assignment. The form of assignment that can be
abbreviated with this technique has the destination variable also appearing as
the first operand in the expression on the right side.

28. What is a cast?

-In the C-based languages, explicit type conversions are called casts.

Problem Set

1. When might you want the compiler to ignore type differences in an
expression?

-When it's overflow or underflow.

3. Do you think the elimination of overloaded operators in your favorite
language would be beneficial? Why or why not?

-no.
overloaded operators can give more advantages, if it's eliminated, it will only
have one function.
the benefit in the following will be no more exist, which harden the coding
process.

For example, if + and * are overloaded for a matrix abstract data type and A,
B,
C, and D are variables of that type, then

A * B + C * D

can be used instead of

MatrixAdd(MatrixMult(A, B), MatrixMult(C, D))

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 subexpressions 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
b. a * (b - 1) / c mod d
c. (a - b) / c & (d * e / a - 3)
d. -a or c = d and e
e. a > b xor c or d <= 17
f. -a + b

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

21. Why does Java specify that operands in expressions are all evaluated in
left-to-right order?

-because left-to-right order is a common used.

22. Explain how the coercion rules of a language affect its error detection

-As a simple illustration of the problem, consider the following Java code:

int a;
float b, c, d;
. . .
d = b * a;

Assume that the second operand of the multiplication operator was supposed
to be c, but because of a keying error it was typed as a. Because mixed-mode
expressions are legal in Java, the compiler would not detect this as an error.
It would simply insert code to coerce the value of the int operand, a, to
float. If mixed-mode expressions were not legal in Java, this keying error
would have been detected by the compiler as a type error.

### KBP chapter 6

Rickvian Aldi / 02PCT / 1601253441
Assignment By Mr. Tri Djoko Wahjono

Review Questions

1. What is a descriptor?

-A descriptor is the collection of the attributes of a variable. In
an implementation, a descriptor is an area of memory that stores the attributes
of a variable.

2. What are the advantages and disadvantages of decimal data types?

-Decimal types have the advantage of being able to precisely store decimal
values, at least those within a restricted range, which cannot be done
with floating-point. For example, the number 0.1 (in decimal) can be exactly
represented in a decimal type, but not in a floating-point type,

-The disadvantages of decimal types are that the range of values
is restricted because no exponents are allowed, and their representation in
memory is mildly wasteful.
Decimal types are stored very much like character strings, using binary
codes for the decimal digits. These representations are called binary coded
decimal (BCD). In some cases, they are stored one digit per byte, but in

others, they are packed two digits per byte. Either way, they take more storage

than binary representations. It takes at least four bits to code a decimal

digit. Therefore, to store a six-digit coded decimal number requires 24 bits of

memory. However, it takes only 20 bits to store the same number in binary.

3. What are the design issues for character string types?

-The two most important design issues that are specific to character string

types
are the following:
• Should strings be simply a special kind of character array or a primitive

type?
• Should strings have static or dynamic length?

4. Describe the three string length options.

-First,the length can be static and set when the string is created. Such a

string is called a static length string.

-The second option is to allow strings to have varying length up to a
declared and fixed maximum set by the variable’s definition, as exemplified
by the strings in C and the C-style strings of C++.

-The third option is to allow strings to have varying length with no maximum,
as in JavaScript, Perl, and the standard C++ library. These are called
dynamic length strings. This option requires the overhead of dynamic storage
allocation and deallocation but provides maximum flexibility.

5. Define ordinal, enumeration, and subrange types.

-An ordinal type is one in which the range of possible values can be easily
associated with the set of positive integers. In Java, for example, the

primitive ordinal types are integer, char, and boolean.
There are two user-defined
ordinal types that have been supported by programming languages: enumeration
and subrange.

-An enumeration type is one in which all of the possible values, which are
named constants, are provided, or enumerated, in the definition. Enumeration
types provide a way of defining and grouping collections of named constants,
which are called enumeration constants.

-A subrange type is a contiguous subsequence of an ordinal type. For example,
12..14 is a subrange of integer type.

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

-Readability is enhanced very directly: Named values are easily recognized,
whereas coded values are not.
In the area of reliability, the enumeration types of Ada, C#, F#, and Java
5.0 provide two advantages: (1) No arithmetic operations are legal on

enumeration types; this prevents adding days of the week, for example, and
(2) second, no enumeration variable can be assigned a value outside its defined

range.4 If the colors enumeration type has 10 enumeration constants and uses

0..9 as its internal values, no number greater than 9 can be assigned to a

colors type variable.

12. What languages support negative subscripts?

-Ruby and Lua.

15. What is an aggregate constant?

-consider the following:
List : array (1..5) of Integer := (1, 3, 5, 7, 9);
Bunch : array (1..5) of Integer := (1 => 17, 3 => 34,
others => 0);
In the first statement, all the elements of the array List have initializing

values, which are assigned to the array element locations in the order in which

they appear. In the second, the first and third array elements are initialized

using direct assignment, and the others clause is used to initialize the

remaining elements. As with Fortran, these parenthesized lists of values are

called aggregate values.

17. Define row major order and column major order.

-In row major order, the
elements of the array that have as their first subscript the lower bound value

of that subscript are stored first, followed by the elements of the second

value of the first subscript, and so forth. If the array is a matrix, it is

stored by rows.
For example, if the matrix had the values

3 4 7
6 2 5
1 3 8

it would be stored in row major order as
3, 4, 7, 6, 2, 5, 1, 3, 8

-In column major order, the elements of an array that have as their last

subscript the lower bound value of that subscript are stored first, followed by

the elements of the second value of the last subscript, and so forth. If the

array is a matrix, it is stored by columns.
If the example matrix were stored in column major order, it would have the

following order in memory:
3, 6, 1, 4, 2, 3, 7, 5, 8

21. What is the purpose of level numbers in COBOL records?

-indicate by their relative values the hierarchical structure of the record.

Any line that is followed by a line with a higher-level number is itself a

record.

23. What is the primary difference between a record and a tuple?

-Tuples are similar to records, but do not have names for their constituent
parts.

24. Are the tuples of Python mutable?

-Python’s tuples are closely related to its lists, except that tuples are
immutable. A tuple is created by assigning a tuple literal, as in the following
example:

myTuple = (3, 5.8, 'apple')

Notice that the elements of a tuple need not be of the same type.
The elements of a tuple can be referenced with indexing in brackets, as in
the following:

myTuple[1]

This references the first element of the tuple, because tuple indexing begins

at 1.

26. In what primarily imperative language do lists serve as arrays?

-Python.

31. Define union, free union, and discriminated union.

-A union
is a type whose variables may store different type values at different
times during program execution.

-free unions
are unions that allowed complete freedom from type checking in their use.

-Type checking of unions requires that each union construct include a type
indicator. Such indicator is called tag or discriminant, and a union with
a discriminant is called a discriminated union.

36. What are the two common problems with pointers?

-Pointers have some inherent dangers: Dangling pointers are difficult
to avoid, and memory leakage can occur.

44. Define type error.

-A type error is the application of an operator to an operand of an

inappropriate type.
For example, in the original version of C, if an int value was passed to a

function that expected a float value, a type error would occur
(because compilers for that language did not check the types of parameters).

45. Define strongly typed.

-A programming language is strongly typed if type errors are always
detected.

46. Why is Java not strongly typed?

-expressions are strongly typed in Java.
However,
an arithmetic operator with one floating-point operand and one integer operand
is legal. The value of the integer operand is coerced to floating-point, and
a floating-point operation takes place. This is what is usually intended by the
programmer. However, the coercion also results in a loss of one of the benefits
of strong typing—error detection.

50. What is name type equivalence?

-Type equivalence is a strict form
of type compatibility—compatibility without coercion.

51. What is structure type equivalence?

-Structure type equivalence
means that two variables have equivalent types if their types have identical
structures.

PROBLEM SET

1. What are the arguments for and against representing Boolean values as
single bits in memory?

A Boolean value could be represented by a single bit, but because a single
bit of memory cannot be accessed efficiently on many machines, they are often
stored in the smallest efficiently addressable cell of memory, typically a

byte.

2. How does a decimal value waste memory space?

-Their representation in memory is mildly wasteful, for reasons discussed in

the following paragraph.
-Decimal types are stored very much like character strings, using binary
codes for the decimal digits. These representations are called binary coded
decimal (BCD). In some cases, they are stored one digit per byte, but in

others,
they are packed two digits per byte. Either way, they take more storage than
binary representations. It takes at least four bits to code a decimal digit.

Therefore,
to store a six-digit coded decimal number requires 24 bits of memory.
However, it takes only 20 bits to store the same number in binary.

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

-In C and C++, there are two ways a pointer to a record can be used to

reference a field in that record. If a pointer variable p points to a record

with a field named age, (*p).age can be used to refer to that field. The

operator ->, when used between a pointer to a record and a field of that

record, comfbines dereferencing and field reference. For example, the

expression p -> age is equivalent to (*p).age. In Ada, p.age
can be used, because such uses of pointers are implicitly dereferenced.

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?

Unconstrained variant records in Ada allow the values of their variants to

change types during execution.

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

13. Analyze and write a comparison of using C++ pointers and Java reference
variables to refer to fixed heap-dynamic variables. Use safety and convenience
as the primary considerations in the comparison.

-In c and C++ pointer can be use the same way as addresses. This design offer

no solutions to the dangling pointer or lost heap-dynamic variable problems.

-Reference types, such as those in Java and C#, provide heap management
without the dangers of pointers.

so its clear that Java has more safety for the heap-dynamic variables.

21. In what way is static type checking better than dynamic type checking?

It allows many type errors to be caught early in the development cycle. Static

type checkers evaluate only the type information that can be determined at

compile time, but are able to verify that the checked conditions hold for all

possible executions of the program, which eliminates the need to repeat type

checks every time the program is executed

### KBP chapter 5

Rickvian Aldi / 02PCT / 1601253441
Assignment By Mr. Tri Djoko Wahjono

Review questions

3. In what way are reserved words better than keywords?
- As a language design choice, reserved words are better
than keywords because the ability to redefine keywords can be confusing.
These statements declare the program variable Real to be of Integer type
and the variable Integer to be of Real type.3 In addition to the strange
appearance of these declaration statements, the appearance of Real and Integer
as variable names elsewhere in the program could be misleading to program

4. What is an alias?

-When more than one variable name can be used to access the same memory location, the variables are called aliases.

5. Which category of C++ reference variables is always aliases?

-Two pointer variables are aliases when they point to the same memory
location. The same is true for reference variables. This kind of aliasing is simply
a side effect of the nature of pointers and references. When a C++ pointer is set
to point at a named variable, the pointer, when dereferenced, and the variable’s
name are aliases.

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

-A variable’s value is sometimes called its r-value
-To access the r-value, the l-value must be determined first.

9. Define static binding and dynamic binding.

-An explicit declaration is a statement in a program that lists variable names
and specifies that they are a particular type. An implicit declaration is a means
of associating variables with types through default conventions, rather than
declaration statements. In this case, the first appearance of a variable name in a
program constitutes its implicit declaration. Both explicit and implicit declarations
create static bindings to types.

-With dynamic type binding, the type of a variable is not specified by a declaration
statement, nor can it be determined by the spelling of its name. Instead,
the variable is bound to a type when it is assigned a value in an assignment statement.

13. Define lifetime, scope, static scope, and dynamic scope.

-The lifetime of a variable is the time during which the variable is bound
to a specific memory location.

-The scope of a variable is the range of statements in which the variable is visible. A variable
is visible in a statement if it can be referenced in that statement.

-the method of binding names to nonlocal variables called static scoping.

-Dynamic scoping is based on the calling sequence of subprograms, not
on their spatial relationship to each other. Thus, the scope can be determined
only at run time.

15. What is the general problem with static scoping?

-First, in most cases it allows
more access to both variables and subprograms than is necessary. It is simply
too crude a tool for concisely specifying such restrictions. Second, and perhaps
more important, is a problem related to program evolution. Software is highly
dynamic—programs that are used regularly continually change. These changes
often result in restructuring, thereby destroying the initial structure that
restricted variable and subprogram access.
-Designers are encouraged to use far more globals than are necessary.

18. What is a block?

-allows a section of code to have its own local variables whose scope is minimized. Such variables
are typically stack dynamic, so their storage is allocated when the section
is entered and deallocated when the section is exited. Such a section of code
is called a block.

19. What is the purpose of the let constructs in functional languages?

-These constructs have two parts:
-The first of which is to bind names to values, usually specified as
expressions.
-The second part is an expression that uses the names defined in the
first part. Programs in functional languages are comprised of expressions, rather
than statements. Therefore, the final part of a let construct is an expression, rather than a statement.

23. What are the advantages of named constants?

-named constants are useful to increase readbility of program
for example, by using name pi instead of the constant 3.14159265

Problem Sets

1. Which of the following identifier forms is most readable? Support your decision.
SumOfSales
sum_of_sales
SUMOFSALES

sum_of_sales
seperated by underscore will give more space, also seperate each wort, so it will be more readable than those are not seperated.

2.Some programming languages are typeless. What are the obvious advantages
and disadvantages of having no types in a language?

-advantages : the programmer allowed to code programs quickly without worrying about data types
-disadvantages : it is slow for parser that has to keep track on whats on the variable.

5. Describe a situation when a history-sensitive variable in a subprogram is
useful.

-Globally accessible variables are often used throughout the execution
of a program, thus making it necessary to have them bound to the same
storage during that execution. Sometimes it is convenient to have subprograms
that are history sensitive.

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.

1 : a,b,c <definition 1> ; b,c,d <definiton 2>
2 : a,b,c <definition 1> ; b,c,d <definiton 2> ; c,d,e <definition 3>
3 : a,b,c <definition 1> ; b,c,d <definiton 2>
4 : a,b,c <definition 1>

### KBP chapter 4

Rickvian Aldi / 02PCT / 1601253441
Assignment By Mr. Tri Djoko Wahjono

Review questions

2.Explain the three reasons why lexical analysis is separated from syntax analysis.

1. Simplicity—Techniques for lexical analysis are less complex than those
required for syntax analysis, so the lexical-analysis process can be simpler
if it is separate. Also, removing the low-level details of lexical analysis
from the syntax analyzer makes the syntax analyzer both smaller and
less complex.
2. Efficiency—Although it pays to optimize the lexical analyzer, because
lexical analysis requires a significant portion of total compilation time,
it is not fruitful to optimize the syntax analyzer. Separation facilitates
this selective optimization.
3. Portability—Because the lexical analyzer reads input program files
and often includes buffering of that input, it is somewhat platform
dependent. However, the syntax analyzer can be platform independent.
It is always good to isolate machine-dependent parts of any software
system.

3.define lexeme and token.

-Formal descriptions of the syntax of programming languages, for simplicity’s
sake, often do not include descriptions of the lowest-level syntactic
units. These small units are called lexemes.

-token of a language is a category of its lexemes. For example, an identifier is a token
that can have lexemes, or instances, such as sum and total. In some cases, a
token has only a single possible lexeme. Each lexeme group is represented by a name, or token.

Consider the following
Java statement:

index = 2 * count + 17;
The lexemes and tokens of this statement are
Lexemes Tokens
index identifier
= equal_sign
2 int_literal
* mult_op
count identifier
+ plus_op
17 int_literal
; semicolon

4. what are the primary task of a lexical analyzer?

-A lexical analyzer is essentially a pattern matcher. A pattern matcher attempts to
find a substring of a given string of characters that matches a given character pattern.
Pattern matching is a traditional part of computing.

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?

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

13.Why are named constants used, rather than numbers, for token codes?

-for the sake of readability of lexical and syntax analyzers.

14.Describe how a recursive-descent parsing subprogram is written for a rule with a single RHS.

-A recursive-descent subprogram for a rule with a single RHS is relatively
simple. For each terminal symbol in the RHS, that terminal symbol is compared
with nextToken. If they do not match, it is a syntax error. If they match,
the lexical analyzer is called to get the next input token. For each nonterminal, the parsing subprogram for that nonterminal is called.

15.What is the FIRST set for a given grammar and sentential form?

FIRST( ) = {a => * a } (If => * , is in FIRST( ))
in which =>* means 0 or more derivation steps.

18.What is left factoring?

-Left factoring is the action taken when a grammar leads backtracking while making parsing/syntax tree

Let us have a grammar:-
A->bcW | bcE
W->x
E->q

Now lets have a look on the production A->bcW | bcE, here 'bc' is repeating.
If we want to parse a string "bcq", then firstly we have two choices - either choose A->bcW or A->bcE. Since both have the same probability, we choose A->bcW. Then when we are finished with "bc" and turn to parse "_ _ q". After this, we have to backtrack because this production is in "A->bcE".

This shows the problem with such type of problem. Now to overcome this problem we have a concept of Left factoring.
In this we take common symbols in a new non terminal. Lets have a look on how we can do it.
Above grammar after applying left factoring is

A->bcX
X->W | E
W->x
E->q

http://en.wikipedia.org/wiki/Left_factoring

Problem Set

(1)1. Perform the pairwise disjointness test for the following grammar rules.
a. A → aB | b | cBB
b. B → aB | bA | aBb
c. C→ aaA | b | caB

A -> aB | b | CBB

first(aB) = a

first(b) = b

first(CBB) = aaA = a

B -> aB | ba | aBb

first(aB) = a

first(ba) = b

first(aBb) = a

They are intersected & thus the rule fails the test.

C -> aaA | b | caB

first(aaA) = a

first(b) = b

first(caB) = c

are not intersected & thus the rule passes

(2)2. Perform the pairwise disjointness test for the following grammar rules.
a. S→ aSb | bAA
b. A → b{aB} | a
c. B → aB | a

S→ aSb | bAA

first(aSb) = a

first(bAA) = b

are not intersected, the rule passes

A → b{aB} | a

first(b{aB}) = b

first(a) = a

are not intersected, the rule passes

B → aB | a

first(aB) = a

first(a) = a

They are intersected the rule fails the test.

(3)3. Show a trace of the recursive descent parser given in Section 4.4.1 for
the string a + b * c.

Consider the following EBNF description of simple arithmetic expressions:
<expr> → <term> {(+ | -) <term>}
<term> → <factor> {(* | /) <factor>}
<factor> → id | int_constant | ( <expr> )

Next token is: 10 Next lexeme is a
Enter <expr>
Enter <term>
Enter <factor>

Next token is: 21 Next lexeme is +
Exit <factor>
Exit <term>

Next token is: 10 Next lexeme is b
Enter <term>
Enter <factor>

Next token is: 10 Next lexeme is *
Exit <factor>

Next token is: 26 Next lexeme is c
Enter<factor>

Next token is: -1 Next lexeme is EOF
Exit <term>
Exit <expr>

4. Show a trace of the recursive descent parser given in Section 4.4.1 for
the string a * (b + c).

Next token is: 10 Next lexeme is a
Enter <expr>
Enter <term>
Enter <factor>

Next token is: 21 Next lexeme is *
Exit <factor>

Next token is: 25 Next lexeme is (
Enter <factor>

Next token is: 10 Next lexeme is b
Enter <expr>
Enter <term>
Enter <factor>

Next token is: 21 Next lexeme is +
Exit <factor>

Next token is: 26 Next lexeme is c
Enter <factor>

Next token is: 26 Next lexeme is )
Exit <term>
Exit <expr>

Next token is: -1 Next lexeme is EOF
Exit <factor>
Exit <term>
Exit <expr>