英語の用語 (24 点)

次の英語の用語の (カタカナはできるだけ少ない) 日本語訳と説明を書きなさい。

Concatenation operation: 連結演算; 二つの語や言語を連結する言語理論の演算 (演算子なし)

Context-free grammar: 文脈自由文法; 構文解析でよく使う文脈に依存しない言語の文法

Ambiguous grammar: 曖昧な文法; ある入力に対して複数の解析木を許す文法

Universal Turing machine: 万能チューリング機械; 可能な計算を何でもできるチューリング機械

Nondeterminism: 非決定性; 「分身」を許すオートマトンや機械の性質

Formal language: 形式言語; 言語理論で文法で定義し、オートマトンで受理する言語

Type equivalence: 型の等価; 定義の仕方がちょっと違っても型が同じとして扱われること

Symbol table: 名前表; 関数名、変数名などを管理する表

Recursive descent parsing: 再帰的下向き構文解析; 各非終端記号に関数を用意する解析方法

Virtual machine: 仮想計算機; 移植性向上などのための仮想的な計算機

Left Recursion: 左再起; 下向き構文解析で最左の非終端記号を繰返し展開し、無限の再帰

Derivation: 導出; 初期記号から書換規則を適応して形式言語の語を作り出す
 

関数呼び出し (4 点)

関数の呼び出しの関係でスタックに置くものを四つ述べなさい。

戻り番地、引数、戻り値、前の関数フレームのベースポインタ、使われるレジスターの値を退避する一時変数、ローカル変数

正規言語の表現の変換 (合計 36 点)

ある正規言語の文法：

S → 0S | 0C
B → C | 2S | 2
C → 1B | 2S

  
  
            S                 C
        
            [図省略]
        
            B                 F
        
        

      [図省略]
      
      
      
      
    

構文木と解析木 (30 点)

price = unitp * items * (1+tax); の構文木と解析木を書きなさい。明記されてない情報 (例: 文法の非終端記号の名前) は適切に補ってください。

     statement
         |
         =
        / \
   price   *
         /   \
       *       +
      / \     / \
 unitp  items 1  tax
      

          statement              (@ から続く)
          /        \              factor
      assignment    ;           /    |   \
     /     |    \              (    exp   )
   var     =    exp                / | \
    |             \             exp  +  term
  price          term            |        |
                /  |  \        term    factor
            term   *   (@)       |        |
           / |  \             factor     var
       term  *  factor           |        |
        |          |            num      tax
      factor      var            |
        |          |             1
       var       items
        |
      unitp
      

構文木の役割や作成方法について専門用語を使いながら詳しく説明しなさい。 (6 点)

構文木は構文解析の段階で作成され、意味解析、最適化、コード生成の入力として使われる。 作成方法の一つは bison で YYSTYPE (属性文法の属性の型) を構文木のノートにして、書換規則の C 言語の部分で { $$ = new_node(PLUS, $1, $3); } などで構文木を上向きに部分木から作成する。 構文木は字句解析で除去されている空白などだけではなく、構文解析後不要になる括弧類や区切りの記号も含まれない。

解析木の役割について専門用語を使いながら詳しく説明しなさい。(6 点)

解析木の役割は実際の構文解析の時点ではなく、構文解析の方法の発案、分析 (途中結果をふくむ)、実装の時にある。 例えば再帰下向き構文解析では最左導出で解析木を上 (根) から作成し、いつもできるだけ一番左の枝を伸ばす。 逆に bison などで使われる上向き構文解析では解析木を下から枝葉を少しずつつないで、最右導出の逆順で解析木を作成。

コード生成と最適化 (合計 30 点)

超単純アセンブリ言語は次のような命令を持つ:

メモリのアドレスは変数名 (小文字) で表す。レジスタは R1, R2,... で表し、数の制限は無い。被演算子の順番は結果を一番左側に書く。

コード生成前の最適化 (9 点)

下記の左側の C 言語の断片を、C 言語のまま、コメントで明記した三つの種類の最適化を使って書き換えなさい。

while (s<60*60 && a==x) {
    s += 2 * a;
}

if (a==x) { /* 共通の式の繰り返しからの追い出し */
    while (s<3600 /* 定数畳込み */) {
        s += a + a; /* 演算の変更 */
    }
}

コード生成 (11 点)

右上のプログラム断片をそのまま (更なる最適化なしに) 単純アセンブリ言語で記述しなさい。
(前の問題で最適化できなかった分もコード生成しなさい。)

        LOAD   R1, a
        LOAD   R2, x
        SUB    R1, R1, R2
        JUMP!= R1, end   
next:   LOAD   R1, s
        CONST  R2, 3600
        SUB    R1, R1, R2
        JUMP>= R1, end

        LOAD   R1, s
        LOAD   R2, a
        ADD    R2, R2, R2
        ADD    R1, R1, R2
        STORE  s, R1
        JUMP   next
end:

コード生成後の最適化 (10 点)

上記の単純アセンブリ言語の断片を更に最適化しなさい。ヒント: 4つ3つのレジスタ、合計 12個13個の命令、ループそのものは 3個2個の命令で可能。ヒント: 少しでも最適化できたら書きなさい。

        LOAD   R1, a
        LOAD   R2, x
        SUB    R2, R1, R2
        JUMP!= R2, end
        ADD    R1, R1, R1
        LOAD   R2, s
        CONST  R3, 3600

        SUB    R2, R2, R3
        JUMP>= R2, end
