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

次の英語の用語の (カタカナのできるだけ少ない) 日本語訳と説明を書きなさい。
Provide Japanese translations (avoiding Katakana where possible) and explanations of the following English terms

Relocatable program: 再配置可能プログラム; .obj ファイル等、再配置が可能な機械語のもの

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

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

Chomsky hierarchy: チョムスキー階層; 形式言語理論での言語族の包囲階層

Control Flow Analysis: 制御フロー解析; プログラムを基本ブロックに分けてその流れの解析

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

Semantic analysis: 意味解析; コンパイラの3番目の段階、主に型のチェックなどが行われる

Secondary error: 二次エラー; 前のエラーで本来エラー出ないところがエラーとなること

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

Symbol table: 名前表; 関数・変数名などの名前、型、スコープなどを管理する表

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

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

Linear-bounded automaton: 線形束縛オートマトン; 文脈依存言語を受理するオートマトン

Priority: 優先度; 演算子の計算順を決め、文法の構造で表せるもの

Scope: 有効範囲; ローカル変数などがプログラムのどこで使えるか示すもの

Control Flow Analysis: 制御フロー解析; プログラムを基本ブロックに分けてその流れの解析

授業へのコメント / 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)

@@@@

右線形文法と左線形文法 / Right Linear Grammars and Left Linear Grammars (62点)

次の文書を完成させなさい (一つの言語を選択)。/ Complete the following text (select a single language). (7 点)

右線形文法は   右線形規則   (1) (例: A → cB) と   定数規則   (2) (例: A → c) からなる。 左線形文法は
  左線形規則   (例: A → Bc) と (2) からなる。
有限オートマトンと右線形文法は次のように対応する。 オートマトンの入力記号は文法の   終端記号   と対応する。 オートマトンの状態は文法の   非終端記号   と対応する。   初期状態   は初期記号と対応する。
  受理状態   への遷移は定数規則と対応する。 全ての遷移は (1) と対応。

A right linear grammar consists of   right linear rules   (1) (e.g. A → cB) and   constant rules   (2) (e.g. A → c). A left linear grammar consists of   right linear rules   (e.g. A → Bc) and (2).
Finite state automata and right linear grammars correspond as follows. The input symbols of an automaton correspond to the   terminal symbols   of a grammar. The states of an automaton correspond to the
  nonterminal symbols   of a grammar. The   start state   corresponds to the start symbol. Transitions to the   final states   correspond to constant rules. All transitions correspond to (1).

次の文法について以下の問に答えなさい。/ Please answer the questions below for the following grammar:
S → aQ | aR | bQ; Q → bR | cR | cT; R → bS; T → bR | c

      S
     / ∖
    a   R
       / ∖
      b   S
         / ∖
        a   Q
           / ∖
          c   T
              | 
              c

               F
              / ∖
             T   c
            / ∖
           Q   c
          / ∖
         S   a
        / ∖
       R   b
       |
       a

この言語の左線形文法を書きなさい。/ Write the left linear grammar for the language. (6 点)

F → Tc; T → Qc; R → Qb | Qc | Sa | a; Q → Sa | Sb | a | b; S → Rb

[次ページへ続く / continued on next page]

[前ページから続く / continued from previous page]

右線形文法と左線形文法と同じ表現能力をもつ仕組みを列挙しなさい。
List the mechanimsm that have the same power as right linear grammars and left linear grammars. (3 点)

正規表現、決定性有限オートマトン、非決定性有限オートマトン

この仕組みが生成・受理できる言語族を書きなさい。
Write the language family that these mechanisms produce/recognize. (2 点)

(3) 正規言語

右線形文法と左線形文法で許されている書換規則を全部使える文法 (この試験で「左右線形文法」と命名) を考える。次の文法をそのような文法に書き換えなさい。ヒント: 新しい記号を導入してよい。
Think about a grammar that can use all the rewriting rules permitted in left linear grammars and right linear grammars (we will call such grammars "left-right linear grammars"). Rewrite the following grammar using such a grammar. Hint: You can introduce additional symbols. (3 点)
S → aSa | bSb | c

