英語の用語 (20 点)

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

Empty word: 空語; 長さ 0 の語、ε で表す

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

Attribute grammar: 属性文法; 文法の書換規則とともに(非)終端記号の属性も書替える仕組み

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

Syntactic sugar: 糖衣構文; 本質機能ではなく利便性のための構文

Kleene closure: クリーン閉包、語や言語の0回以の連結、* であらわす

Bottom-up parsing: 上向き構文解析; 構文解析で終端記号から初期記号へと解析を進むこと

Control flow analysis: 制御フロー解析; 最適化の手法の一つで、プログラムの流れの解析

Concrete syntax tree: 解析木; 構文解析の途中経過など構文解析方法の研究・調査に使う木

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

bison の動作 (8 点)

次に bison -v で作成された .output のファイルの一部 (一つの状態についての情報) を示す。

state 18

   23 addExpression: mulExpression .
   24 mulExpression: mulExpression . '*' unaryExpression
   25              | mulExpression . '/' unaryExpression
   26              | mulExpression . '%' unaryExpression

    '*'  shift, and go to state 44
    '/'  shift, and go to state 45
    '%'  shift, and go to state 46

    $default  reduce using rule 23 (addExpression)

上記の . (四ヶ所) の意味を説明しなさい。 (2 点)

. は解析の現在位置を表します。

bison の解析方法は LALR(1) と名付けらている。その中の (1) を上記の例を使って説明しなさい。(3 点)

(1) は先読みがトークンひとつであることを示す。上記の例では現在位置 . の次のトークン *, /, 又は % を先読みし、それの種類や有無によって次の動作を決定する。

.output ファイル内の状態 46 でのルール 26 を書きなさい。そのルールしかないと想定しなさい。(3 点)

26 mulExpression: mulExpression '%' . unaryExpression

文法のパターン (15 点)

下記の項目を文法のパターンを使って表しなさい。記述は bison 風の文法でも理論的な文法の記述方法でもよいが、統一すること。

式 S が演算子 # と部分式 T からなって、演算子 # が左結合である。
(例： T # T # T # T は (((T # T) # T) # T) と解釈すべき)

S: S # T
 | T
 ;

項目列 X はゼロ個以上の Y からなる。

X: Y X
 |
 ;

式 R が演算子 @ と部分式 Q からなって、演算子 @ が右結合である。
(例： Q @ Q @ Q @ Q は Q @ (Q @ (Q @ Q))) と解釈すべき)

R: Q @ R
 | Q
 ;

大きな式 M は中の式 N と二項演算子 $ からなって、中の式がさらに小の式 V と二項演算子 & から構成される。$ より & の優先度が高くて、結合規則はどちらの方向でもよい。
(例： V $ V & V は V $ (V & V) と解釈すべき)

M: M $ N
 | N
 ;
N: N & V
 | V
 ;

名前表 (合計 10 点)

名前表が扱うデータを細かく列挙しなさい。(6 点)

• 名前の種類 (変数、関数、型など)
• 宣言・定義・使用の種別
• 変数、関数などの型
• 名前が有効な領域 (例えば関数、ブロック)
• 変数などの場合: 大きさ (必要なメモリ)
• 関数、変数などの (相対) アドレス

名前表の二つの要点について説明しなさい。(4 点)

• 使うことが多く、名前の数が多いので効率が大切
• 同じ名前が複数ある可能性があるので区別が必要

文法の解釈 (16 点)

文法 S → o, S → qSp, S → pSq  から、それぞれすべての書換規則を使いながら 3個のお互いに異なる長さの語を作成しなさい。 (3 点)

qpoqp, pqopq, qqpoqpp

直前の部分問題の文法が受理する言語とその長さを説明しなさい。 (3 点)

真中が必ず o で、その周りに真中と同じ距離で左が p でしたら右が q、左が q でしたら右が p。p と q がお互いに左右対処なので結果が左右対称に見える。長さが必ず奇数。

文法 S → ε, S → qSp, S → pSq  から、それぞれすべての書換規則を使いながら 3個のお互いに異なる長さの語を作成しなさい。 (3 点)

qpqp, pqpq, ppqpqq

直前の部分問題の文法が受理する言語とその長さを説明しなさい。 (3 点)

真中の周りに真中と同じ距離で左が p でしたら右が q、左が q でしたら右が p。p と q がお互いに左右対処なので結果が左右対称に見える。長さが必ず偶数。

上記の二つの言語の受理に必要なオートマトンとその違いについて詳しく説明しなさい。 (4 点)

最初の言語には真中の印 (o) があるので、決定性プッシュダウンオートマトンで受理可能だが、二つ目の言語では真中の印がないので、非決定性プッシュダウンオートマトンでしか受理できません。 有限オートマトンと違って、プッシュダウンオートマトンの場合一般に非決定性のものの決定性のものへの返還が不可能です。

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

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

@@@@

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

@@@@

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

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

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

コード生成 (12 点)

下記の左側の C 言語のプログラム断片を超単純アセンブリ言語に変換しなさい。

for (i=0; i<20 && a>0;
          i++) {
    a /= b;
}

        CONST  R1, 0
        STORE  i, R1
