試験解答例

1.
  1. コンパイラー(編訳系)によって機械語に翻訳した後に直接実行する形態
    一旦機械語に翻訳された後は実行速度が速い。
  2. インタープリターによって逐次解釈しながら実行する形態。
    逐次解釈のための時間が余分に必要であるが、 コンパイルにかける時間が必要無いため、プログラムの変更や デバッグが容易である。

2.

  1. 最右導出
  2. EEAA ⇒ aASb ⇒ aASAb ⇒ aAb ⇒ aaASbb ⇒ aabb
3.
  1. まず、関数呼び出しが終了したとき呼び出しをしたところへ正しく戻ることができる 必要がある。特に、多重に呼び出されている場合でも戻ることができるように、 スタックなどの LIFO バッファに戻り番地が入っている必要がある。
  2. 次に、引数の結合方式で、引数の番地を渡す「参照呼び出し」の場合には、 多重に呼び出された関数によって、その値が予測不可能な形で書き換えられる 可能性があるので、「値呼び出し」による引数結合を行う必要がある。
  3. さらに、関数内部で使われる変数が、多重に呼び出される計算の中で 書き換えられることがないように、関数の呼び出し毎に変数のための記憶領域が 確保される「動的割り当て」ができることも必要である。

4.
スタック 素語の列 動作
$0 (i+i)*i$ shift
$0(4 i+i)*i$ shift
$0(4i5 +i)*i$ reduce 6
$0(4F3 +i)*i$ reduce 4
$0(4T2 +i)*i$ reduce 2
$0(4E8 +i)*i$ shift
$0(4E8+6 i)*i$ shift
$0(4E8+6i5 )*i$ reduce 6
$0(4E8+6F3 )*i$ reduce 4
$0(4E8+6T9 )*i$ reduce 1
$0(4E8 )*i$ shift
$0(4E8)11 *i$ reduce 5
$0F3 *i$ reduce 4
$0T2 *i$ shift
$0T2*7 i$ shift
$0T2*7i5 $ reduce 6
$0T2*7F10 $ reduce 3
$0T2 $ reduce 2
$0E1 $ accept


問題