入力と出力の難しさ (9 点)

一般的に、プログラムの入力と出力のどちらの方が難しいのか、具体例を交え項目を分けて詳しく説明しなさい。

一般的に、プログラムの出力より明らかに入力が難しいです。

理由の一つは、プログラム内のデータが構造化されているのに、
ファイル内のデータはただ文字 (実際はバイト) の羅列だけです。入力は構造を分析、
認識しないといけないのに対し、出力はただ構造に沿って文字列に変換すればよいです。
例えば XML の場合、入力には &lt; などがありますが、これをプログラムの内部に <
で表現できる。< → &lt; よりも &lt; → < の変換ははるかに簡単です。

もう一つの理由は、入力には色々間違いがあり得ることです。例えば
コンパイラの場合、全てのテキストファイルを考えると、その内、正しいプログラムの割合が
非常に低くて、間違っているプログラムが非常に多いです。入力はそれらすべてに
何かの形で対応しないといけないが、出力は正しいデータを前提にできる。

英語の用語 (20 点)

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

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

Kleene Closure: クリーン閉包: * で表すある語や言語の 0 回以上の連結

Top-down parsing: 下向き構文解析; 初期記号、すなわち解析木の一番上から構文解析を行う

Empty Word: 空語; 長さ 0 の語

Panic Mode: エラー処理の一つで; 文法に合うトークンを見つけるまでにトークンを捨てる

Type Inference: 型推論; 変数などの方をプログラムの分析によって導き出す

State Transition Table: 状態遷移表; オートマトンの状態と入力によって次の状態を示す表

Mark and sweep: 印掃式; ゴミ集めの一つの方法で、印をつけて回収不可能なメモリを識別

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

Nondeterministic Finite Automaton: 非決定性有限オートマトン; ε 遷移や分身を許す有限オートマトン

正規表現と bison の文法 (24 点)

下記左側の実用的な正規表現を有限オートマトンと bison 風の文法に変換しなさい。 bison 風の文法への変換の前提は、字句解析を使わずに処理のすべてを一段階で行うことである。

詳細： 有限オートマトンはできるだけ簡略化して下さい。正規表現の一つ一つの文字をそのまま bison のトークンとして使う。実際の bison の場合と違って、終端記号 (トークン) を小文字一つ、非終端記号を大文字一つで表す。 C による計算は不要。初期記号としてはどの問題でも S を使用。ヒント: 一部の場合、非終端記号の導入が必要。

S: a b
 | c d;

S: a S
 | ;

S: b S
 | b;

S: c
 | ;

S: b
 | c
 | d;

S: a a
 | a a a
 | a a a a;

S: a
 | b Q;
Q: c Q
 | ;

S: T S
 | T;
T: a
 | b;

S: Q S | Q;
Q: a | T;
T: b T | ;
 

プッシュダウンオートマトンの作成 (10 点)

「(」と「)」が入れ子になっている言語を受理するプッシュダウンオートマトンを作成し、その遷移図を書きなさい。

言語に含まれる語の例： ε, (), ()(), (()), (()(()()))() など; 言語に含まれない語の例： (, ), (())), ())( など。

コード生成と最適化の順番 (10 点)

コード生成と最適化の順番について、最適化の手法や手段に具体的に言及しながら詳しく説明しなさい。

コード生成と最適化はコンパイラのそれぞれ別の段階。
しかし実際にはどの順番 (すなわちコード再生が先、それとも最適化が先)
でもあり得ますし、交互で行われていることも多い。例えば構文木上で静式評価
や演算の変更という最適化後に、いったんコード生成をて、
生成したコードで再度ピープホール最適化を行ったり、制御フロー解析や
データフロー解析をして、その結果を利用して定数伝播や無用命令の削除
を行うことが考えられます。

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

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

@@@@

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

@@@@

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

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

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

コード生成と最適化の逆変換 (16 点)

下記の左側の最適化された超単純アセンブリ言語の断片を、真ん中で制限された C 言語 (制御文は if と goto のみ、if 文の条件は 0 との比較のみ、if 文後は goto のみに制限) に変換し、右側で普通の C 言語のプログラマが書くプログラム (goto 無し) に変換しなさい。

        CONST   R1, -1
        CONST   R2, 20
        CONST   R3, 1
        LOAD    R4, b
next:   ADD     R1, R1, R3
        ADD     R4, R4, R1
        SUB     R5, R1, R2
        JUMP<   R5, next
        JUMP<   R4, next
        STORE   b, R4
        STORE   k, R1

        k = -1;
next:   k += 1;
        b += k;
        if (k-20<0)
            goto next;
        if (b<0)
            goto next;

for (k=0; k<20 || b<0; k++)
{
    b += k;
}

モジュロ演算のコード生成 (6 点)

下記の左側の C 言語のプログラム断片を超単純アセンブリに書き換えなさい。ただし、a が正と仮定してよい。

    c = a % 5;        
      

        LOAD    R1, a
        CONST   R2, 5
        DIV     R3, R1, R2
        MUL     R3, R3, R2
        SUB     R3, R1, R3
        STORE   c, R3

形式言語の階層と文法の書き換え規則 (合計 13 点)

チョムスキーによる形式言語の階層は文法の書き換え規則の制限に対応している。