next:   ADD    R2, R2, R1
        JUMP<  R2, next
        ADD    R2, R2, R3
        STORE  s, R2
end:

コンパイラの前後の段階 (合計 12点)

コンパイラ本体の前によく行われる処理を明記し、具体例で説明しなさい (5 点)。

コンパイラ本体の前はプリプロセッサを使うことが多いです。具体例として C 言語のプリプロセッサはヘッダファイルのインクルード (例: #include <stdio.h>)。
さらに、マクロの定義 (例: #define max(a,b) ((a)>(b)?(a):(b))) や条件付きコンパイル (#ifdef ...) などもできます。

コンパイラ本体の後に行われる処理を明記し、説明しなさい (7 点)。

コンパイラの後によく使われる段階はアセンブラ、リンカ、ローダである。
アセンブラは人間に見えるように書かれている機械語に近いアセンブリ (機械命令ごとに一行) を本当の機械語に直しているが、普通、コンパイラは直接本当の機械語を出力する。
リンカは複数のオブジェクトファイル (拡張子 .o 又は .obj) を一つの実行可能なファイル (拡張子 .exe など) に結びつきます。
ローダは実行可能ファイルをメモリにロードし、実行の準備を行います。

ゴミ集め (合計 9点)

ゴミ集めを採用しないプログラム言語を三つ列挙しなさい (2 点)。

C, C++, Objective C

ゴミ集めを採用するプログラム言語を三つ列挙しなさい (2 点)。

Ruby, Java, JavaScript

ゴミ集めの意義について説明しなさい (5 点)。

C 言語などで使われる動的メモリ管理は多くのバグの原因となっています。 しかも動的メモリ管理に関係するバグが非常に見つけにくくて、そのため IT業界で多くのコストが発生します。ゴミ集めにより、そのバグが無くなるので、 プログラミングの効率が上がって、コストが削減できます。

チューリング機械 (合計 30 点)

左のチューリング機械の遷移表に相当する遷移図を右側に書きなさい。(8 点)

[図省略]

上記の機械の ...␣1010011␣... に対する動作を示しなさい。(8 点)

  _ _ _ 1 0 1 0 0 1 1 _ _ _
                    ↑A

  _ _ _ 1 0 1 0 0 1 0 _ _ _
                  ↑C
  _ _ _ 1 0 1 0 0 1 0 _ _ _
                ↑C
  _ _ _ 1 0 1 0 1 1 0 _ _ _
              ↑B
  _ _ _ 1 0 1 0 1 1 0 _ _ _
            ↑B
  _ _ _ 1 0 0 0 1 1 0 _ _ _
          ↑C
  _ _ _ 1 1 0 0 1 1 0 _ _ _
        ↑B
  _ _ _ 0 1 0 0 1 1 0 _ _ _
      ↑C
  _ _ 1 0 1 0 0 1 1 0 _ _ _
    ↑D
  _ _ 1 0 1 0 0 1 1 0 _ _ _
      ↑E  

上記のチューリング機械は、テープ上の記号が 0, 1, ␣ に限定されているとき、どのような操作・計算をするか推測し、各状態の役割を含め説明しなさい。(6 点)

全体の動作は、0/1 をそれぞれ一枠左に移動させ、一番右に新たに 0 を追加することです。0/1 の列を二進数と解釈すると、計算は「掛ける 2」となっている。 状態 B は「0を左に待っていく」、C は「1を左に持っていく」という役割を持っています。D は終了の感知、E は終了状態。

正規言語 (族) は句構造言語 (族) の部分集合です。よって、有限オートマトンで可能な正規言語の受理の判定はチューリング機械でも可能です。 ある正規言語を受理する DFA をどうやってチューリング機械に変更できるか考えて、説明しなさい。(8 点)

入力は右からテープに書くことにする。DFA の状態を機械の状態にする。 書換は一切しない (現記号と新記号の欄が同じ)。移動方向は全部 L。 DFA の初期状態が機械の初期状態 (一番右の␣でない記号からスタート)。 DFA の受理状態で、␣の場合 R の移動で新設の機械の受理状態に遷移、終了。

文法の作成 (15 点)

次の言語のために、bison で使える形で文法の書換規則を書きなさい。{ } やその中の C 言語の部分は不要。非終端記号はできるだけ分かりやすいものにしてください。

言語は一つ以上の文からなる。文は式と終端記号 SEPARATOR からなる。式には被演算子を表す終端記号 NUMBER、終端記号 LEFTP と RIGHTP で表す左括弧と右括弧、そして直接終端記号として使える四つの二項演算子 △、▽、○、● が使える。△ と ▽ は左結合で、それらより優先度が高い ○ と ● は右結合である。

  statements: statement
            | statement statements
            ;
  statement : expression SEPARATOR
            ;
  expression: expression △ term
            | expression ▽ term
            | term
            ;
  term      : factor ○ term
            | factor ● term
            | factor
            ;
  factor    : LEFTP expression RIGHTP
            | NUMBER
            ;

授業へのコメント (6 点)

この授業で一番分かりにくかったことを書きなさい。 (決まった正解はありません。)

@@@@

この授業で一番勉強になったことを書きなさい。 (決まった正解はありません。)

@@@@