正規表現と有限オートマトンの作成
Creation of regular expressions and finite automata (21 点)

次のそれぞれの条件を満たす言語を定義する正規表現と受理する有限オートマトンの遷移図を書きなさい(アルファベットは説明に明記された記号だけ、遷移図はできるだけ簡単なもの)
For each of the languages with the following conditions, write the corresponding regular expression and the transition diagram of the finite automaton that accepts this language (the alphabet in each case is limited to the letters appearing in the description, the transition diagram should be as simple as possible)

 q(qq)*
    
    
    
    
    
    
    
    

fx?x?g
    
    
    
    
    
    
    
    

ppp(pppp)*
    
    
    
    
    
    
    
    

(t+s+t*s|st+s|ss+t)(s|t)*
    
    
    
    
    
    
    
    

文法から決定性オートマトンへ
From Grammar to Deterministic Automaton (合計 26 点)

下記の文法を遷移図に変換しなさい / Convert the grammar below to a transition diagram (5 点)

ヒント： 受理専用の新状態 F を導入する / Hint: Introduce a new state F for acceptance only.

S → xA | yB
A → zS | z | εB
B → xC | zC
C → yA | yB | zC | x

上記の有限オートマトンを決定性のものに変換し、その遷移表を (状態の書換無し) で書きなさい / Convert the finite automaton above to a deterministic one, writing down its transition table (without rewriting states) (8 点)

決定性オートマトンへの変換の目的について説明しなさい
Explain the purpose of the conversion to a deterministic automaton (3 点)

決定性有限オートマトンの方は簡単なテーブルで実装でき、入力の処理速度が非常に速い

非決定性オートマトン N の状態の数を n とすると、対応する決定性オートマトン D の最大の状態の数とその理由を書きなさい / Assuming that a nondeterministic automaton N has n states, give the maximum number of states of the corresponding deterministic automaton D and its reason (4 点)

状態の最大数は 2ⁿ-1; 理由は、D の状態は N の状態の集合で、全てを考えると N の状態のベキ集合になるが、空集合は状態としてありえない

上記の文法に ε が含まれるが、右線形文法には ε がありえない。上記のような文法から ε を取り除ける方法を考えて、説明しながら、その結果の文法を書きなさい。
The grammar at the top of the page contains an ε, but right linear grammars do not allow that. Devise and explain a method to remove ε from such grammars, and give the resulting grammar (7 点)

全ての ε 遷移の書換規則 (例: A → εB) について、その左辺 (例: A) が右辺に現れる書換規則 (例: S → xA) 全てを見つけ、 そこに元の書換規則の右辺に変えた書換規則 (例: S → xB) を追加。最後にダブっている書換規則 (例： C → yB | yB) を取り除く。
文法: S → xA | xB | yB; A → zS | z ; B → xC | zC; C → yA | yB | zC | x

構文解析の仕組み / How Parsing Works (24 点)

下記の図はある入力の構文解析を10段階で示したものである。
The figure below shows 10 stages of parsing some input.

上記の構文解析に使われる文法を書きなさい / Write a grammar for the parsing above (4 点)

  Exp  → Term | Exp + Term;
  Term → num | Term * num

上記の文法を、'-' と '/'、そして '(' と ')' も普段の意味で使えるように拡張しなさい
Expand the grammar above to deal with '-' and '/', as well as '(' and ')', in their usual meaning (6 点)

  Exp  → Term | Exp + Term | Exp - Term
  Term → Fac | Term * Fac | Term / Fac
  Fac → num | ( Exp )

上記の木の種類の正式名称と目的を書きなさい / Give the term for the trees above, and their purpose: (3 点)

解析木、構文解析の研究、解析の途中経過の表現などに使われる

上記の構文解析で使われている一般的な方法と解析に使われたツールの名前を書きなさい
Give the name of the general parsing method used above and the name of a tool used for this method (2 点)

上向き構文解析; bison

そのツールの場合、図の 3→4、4→5、6→7、7→8 のそれぞれの移行に使われている操作の名前と説明を書きなさい / Give the name of, and explain, the operation in the transitions 3→4, 4→5, 6→7, and 7→8 above (3 点)

shift; 入力の終端記号を関連する状態とともにスタックに積み

上記と同様、2→3 や 8→9 などの移行で使われている操作について
Same as above for transitions such as 2→3 and 8→9 (3 点)

reduce; 複数の (非) 終端記号を、文法の書換規則と逆に、一つの非終端記号にまとめる

「導出」で図の段階の順番を説明しなさい / Explain the order of the stages above using "derivation" (3 点)

上向き構文解析で、最右導出 (常に一番右の非終端記号を導出) の逆順で解析が行われる。

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

超単純アセンブリ言語は次のような命令を持つ (授業のものと違うところがあるので要注意)
Very simple assembly language uses the following instructions (caution: differences to version used in lecture):

メモリのアドレスは変数名 (小文字) で表す。レジスタは 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 言語のプログラム断片は m と n の積を t に残す。これを制限された C 言語 (制御文は if と goto のみ、if 文の条件は 0 との比較のみ、if 文後は goto のみ)、最適化されてないアセンブリ、最適化されたアセンブリに変換しなさい。
Because this machine does not have a multiplication instruction, the plain C code below leaves the product of m and n in t. 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), non-optimized assembly, and optimized assembly.

t = 0;
while (m > 0) {
    if (m & 1)
        t += n;
    m >>= 1;
    n <<= 1;
}

    CONST R1, 0
    STORE  t, R1
