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

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

[図省略]

上記の機械の ...␣10101␣... に対する動作を示しなさい。スタートの場所は真中の 1 である。(8 点)

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

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

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

まず、状態 A では左側の最初の_まで移動し、0/1 の領域内に戻る。状態 B で一番左の0や1を消し、 その値を状態 (C は 0、D は 1) に記憶し、ひとマスずつ右に移動。右側の最初の_に着いたら、移動してきた値を捨て、一歩だけ左に行って、一番右の0や1に停止する。 結果、テープ上のデータを二進数で解釈すると、2での割り算 (余りを無視) という計算を行う。

有限オートマトンと文法 (合計 18 点)

左の遷移表の非決定性有限オートマトンに相当する状態遷移図を右側に書きなさい (5 点)。

上記の有限オートマトンを決定性のものに変換し、その遷移表を (状態の書換無し) で書きなさい (8 点)。

上記の非決定性有限オートマトンを右線形文法に書換なさい。ヒント： 右線形文法には ε 遷移が無いので、できれば除去してみなさい (5点)。

S → xA | xB | xC | x | yA; A → yB | yC | y | zC | z; B → xS | xA; C → xA

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

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

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

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

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

式の解釈 (20 点)

下記 4つの小問ごとに、文法に従って式の中の計算順を括弧で明記しなさい。文法で解析不可な場合または曖昧な場合はその旨だけを書きなさい。なお、NUM は数値のトークンを表す。

例: Exp → NUM ∆ NUM

 (5  ∆  7)
  ∆  5  ∆  ∆  7  解析不可

Exp → Exp ∆ NUM | NUM (3点)

  (5   ∆   7)
 ((5   ∆   7)  ∆   3)
(((5   ∆   7)  ∆   4)  ∆   3)

Exp → NUM ∆ Exp | NUM (3点)

  (5   ∆   7)
  (5   ∆  (7   ∆  3))
  (5   ∆  (7   ∆ (3   ∆   4)))

Exp → Exp ∆ Got | Got; Got → NUM ⁑ Got | NUM (6点)

  ((5    ∆   (7    ⁑   (3    ⁑    4))) ∆    9)
 (((5   ⁑   (7    ⁑    3))  ∆     4)   ∆    9)
 (((5   ⁑    7)    ∆    3)   ∆    (4    ⁑    9))

Exp → Exp ∆ Got | Got; Got → NUM | ∆ NUM (4点)

  ((5    ∆   (∆    7))  ∆   3)
  ((5    ∆    7)   ∆   (∆    3))

上記4つの部分問題において、プログラミング言語で現れる現象を専門用語を使って説明しなさい。必要に応じて部分問題の番号を使ってください (4点)。

4.1 で演算子 ∆ は左結合に対し、4.2では右結合。この違いは文法の左再帰 (4.1) や右再帰 (4.2) によって表されている。 4.3 では演算子 ∆ (左結合) より演算子 ⁑ (右結合) の優先度が高いです。これは文法で優先度の低いものから優先度の高いものへ展開することで表されている。 4.4 では前置 (単項) の演算子 ∆ が二項演算子 ∆ より優先度が高いです。普通の式の符号 (前置単項 -) と同じ仕組みです。

授業へのコメント / Comment on Course (6 点)

この授業で一番分かりにくかったことを書きなさい (決まった正解はありません)
What was most difficult to understand in this course (there is no single answer)

@@@@

この授業で一番勉強になったことを書きなさい (決まった正解はありません)
What was most informative/interesting in this course (there is no single answer)

@@@@

コード生成と最適化、並びに文法の曖昧さ (合計 30 点)

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

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

下記の左側には 0 より大きい整数 a、 b の最大公約数を計算するプログラム (の一部) である。これを制限された C 言語 (制御文は if と goto のみ、if 文の条件は 0 との比較のみ、if 文後は goto のみ)、最適化されてないアセンブリ、最適化されたアセンブリにそれぞれ変換しなさい。

if (a>0 && b>0)
    while (a != b)
        if (a > b)
            a -= b;
        else
            b -= a;

    LOAD    R1, a
    JUMP<=  R1, end1
    LOAD    R1, b
    JUMP<=  R1, end1
next1:
    LOAD    R1, a
    LOAD    R2, b
    SUB     R1, R1, R2
    JUMP=   R1, endwhile
    LOAD    R1, a
    LOAD    R2, b
    SUB     R1, R1, R2
    JUMP<=  R1, else1
    LOAD    R1, a
    LOAD    R2, b
    SUB     R1, R1, R2
    STORE   a, R1
    JUMP    endif1
else1:
    LOAD    R1, a
    LOAD    R2, b
    SUB     R1, R1, R1
    STORE   b, R1

endif1:
    JUMP    next
endwhile: end1:

    LOAD    R1, a
    JUMP<=  R1, end1
    LOAD    R2, b
    JUMP<=  R2, end1
next1:
    SUB     R3, R1, R2
    JUMP=   R3, endwhile
    JUMP<=  R3, else1
    SUB     R1, R1, R2
    JUMP    next1
else1:
    SUB     R2, R2, R1
    JUMP    next1
endwhile:
    STORE   a, R1
    STORE   b, R2
end1:

    if (a <= 0)
        goto end1;
    if (b <= 0)
        goto end1;
