Answer

Exercise 1

Exercise 2

<var> ::= A | B | C
<factor> ::= <var> | ( <expr> )
<term> ::= <factor> | <term> * <factor>
<expr> ::= <term> | <expr> + <term>

Exercise 3

The else part can be associated with both of two if statements, resulting the following two interpretation:

Exercise 4

In order to prove a certain grammar is ambiguous, we need a sentence which can be parsed in more than one way. In this case, AAA is such a sentence.

Exercise 5

	without declarations	with declarations
code length	short	long
misspelling	difficult to find	easy to find
maintainability	easy to write, hard to read	hard to write, easy to read

In many languages, variable declarations are accompanied by information such as types (e.g. int, double), scopes (e.g. global, local), and access modifiers (e.g. public, private):

• Compilers can take advantage of such information (e.g. type checking, memory allocation)

• Code is less flexible because more features are fixed at compile time.

Exercise 6

Static scoping: 5

Dynamic scoping: 10

Exercise 7

Suppose data A and B refer to each other. When all references from outside are lost, A and B are unreachable, but their reference counts are 1.

Exercise 8

1. Suppose there are two variables A and B, and B refers to a heap area C.

2. Data that can be followed from A are marked by GC.

3. Some part of the program is executed where the values of A and B are changed. Now A refers to C, and B refers to somewhere else.

4. Data that can be followed from B are marked by GC.

5. Though A refers to C, C is discarded since it is not marked.

Exercise 9

The library function strtok breaks a string into a series of tokens using some delimeters. On its first call we should provide a string for the first parameter, but we should give NULL when we retrieve the succeeding tokens. This is because strtok has a static local variable to store the string.

• It should not use global variables because it is a library function.

• It would requre memory allocation of an array of strings if you want to return all tokens at once.

cf. source code (Apple Open Source) , sample usage (TutorialsPoint)

Exercise 10

• Merits of C

  • The language specification can be kept small. In other words, it is easier to implement a compiler.

  • It is possible to write concise code if 0 has a special meaning (e.g. end of a character string, absence of data, etc.).

    while (*q++ = *p++);  /* copy a string from *p to *q */
    

• Merits of Java

  • The code may be more human-readable.

  • Some kind of bugs can be detected at the compile time. For example, it is a common mistake in C language to write if (x = 1) when we want to compare x and 1. In Java, such code makes a type mismatch error.

  • It may be possible to optimize code using type information (e.g. a boolean value consumes 1byte in the memory while an integer needs 4bytes).

Exercise 11

(a->b)->[a]->[b]

Exercise 13

1. (a#b)$c

2. a!(b?c)

3. (a#b)!(c$d)

4. (a#b)!(c?d)

5. ((a#b)$c)!(d?e)

Exercise 14

If the second argument has a side-effect, we may want to use the non-short-circuiting operators so that the side-effect will occur regardless of the value of the first argument.

Otherwise short-circuiting operators are more efficient.

Exercise 15

• Error corresponds to a severe incident, so it is difficult to recover by the user program.

• RuntimeException includes:

  • exceptions caused by mistakes of programmers (e.g. ArrayStoreException)

  • exceptions that have chances to occur at almost everywhere in the program, so it is too cumbersome to write handlers (e.g. ArithmeticException)

Exercise 16

1. x: 2, list: {1, 3, 5, 7, 9}

2. x: 2, list: {3, 1, 5, 7, 9}

3. x: 2, list: {3, 2, 1, 7, 9}

Exercise 17

Variable i is declared in the surrounding environment of function() { alert(i); };, being shared by all generated closures. The value of i is 11 after execution of the loop, hence every button shows number 11.

Note that if we used for (let i = 1; i <= 10; i++), it would work fine because the variable name i is bound to a newly created variable in each iteration.

Exercise 18

• Subclass may have new methods in addition to methods inherited from its superclass.

• Static type checking should guarantee that no type-related error will happen at run time.

The reason why A x = new B() is allowed

‘x has type A’ means we may call methods defined in class A for an object stored in x. If the object is actually an instance of class B, no error will happen at run time because the object inherits all methods of A.

The reason why B y = new A() is not allowed

‘y has type B’ means we may call methods defined in class B for an object stored in y. If the object is actually an instance of class A, an error will happen when we call a method defined in B but not A.