S → aR | bT | c; R → Sa; T → Sb

前問の文法を、A → BC と D → d のような書換規則しか許されていない Chomsky 標準形に書き換えなさい。ヒント: さらに記号を導入する。/ Rewrite the grammar in the previous problem to Chomsky normal form, which only allows rewriting rules of the form A → BC and D → d. Hint: Introduce more additional symbols. (3 点)

S → AR | BT | c; R → SA; T → SB; A → a; B → b

「左右線形文法」で生成される言語が (3) に限定されないことを説明しなさい。
Explain why languages produced by "left-right linear grammars" are not limited to (3). (4 点)

解析木で考えると、左右線形文法では解析木がだだ右下 (又は左下) に線形に伸びるのではなく、ジグザグの動きをする。 S → aSa | bSb | c の文法は左右対称の言語を生成するが、それは正規言語ではありません。

「左右線形文法」が生成する言語はどの言語族に属しているか書きなさい。
Write to which language family the languages generated by "left-right linear grammars" belong. (2 点)

(4) 文脈自由言語

「左右線形文法」 で生成できない (4) に属する簡単な言語の文法の例を挙げなさい。ヒント: 授業の宿題の言語を考える。/ Given the grammar of an example of a simple language in (4) that cannot be generated by "left-right linear grammars". Hint: Think about languages in the homeworks of this lecture. (4 点)

例: 足し算と掛け算の文法: Exp → Exp + Term | Term; Term → Term * Num | Num

なぜ「左右線形文法」はコンパイラで使用されないかを説明しなさい。
Explain why "left-right linear grammars" are not used in compilers. (4 点)

コンパイラの字句解析の段階では正規言語で十分ですが、構文解析では上記の例のように、 文脈自由言語ではあるが、「左右線形文法」で生成できない、解析木が複雑にわかれる式などの処理が重要ですから。

コード生成と最適化 / Code Generation and Optimization (合計 24 点)

超単純アセンブリ言語は次のような命令を持つ / Very simple assembly language uses the following instructions:

メモリのアドレスは変数名 (小文字) で表す。レジスタは R1, R2,... で表し、数は無制限。被演算子の順番は結果を一番左側に書く。 / Memory addresses are expressed as variable names (lower case). Registers are expressed as R1, R2,... The number of registers is not limited.