next1:
    if (a-b == 0)
        goto endwhile;
    if (a-b <= 0)
        goto else1;
    a = a - b;
    goto endif1;
else1:
    b = b - a;
endif1:
    goto next1;
endwhile: end1:

bison が構文解析に使用されたことと、 if文・if-else文が一般的な曖昧な文法で定義されたことを前提に、なぜ上記の C 言語の断片がインデントの通り構文解析されるのかを説明しなさい (6 点)。

if-else 文の一般的な曖昧な文法は bison の場合、else トークンを読む時点で shift-reduce コンフリクトを起こしますが、その場合、bison が shift を選択するため、else 文の前の部分 (今回は while とその中の if) が reduce されなくて、else が直前の if と対で解釈される。

文法からの導出と文法の作成 (合計 24 点)

次の文法から導出可能な一番短い三つの語を途中経過を含め導出しなさい。

S → Tb, T → BTA, T → BA, BA → AB, BBA → ABB, A → a, AA → aa, B → b, BB → bb

一番短い語の導出 (1点):

S → Tb → BAb → ABb → aBb → abb

二番目に短い語の導出 (2点):

S → Tb → BTAb → BBAAb → bbAAb → bbaab

三番目に短い語の導出 (3点):

S → Tb → BTAb → BBTAAb → BBBAAAb → BABBAAb → ABBBAAb → ABbbAAb → aBbbAAb → abbbAAb → abbbaab

上記の文法の種類 (文法族) とその理由を書きなさい (3点)。

句構造文法です。なぜなら、AA → aa で二つ以上の非終端記号が一気に書き換えられ、これは文脈依存文法でも許されていません。

この文法からどのような語が導出できるかを説明しなさい (3点)。

a が n 個 (n>=1) で、 b が n+1 個で、最後が b 以外順番が自由な語

上記の文法が定義している言語の種類 (言語族) とその理由を書きなさい (3点)。

文脈自由言語; 理由: 最後の b はおまけとして、残りは a (b) が多ければ a (b) の多い分、プッシュダウンオートマトンで数えればいい。

直前の部分問題で書いた言語(族) に対応する文法(族) でこの問題の言語の語が導出できる文法を書きなさい。
(3点、ヒント: 最初の文法より簡単になるはず。)

S → Xb, X → ab | ba | aXb | bXa | abX | baX | aXbX | bXaX

この問題の言語を受理できるオートマトンを、種類を明記した上で書きなさい (6点)。

種類は (非決定性) プッシュダウンオートマトンです。
      _                             =
     / \              b,Z/Z       // \\
  ->| p |------------------------>||r||
     \ /                          \\ //
      - ↖                           =
     \  / a,Z/AZ; a,A/AA; a,B/ε       
      --  b,Z/BZ; b,B/BB; b,A/ε

構文解析の実装問題の解決 (合計20点)

次の関数はある構文解析の実装の一つの関数を示す。

int Expression() {
    int r = Expression();

    if (nextToken.type == plus) {
         nextToken = getNextToken();
         r += Term();
    }
	else if (nextToken.type == minus) {
         nextToken = getNextToken();
         r -= Term();
    }
    return r;
}

この実装が使っている解析方法の名称を書きなさい (2点): 再帰的下向き構文解析

上記の関数の実装の問題点を説明しなさい (3点)。

左再帰といわれる問題です。Expression 関数の 中で最初に何もチェック無しに自分 (Expression関数)を呼んでしまうので、すぐスタックオーバフローなどになる。

関数内の getNextToken の目的・使い方を説明しなさい (3点)。

getNextToken 関数は字句解析から次のトークンを読み込む。前のトークンを処理した直後にすぐ呼ばないといけません。

上記の問題が解決するように関数を書き直しなさい。(8点)

int Expression() {
    int r = Term();

    while (nextToken.type==plus || nextToken.type==minus) {
        if (nextToken.type == plus) {
             nextToken = getNextToken();
             r += Term();
        }
        else { // nextToken == minus
             nextToken = getNextToken();
             r -= Term();
        }
    }
    return r;
}

文法で上記の関数 (修正後) に相当する部分を書いて、その記述方法や使った記号について説明しなさい (4点)。

文法: Expression → Term { ('+' | '-') Term }
これは EBNF という記法で、{} は0回以上の繰り返しを表している。このような繰り返しで左再帰が避けられるので、再帰的下向く構文解析ではよく EBNF が使われる。

英語の用語 / English Terms (24 点)

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

Terminal Symbol: 終端記号: 文法でもう書き換えられない記号 (構文解析の場合トークン)

Dynamic Compilation: 動的コンパイル: プログラムの実行時の統計を利用したコンパイル

Environment Variable: 環境変数: 環境で設定され、プログラムから利用できる変数

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

Empty Word: 空語: 長さ 0 の語

Turing Completeness: チューリング完全性: チューリング機械と同じ計算能力を保持する性質

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

Attribute Grammar: 属性文法: 書換規則とともに属性 (例: 式の値、構文木) も書き替える

Constant Propagation: 定数伝播: 最適化で、(変数に代入された) 定数を追って、入れ換える

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

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

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

正規表現の作成 (10点)

次の形式言語を受理する理論的な正規表現 （使える記号は |, *, ( と )) 又は実用化された正規表現を作りなさい。