青山学院大学

前期試験 ・ 2009 年 7 月 24 日 2 時限実施 ・ ページ

授業
科目		 言語理論とコンパイラ 学生番号 学科 学年 組 番 フリ
ガナ		   評点
                        氏名    
担当者 DÜRST, Martin J.

ゴミ集めの詳細 (8 点)

ゴミ集めの方法を一つ選んで、明記の上、例を含め細かく説明しなさい。

印掃式 (mark and sweep): すべてのヒープにあるオブジェクトに
「まだ必要か」の印をつける。ゴミ集めの最初にすべての印を OFF にする。
グローバル変数やスタックからポインタを辿って、ヒープにあるオブジェクトに
辿りついたら印が ON のときに何もしないが、OFF のときに ON にし、その
オブジェクトからのポインタを更に辿る。全て辿り終わったら、印がOFF になっているオブジェクト
をゴミ集めする。同時に ON の印を OFF にすると次のゴミ集めの初期化も出来てしまう。

英語の用語 (20 点)

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

Data Flow Analysis: データフロー解析; どこの変数の代入がどの変数の使用に影響を及ぼすか

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

Context-sensitive grammar: 文脈依存文法; 文脈依存言語を定義する文法

Nonterminal Symbol: 非終端記号; 文法でまだ書換ないといけない記号

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

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

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

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

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

Attribute Grammar: 属性文法; 文法の書換規則とともに属性 (値、構文木等) も書替える仕組み

有限オートマトンの単純化 (12 点)

次の遷移表で与えられた有限オートマトンを単純化し、結果を遷移図で示しなさい。

A simplified automaton
  a b
→S U T
T U T
*U U W
V U T
*W W X
*X X U

前期試験 ・ 2009 年 7 月 24 日 2 時限実施 ・ ページ

コード生成 (15 点)

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

命令 被演算子 説明 (コメント)
LOAD R1, a メモリの変数 a の値をレジスタ R1 に代入
STORE a, R1 レジスタ R1 の値をメモリの変数 a に代入
CONST R1, 5 レジスタ R1 に 5 の定数を代入
JUMP label 無条件に label へジャンプ
JUMP< R1, label レジスタ R1 が 0 より小さい時 label へジャンプ
(同様に JUMP<=, JUMP==, JUMP!=, JUMP>= と JUMP> がある。)
ADD R1, R2, R3 R2 と R3 を足して R1 に代入。同じレジスタを何回使ってもよい。
同様に SUB、MUL、DIV がある。

以上の命令で詳細は次のようになる:

次のプログラムの部分を超単純アセンブリに書き換えなさい。

 if (x > y  && x > z)
     a = x;
 else if (y > z)
     a = y;
 else
     a = z;
 
        LOAD    R1, x
        LOAD    R2, y
        LOAD    R3, z
        SUB     R4, R1, R2
        JUMP<=  R4, elsif
        SUB     R4, R1, R3
        JUMP<=  R4, elsif
        STORE   a, R1
 
        JUMP    end
elsif:  SUB     R4, R2, R3
        JUMP<=  R4, else
        STORE   a, R2
        JUMP    end
else:   STORE   a, R3
        JUMP    end
end:

コードの最適化 (15 点)

下記の表の左側にある C 言語の関数を、使用した最適化を変更箇所に明記のうえ五つの最適化を応用して最適化された C 言語のプログラムに書き換えなさい。

int f (int a)
{
    int b = 100;
    int c;
    int i = 0, r = 0;

    while (i < b) {
        c = a * a;
        if (r % c != 3 + 2)
            r += i * 4;
    }
    return r;
    r *= 3;
}
 
int f (int a)
{   /* 定数伝播 */
    int c = a * a;
    int i = 0, r = 0;
    while (i < 100) {
        /* 共通の式の繰り返しからの追い出し */
        if (r % c != 5) /* 定数畳み込み */
            r += i << 2; /* 演算の変更 */
    }
    return r;  /* 無用命令の削除 */
}

青山学院大学

前期試験 ・ 2009 年 7 月 24 日 2 時限実施 ・ ページ

授業
科目		 言語理論とコンパイラ 学生番号 学科 学年 組 番 フリ
ガナ		   評点
                        氏名    
担当者 DÜRST, Martin J.

正規表現の作成 (20 点)

次の語を受理する・受理しない一番短い (文字数が少ない) 正規表現を作りなさい。列挙されてない語は受理してもしなくても構わない。使える記号は |, *, (, ) と ? である。