next:   LOAD   R1, i
        CONST  R2, 20
        SUB    R1, R1, R2
        JUMP>= R1, end
        LOAD   R1, a
        JUMP<= R1, end
        LOAD   R1, a

        LOAD   R2, b
        DIV    R1, R1, R2
        STORE  a, R1        
        LOAD   R1, i
        CONST  R2, 1
        ADD    R1, R1, R2
        STORE  i, R1
        JUMP   next
end:

最適化 (8 点)

上記の単純アセンブリ言語を最適化しなさい。
ヒント: レジスタ 4個を使えば、合計 11 12 個の命令で、ループそのものは5個4個の命令で可能。

     
        CONST  R1, 1  ; 定数
        CONST  R2, 20  ; 20-i
        LOAD   R3, a
        LOAD   R4, b
next:   JUMP<= R3, end
        SUB    R2, R2, R1

        DIV    R3, R3, R4
        JUMP<  R2, next
end:    STORE  a, R3
        CONST  R1, 20
        SUB    R2, R1, R2
        STORE  i, R2

形式言語の表 (合計 18 点)

次の表の空白を埋めなさい。 (10 点)

上記の表の意義や用途について論じなさい。 (4 点)

形式言語を分類することで言語の解析の難しさを判断でき、適切なツールの選択につながる。さらに、言語の設計において、 設計を少し変換することで解析を大幅に簡単化できる可能性があることが分かり、活用が可能である。

上記の表のコンパイラの設計や実装においての役割について述べなさい。 (4 点)

コンパイラではフロントエンドを字句解析と構文解析に分けることが効率的である。字句を正規表現で表現でき、 有限オートマトンで解析できると効率的。構文解析の場合、文脈自由言語を使って、文脈自由文法で言語の文法を定義し、 プッシュダウンオートマトンやそれと類似する仕組みで解析可能にするとよい。

正規言語の表現方法 (合計 12 点)

正規言語の授業で習った表現方法をすべて列挙しなさい。(5 点)

1. 正規表現
2. 非決定性有限オートマトン
3. 決定性有限オートマトン
4. 左線形文法
5. 右線形文法

上記の中から二つ選んで、その間の変換を実例を使いながら詳細に説明しなさい。(7 点)

[省略]

参照カウント GC (合計 10 点)

参照カウント GC の原理、利点、欠点をそれぞれ説明しなさい。

原理 (4 点): 各参照されるメモリのブロックに、何回参照されているかのカウントが付く。参照が増えるとそのカウントが ++, 参照が減るとこのカウントが -- たされる。カウントが 0 となった時点でメモリが回収可能。

利点 (3 点): ゴミ集めに必要な操作が他の操作と細かく入れ混じっているので、他の GC 方法と違ってゴミ集めのために他の処理を長時間停止する必要がない。

欠点 (3 点): 参照のサイクルが残る可能性がある。その場合、他の GC 方法で回収可能なメモリが回収できなくなる。

DFA の単純化 (合計 37 点)

DFA には場合によって無駄な遷移や状態がある。それを省くために DFA の最小化を使う。最小化の方法は複数あるが、ここで Brzozowski のアルゴリズムを使用する:

1. 与えられた DFA の「逆 NFA」を作成：
   1. 全ての遷移 (状態間の矢印) の方向を逆にする。
   2. 初期状態と受理状態を入れ替える。その時、元の DFA に受理状態が複数あった場合、「逆 NFA」で初期状態が複数できる。本来の NFA の定義に反するが、問題にしなくてよい (ゲームの言葉に言い替えると、二人以上の分身で二つ以上の場所からスタートできること)。
2. 「逆転 NFA」を DFA へ変換。結果は「逆転 DFA」。逆転 DFA は (面白いことに) 最小化されているが、元の DFA の逆の語の言語を受理する。そのため、最小でありながらもとの DFA より状態の数が多いこともありうる。
3. 「逆転 DFA」にステップ 1. と 2. をもう一回適応すると、元の DFA の最小化が完成。

次の遷移表で与えられた DFA を上記のアルゴリズムに沿って最小化しなさい。

下記左の遷移表の DFA の遷移図を作りなさい。 (6 点)

[図省略]             

上記の遷移図から 「逆転 NFA」 の遷移図を示しなさい (6 点)。

  
  
  [図省略]

[次ページに続く]

[前ページから続く]

「逆転 NFA」から「逆転 DFA」を作成し、その遷移表を示しなさい (7 点)。
確認のヒント: 初期状態は {BD} である。

「逆転 DFA」の状態名を書き換えてから、再度逆転し、その結果を再度 DFA に変換し、結果の (最小化された) DFA の遷移表と遷移図を示しなさい (10 点)。確認のヒント: 最小化された DFA の状態の数が 3 である。

[図省略]             

元の DFA と最終結果の DFA を比較し、最終結果が元の DFA と同じ言語を受理するかどうか、最小であるかどうかについて論じなさい (5 点)。

最小であるかどうかという点ですが、仮に a だけの言語を考えると、「a の数を三つで割った余りが 1」の言語が受理されますが、これは三つより少なめの状態では受理不可能です。同じ言語かどうかは、元の DFA の A と C、B と D、そして E と 　F の状態を合流すれば確認できます。

DFA の最小化は flex においてどう使われるのか説明しなさい (3 点)。

flex では複数の正規表現から字句の認識のために NFA 経由で DFA が作成される。このためのテーブルをコンパクトにするには DFA の最小化が有効である。