この機械には割り算の命令がないので、下記の左側の普通の C 言語のプログラム断片は a を b で割った商を q、余り (剰余) を r に残す。これを制限された C 言語 (制御文は if と goto のみ、if 文の条件は 0 との比較のみ、if 文後は goto のみ) と最適化されていないアセンブリ言語に変換しなさい。
さらに、割り算の (あまり効率的でない) アルゴリズムを変更しないで、コンパイラ内から使える最適化されたコードを、 スタート時点で被除数が R1、除数が R2 にセットされている際に、剰余を R1、商を R2 に残すように作製しなさい。R1 と R2 以外に、使われるレジスタの値をスタック (変数 s1, s2,...) に保存し、最後にレジスタに戻しなさい。a も b も正の整数と仮定してよい。
Because this machine does not have a division instruction, the plain C code below leaves the quotient of a divided by b in q, and the remainder in r. Convert this code to restricted C (control statements limited to if and goto, conditions in if restricted to comparison with 0, if statement takes only goto) and non-optimized assembly.
In addition, create optimized code (not changing the division algorithm, which isn't very efficient itself) for use by the compiler, assuming that at the start, the dividend is available in R1 and the divisor in R2, and the remainder is left in R1 and the quotient in R2. Except for R1 and R2, save any registers you use on the stack (in variables s1, s2,...) and restore them at the end. You can assume that both a and b are positive integers.

  q = 0;
  while (a>=b) {
      a -= b;
      q++;
  }
  r = a;

    CONST   R1, 0
    STORE   q, R1
  next1:
    LOAD    R1, a
    LOAD    R2, b
    SUB     R1, R1, R2
    JUMP<   R1, endwhile
    LOAD    R1, a
    LOAD    R2, b
    SUB     R1, R1, R2
    STORE   a, R1
    LOAD    R1, q
    CONST   R2, 1
    ADD     R1, R1, R2
    STORE   q, R1
    JUMP    next
  endwhile1:

    LOAD    R1, a
    STORE   r, R1

    STORE   s1, R3
    STORE   s2, R4
    CONST   R3, 0
    CONST   R4, 1
  next1:
    SUB     R1, R1, R2
    ADD     R3, R3, R4
    JUMP>=  R1, next1
    ADD     R1, R1, R2
    SUB     R3, R3, R4
    LOAD    R4, s2
    SUB     R2, R2, R2
    ADD     R2, R2, R3
    LOAD    R3, s1

  q = 0;
next1:
  if (a-b<0) goto end1;
  a -= b;
  q++;
  goto next;
end1:
  r = a;

論理的な正規表現と実用的な正規表現 (18 点)

論理的な正規表現と実用的な正規表現は色々な面で違う。実用的な正規表現には存在するが、論理的な正規表現には存在しない機能を、論理的な正規表現でどの様に代用できるかを含め、四つ説明しなさい。 できるだけ異なる機能を選びなさい。/ Theoretical regular expressions and practical regular expressions differ in many aspects. Explain four features available in practical regular expressions but not in theoretical regular expressions, and what to substitute for them in theoretical regular exrpessions. (各/each 3 点)

. (ドット)： 任意の文字ひとつ。論理的な正規表現での書き方: (a|b|c|d|e|....)

文字クラス: [ABF-H] で多くの文字をコンパクトに表現。論理的： (A|B|F|G|H)

+: 一つ以上という意味。R+ は論理的に RR* と書けます。

?: 有るか無いかの選択肢。R? は論理的に ε|R と書けます。

実用的な正規表現にはあるが、論理的な正規表現で代用できない機能を一つ説明しなさい。/ Explain a feature available in practical regular expressions that does not have a substitute in theoretical regular expressions. (3 点)

^ (最初) や $ (最後) のアンカー。理論的な正規表現は必ず入力全てをマッチしますので不要。

論理的な正規表現にはあるが、実用的な正規表現に無い唯一の機能を説明しなさい。/ Explain the single feature that is available in theoretical regular expressions but not in pratcical regular expressions. (3 点)

ε (空語) である。ε は欧米のキーボードで書きにくいし、理解しにくい。? で代用可能。

動的コンパイル (10 点)

動的コンパイルの目的と仕組みを詳しく説明しなさい。/ Explain dynamic compilation in detail. (6 点)

動的コンパイルは実行時にコンパイルされたコードを再コンパイルすることで、実行速度を上げるのが目的です。 主に二つの場合に使われます。 一つ目は、仮想マシンのコードを実際のハードウェアの機械命令に再コンパイルすることです。これにより、 仮想マシンの命令をエムレートする必要が無くなり、実行速度が上がる。ある程度の回数で呼ばれている関数・メソッドが対象です。 二つ目は、頻繁に使われる引数の型や値 (例えば 0 や 1 など) のための専用なコードの作成です。 どこかで特殊な型や値かどうかの枝分れが必要が、その後、特殊のケースに限定されているコードで多くな最適化が可能かもしれませんので、 それによって高速化に貢献する。

授業で説明した、動的コンパイルの利点も問題点もよくわかる例を説明しなさい。/ Explain the example given in the lecture that shows both the advantages as well as the problems of dynamic compilation. (4 点)

Java の実装には殆どの場合、動的コンパイルが使われている。Java 言語は Java VM のコードにコンパイルされて配布されているが、その実行速度はあまり早くない。動的コンパイルによって実行速度が改善するが、 それが効くにはある程度時間がかかる。それによって、Java で書かれているアプリケーション (例: Eclipse IDE) は 立ち上がりのときには遅いが、その後どんどん早くなる。動的コンパイルを含まれている Java VM の一つの名前は HotSpot であるが、それもコールドからのスタートとなります。

flex と bison / flex and bison (合計 10点)

flex と bison の入力ファイルの構文を、共通点を中心に説明しなさい。
Describe the input files for flex and bison, concentrating on commonalities. (6点)

両方ともファイルが行頭の %% 二つで三つの部分に分かれている。以下にこれを示す。
第一部分には flex や bison の設定や後で使えるマクロと、C 言語の宣言やグローバル変数の定義がある。 C の部分は字下げなどで区別する必要がある。
%%
第二部分は中心です。左側 (行頭から) ルールがあり、そのルールに合致すると、右側にある C の断片が実行される。 flex の場合、ルールは正規表現です。bison の場合、ルールは文法の書換規則です。
%%
第三部分には main 関数をはじめ C の関数を書きます。

flex と bison を同時に使う場合、その使い方と動作を説明しなさい。
Explain how flex and bison are used together and work together. (4点)

main 関数は bison にある。bison でトークンの種類を %token で定義する。bison が字句解析のトークンを必要とするたびに flex を呼び出し、 flex がトークンの種類を return で返す。属性の型は YYSTYPE で、必要に応じて flex で yylval 変数に値を設定し、これを bison で使える。

下向き構文解析と上向き構文解析 / Top-down and bottom-up parsing (14点)

下向き構文解析と上向き構文解析に関する下記の表を埋めなさい。
Fill in the table below about top-down and bottom-up parsing.

有限オートマトンの状態の最低数 / Minimum Number of States in FSAｓ (12 点)

下記のそれぞれの言語について、受理する有限オートマトンの状態の最低数を書きなさい。
For each of the languages below, give the minimum number of states in an FSA recognizing the language.

語が aqfz 一つのみの言語 / language consisting only of the word aqfz 5

x が偶数個で y が奇数個の語の言語 / language with an even number of x and an odd number of y 4

正規表現 ttt* で定義された言語 / language defined by the regular expression ttt* 3

s が最低一つで、t が最低二つの語からなる言語 / language with at least one s and at least two t 6

正規表現 rp|sq* で定義された言語 / language defined by the regular expression rp|sq* 4

w の数が 3 の倍数かつ 5 で割ったときに余りが 2 による言語
language where the number of w is a multiple of 3 and has remainder 2 when divided by 5 15

チューリング機械の作成 / Constructing a Turing Machine (合計 24 点)

テープ状の 0 と 1 で与えられた二進数に 2 を足すチューリング機械を作る。
We construct a Turing machine that adds 2 to a binary number represented with 0 and 1 symbols on the tape.
詳細: テープはスタート時も終了時も二進数以外全て blank が入っている。スタート時にヘッドは二進数の右にある。終了時のヘッドの位置はどこでも構わない。状態には順に A, B,... のラベルを付けなさい。
Details: Both at the start and at the end of the computation, apart from the binary number, the tape shall only contain blanks. At the start, the head is placed to the right of the binary number. When the machine stops, the head can be anywhere. Label the states A, B,... in order.
ヒント: 二進数に 1 を足すチューリング機械とどう違うかを考えなさい。
Hint: Think about how this machine differers from a Turing machine that adds 1 to a binary number.

次の二つのテープの初期値に対し、それぞれの終了値を書きなさい。(2 点)

初期値: ␣10100␣ 終了値: ␣10110␣                  初期値: ␣10011␣ 終了値: ␣10101␣

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

  _ _ _ 1 1 1 1 _ _ _
              ↑A
  _ _ _ 1 1 1 1 _ _ _
            ↑B
  _ _ _ 1 1 0 1 _ _ _
          ↑B
  _ _ _ 1 0 0 1 _ _ _
        ↑B
  _ _ _ 0 0 0 1 _ _ _
      ↑B
  _ _ 1 0 0 0 1 _ _ _
    ↑C

[図省略]
 
 
 
 
 
 
 
 
 
 
 
 

上記のチューリング機械の状態遷移表を書きなさい。
Write the state transition table of the above Turing machine. (8 点)