受理する語 受理しない語 正規表現
例 a, aa ε aa*
abcde, abcdf abcd, abcdef, abcdfe abcd(e|f)
abc, abcd, abce, adbcde abd, abcdd, abced, abceee abcd?e?
bbb, bbbbbb, bbbbbbbbb b, bb, bbbb, bbbbb (bbb)*
bbb, bbbbb, bbbbbbb, b bb, bbbb, bbbbbb b(bb)*
x, yy, xx, y, yyy xy, yyx x*|y*
x, xy, xx, y, yy, xxxxyyy yx x*y*
ax, ay, axy, ayx, ayy, axx, axyx xy, ya a(x|y)*
pppqp, qpp, pqp, ppppq, q, ppqpppp, pppppqp qq, pp, pq, ppqp, ppqqpp (pp)*(q|pqp)(pp)*
kk, kkk, kkkk k, kkkkk, kkkkkk kkk?k?
g, hg, hhg, hhhg, gg, ghhg, hgghhhg h, gh, hh, ggh (h*g)*

簡単な文法の作成 (15 点)

C 言語の一部の文法を書きなさい。終端記号 (トークン) は NUM (整数の定数)、 MINUS ('-')、SLASH ('/')、EQUAL ('=')、IDENT (変数名)、SEMICOLON (';')、LPAREN ('(')、RPAREN (')') に限定される。初期記号は statements (文のリスト)。非終端記号にはわかりやすい名前やその略を使用。結合や優先順位を間違えないように注意。

statements → statement statements | 
statement → expression SEMICOLON
expression → IDENT EQUAL expression
expression → subExpression
subExpression  → subExpression MINUS term | term
term → term SLASH factor | factor
factor → NUM | IDENT | LPAREN expression RPAREN

前期試験 ・ 2009 年 7 月 24 日 2 時限実施 ・ ページ

有限オートマトン (合計 16 点)

有限オートマトンと線形文法 (6 点)

次の有限オートマトンを線形文法に変更しなさい。

finite state automaton 
      F → aG | bL | b
      G → aJ | bH
      H → aL | a | bJ
      J → aM | a
      K → bM | b
      L → aJ | bJ | aN
      M → G
      N → aJ | bM | b

NFA と DFA (10 点)

上記の NFA を DFA に変更し、その状態遷移表を書きなさい (状態を書き替える必要は無い)。

a b
→{F} {G} {L}
{G} {J} {H, K}
{H, K} {L} {J, M, G}
{J} {M, G} {}
{L}* {J, N} {J}
{J, M, G}* {J, M, G} {H, K}
{M, G}* {J} {H, K}
{J, N} {J, M, G} {M, G}

実用化された正規表現 (6 点)

実用化された正規表現にしかない主な機能三つを (論理的な正規表現への置き換えを含め) 説明しなさい。

'+' は「一つ以上」を表している。a+ は論理的な正規表現で aa* と書く。

[] 内の文字の羅列で文字クラスを表すことが可能。[abc] は論理的で (a|b|c) と書く。

{} 内に繰り返しの最初と最大の回数を書ける。a{2,4} は aa(a|ε)(a|ε) と論理的に書ける。

青山学院大学

前期試験 ・ 2009 年 7 月 24 日 2 時限実施 ・ ページ

授業
科目		 言語理論とコンパイラ 学生番号 学科 学年 組 番 フリ
ガナ		   評点
                        氏名    
担当者 DÜRST, Martin J.

プッシュダウンオートマトン (合計 15 点)

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

綺麗に入れ子になっている丸括弧の言語を受理するプッシュダウンオートマトンの図を書きなさい。「綺麗に入れ子」というのは次の条件を指す: 語内のある点までの開け括弧の数は常に閉じ括弧の数より多く、語の先頭と最後だけでは開け括弧と閉じ括弧の数が等しい。

A pushdown automaton

プッシュダウンオートマトンの能力 (5 点)

上記の言語はなぜ有限オートマトンで受理できないのかを説明しなさい。

言語を受理するには開け括弧が閉じ括弧よりどのぐらい多いのかを常に管理しないといけないです。n 個の括弧を数えるには NFA の場合に log2 n 個程度、DFA の場合 n 個程度の状態が必要が、有限オートマトンは名の通り一定の有限の状態の数しかないので、受理が不可能。

エラー処理 (5 点)

コンパイラのよいエラー処理に要求されるものを五つ列挙しなさい。

1. 分かりやすいエラーメッセージ; 2. 一つだけではなく、複数のエラーを見つける; 3. 二次エラーをできるだけ抑える; 4. 正しいプログラムの処理を遅くしない; 5. コンパイラを出来るだけ簡単のままにする