n1: LOAD   R1, m
    JUMP<= R1, e1
    LOAD   R1, m
    CONST  R2, 1
    ADD    R1, R1, R2
    JUMP== R1, f1
    LOAD   R1, t
    LOAD   R2, n
    ADD    R1, R1, R2
    STORE  t, R1
f1: LOAD   R1, m
    CONST  R2, 1
    SHR    R1, R1, R2
    STORE  m, R1
    LOAD   R1, n
    CONST  R2, 1
    SHL    R1, R1, R2
    STORE  n, R1
     
     

    JUMP   n1
e1:

    CONST  R1, 1
    CONST  R2, 0; t
    LOAD   R3, m
    LOAD   R4, n
n1: JUMP<= R3, e1
    AND    R5, R3, R1
    JUMP== R5, f1
    ADD    R2, R2, R4
f1: SHR    R3, R3, R1
    SHL    R4, R4, R1
    JUMP   n1
e1: STORE  t, R2
    STORE  m, R3
    STORE  n, R4

    t = 0;
n1: if (m <= 0)
        goto e1;
    if (m&1 == 0)
        goto f1;
    t += n;
f1: m >>= 1;
    n <<= 1;
    goto n1;
e1:

形式言語の分類 (合計 24 点)

次の表の空白を埋めなさい / Fill in the blanks in the table (11 点)

上記の表の各行において、その行の言語に対してその行の文法の役割を専門用語で説明しなさい。/ Explain the relationship between language and grammar in each row of the above table in technical terms. (3 点)

文法を使って、言語に属する語を初期記号から書き換え規則を使って導出 (作成) できる。

上記の表の各行において、その行の言語に対してオートマトンの役割を専門用語で説明しなさい。/ Explain the relationship between language and automaton in each row of the above table in technical terms. (3 点)

オートマトンを使って、ある語がある言語に属するかどうか (受理できるかどうか) を判断できる。

上記の表で「言語」の代わりに使えるもっと正確な専門用語を書きなさい。/ Give a more precise term for "language" in the above table. (1 点)

言語族

具体例を上げながら、表の最後の二行がなぜ違うのかを説明しなさい。
Using a concrete example, explain why the last two rows of the table differ. (3 点)

左右対称の言語は、対称点の前の部分をスタックで記憶できるので、プッシュダウンオートマトンで受理できるが、記憶装置の無い有限オートマトンでは受理できない。

具体例を上げながら、表の一つの行について、まとまっているものを分けることが可能なところを説明しなさい。
Using a concrete example, explain where and how the things lumped into a single row in the table can be split further. (3 点)

プッシュダウンオートマトンで決定性なものより非決定性なものの受理能力が高いことによって、二行に小分けできるはず。

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

@@@@

世代別 GC / Generational Garbage Collection (合計 10 点)

世代別 GC の原理、利点、欠点をそれぞれ説明しなさい
Explain the working, advantage(s), and disadvantage(s) of generational garbage collection

原理 / Workings (5 点): データ項目を複数の世代に分ける。 できたばかりのものは若い世代で、その世代を頻繁に GC する。若い世代のデータ項目の平均寿命が非常に短いので、多くの項目を早めに回収できる。 一定回数回収できないものは古い方の世代に格上げされる。古い方の世代の項目は長生きするものが多いので、たまにしか GC しない。

利点 / Advantage(s) (2 点): 若い世代のを頻繁に GC することで、低い負担でメモリ使用量を抑えることが可能。

欠点 / Disadvantage(s) (2 点): 古い世代から新しい世代への参照のところでは特別な注意が必要。

字句解析と構文解析の比較 / Lexical Analysis and Parsing (合計 12 点)

次の表の空白を埋めなさい / Fill in the blanks in the table below (6 点)

字句解析と構文解析を分けないでまとめて実装するやり方もあります。その場合の利点や問題点などを考えて説明しなさい。 / Implementations that do not separate but combine lexical analysis and parsing also exist. Think about and explain the advantages and problems for such an approach. (6 点)

利点は、ツール (例えば bison のみ) やファイルの数が減って、文法の違い (正規表現 vs. 書換規則) などに気を付けなくてよいし、言語の使用全般をまとめて一望できる。
欠点は、正規表現を書換規則で書くと記述が長くなるし、一文字一文字にプッシュダウンオートマトンを動かしているので 実行も遅いし、高レベル (例: 関数) と低レベル (例: スペースの有無) を同時に考えるのは

形式言語の演算 / Operations on Formal Languages (10 点)

授業で習った五つの形式言語の演算を説明しなさい。二項演算のばあいは言語 X と Y, 単項演算の場合は言語 Z が被演算子の場合の結果を書きなさい。結果が無限になる場合、最小の五八つの語を列挙しなさい。
Explain the five operations on formal languages that were discussed in the course. For binary operations, give the result of using X and Y as operands. For unary operations, give the result of using Z as operand. If the result is of infinite size, list the five firsteight smallest words.
X={ab, bc}, Y={bc, cd}, Z={a, b, ac}

言語の和集合; {ab, bc, cd}

言語の積集合; {bc}

言語の差集合; {ab}

言語の連結; {abbc, abcd, bcbc, bccd}

クリーン閉包; {ε, a, b, aa, ab, ac, ba, bb}

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

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

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

Virtual machine: 仮想計算機; 移植性向上などのための仮想的な計算機

Start symbol: 初期記号; 文法の導出を開始する非終端記号

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

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

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

Parser generator: 構文解析器生成系; bison みたいに構文解析器を自動生成するツール

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

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

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

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

Constant Folding: 静式評価; プログラム内の定数だけからなる式のコンパイル時の評価