解答例

課題1

_images/parse-tree-quiz.png

課題2

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

課題3

この文法は曖昧なので、次の2通りの構造のどちらであるか、これだけでは決められない。

_images/dangling-else-1.png
_images/dangling-else-2.png

課題4

曖昧であることを示すためには二種類の構文解析が可能であるような文を見つければ良い。例えば AAA はそのような文である。

_images/ambiguous.png

課題5

厳密に言うと、変数宣言と型宣言は同じではない（型がない変数宣言、宣言せずに型推論で型が決まる場合などがある）。また、変数宣言で型以外の属性を指定することもある。

変数の名前を宣言することについては：

宣言なし

宣言あり

読み書き

書きやすい

読みやすい

コードは

短い

長い

スペルミスの発見は

しにくい

しやすい

変数宣言に型(e.g. int, double)、スコープ(e.g. global, local)、アクセス修飾子(e.g. public, private)などを含める場合は：

  • コンパイラがそれらの情報を利用してバグを発見したり、効率の良い機械語を生成したりできる。

  • プログラミングの柔軟性は少なくなる。

課題6

静的スコープでは5、動的スコープでは10。

課題7

AとBというデータがお互いに参照している場合、外部からの参照が無くなればAとBの両方が不要になるが、参照カウンタは1のままである。

課題8

  1. 変数に記憶されているデータA, Bと、Bから参照されているデータCがあるとする。

  2. GCにより、Aからたどれるデータにマークが付けられる。

  3. プログラムの実行によりA, Bの内容が変更され、AがCを参照し、Bは何も参照しなくなる。

  4. GCにより、Bからたどれるデータにマークが付けられる。

  5. そうすると、CはAから参照されているので必要なデータだが、GCでマークが付けられないので捨てられる。

課題9

C言語のライブラリ関数 strtok は、文字列を区切り文字で区切ってトークンに分解する。最初に呼び出す時は、第1引数に文字列を与え、先頭のトークンが返ってくる。2回目以降の呼び出しでは、第1引数に NULL を与え、呼び出すたびに次のトークンが順に返ってくる。これは、 strtok が static local 変数で文字列をどこまで分解したかを覚えているからである。

  • ライブラリ関数なので、グローバル変数は使うべきではない。（ユーザのアプリケーションで使っている名前とぶつかる可能性がある。）

  • 1回の呼び出しですべてのトークンを返そうとすると、不定個の文字列の配列が必要となるが、ライブラリ関数で記憶領域を割り当てるべきではない。（ユーザのアプリケーションでどのようなメモリ管理をしているかわからない。）

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

課題10

  • Cの利点

    • 言語仕様が小さくなるので、処理系が作り易い。

    • 整数値で0だけを特別扱いすること（例えば文字列の終端）が多いので、そのような場合は短いプログラムが書ける。

      while (*q++ = *p++);  /* pからqへの文字列コピー */

  • Javaの利点

    • プログラムを読む時にわかりやすい。

    • 整数と真偽値を間違えた場合に型検査で発見できる。

    • 型情報を利用して最適化ができる可能性がある。

課題11

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

課題12

  1. 【a#b】$c

  2. a!【b?c】

  3. 【a#b】!【c$d】

  4. 【a#b】!【c?d】

  5. 【【a#b】$c】!【d?e】

課題13

短絡評価の場合、後半部分に副作用があると、前半部分の値によって副作用が起きたり起きなかったりするので、それを避けるために短絡評価をしない演算子が用意されている。副作用がない場合は、短絡評価の方が効率が良い。