******
Answer
******
   
    .. _ex1-answer:

    .. admonition:: Exercise 1
       :class: exercise

       .. figure:: parse-tree-quiz.png
	  :scale: 70%

    .. _ex2-answer:

    .. admonition:: Exercise 2
       :class: exercise

       .. code-block:: bnf

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

    .. _ex3-answer:

    .. admonition:: Exercise 3
       :class: exercise

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

       .. figure:: dangling-else-1.png
	  :scale: 60%

       .. figure:: dangling-else-2.png
	  :scale: 60%

    .. _ex4-answer:

    .. admonition:: Exercise 4
       :class: exercise

       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.

       .. figure:: ambiguous.png
	  :scale: 70%

    .. _ex5-answer:

    .. admonition:: Exercise 5
       :class: exercise

       .. list-table::
	  :header-rows: 1

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

    .. _ex6-answer:

    .. admonition:: Exercise 6
       :class: exercise

       Static scoping: 5

       Dynamic scoping: 10

    .. _ex7-answer:

    .. admonition:: Exercise 7
       :class: exercise

       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.

    .. _ex8-answer:

    .. admonition:: Exercise 8
       :class: exercise

       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.

    .. _ex9-answer:

    .. admonition:: Exercise 9
       :class: exercise

       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) <http://www.opensource.apple.com/source/Libc/Libc-167/string.subproj/strtok.c>`_ , `sample usage (TutorialsPoint) <http://www.tutorialspoint.com/c_standard_library/c_function_strtok.htm>`_

    .. _ex10-answer:

    .. admonition:: Exercise 10
       :class: exercise

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

	    .. code-block:: c

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

    .. _ex11-answer:

    .. admonition:: Exercise 11
       :class: exercise

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

    .. _ex13-answer:

    .. admonition:: Exercise 13
       :class: exercise

       1. ``(a#b)$c``
       2. ``a!(b?c)``
       3. ``(a#b)!(c$d)``
       4. ``(a#b)!(c?d)``
       5. ``((a#b)$c)!(d?e)``

    .. _ex14-answer:

    .. admonition:: Exercise 14
       :class: exercise

       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.

    .. _ex15-answer:

    .. admonition:: Exercise 15
       :class: exercise

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

    .. _ex16-answer:

    .. admonition:: Exercise 16
       :class: exercise

       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}

    .. _ex17-answer:

    .. admonition:: Exercise 17
       :class: exercise

       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.

    .. _ex18-answer:

    .. admonition:: Exercise 18
       :class: exercise

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

.. comment

    .. _ex19-answer:

    .. admonition:: Exercise 19
       :class: exercise

       Mathematical induction on the number of philosophers *n*.

       It is ovbious when *n=1*.

       Assume deadlock never occurs when *n=k*.  Let *p(1), p(2), ..., p(k+1)* be philosphers sitting in this order, left to right.  Since *p(k+1)* can always take his right folk, he can eat if only he can get his left folk.  Using the induction hypothesis, there is a moment *p(k)* put his right folk after eating, when *p(k+1)* can take that folk.

.. comment

    .. _ex20-answer:

    .. admonition:: Exercise 20
       :class: exercise

       モニタ

	  * ``synchronized`` 文
	  * メソッドの ``synchronized`` 修飾子

       モニタの中で寝る

	  * ``Object.wait`` メソッドの呼び出し

       モニタの中で寝ているタスクを起こす

	  * ``Object.notify`` メソッドの呼び出し
	  * ``Object.notifyAll`` メソッドの呼び出し