flex と bison の入力の区分け (9 点)

flex でも bison でも入力が %% で区切られた三つの部分からなる。上から順にそれぞれの内容や役割を説明しなさい。

全体に必要な設定と C プログラムに必要な宣言

トークンや文法の規則とその時に使われる C のプログラムの部分

C プログラム言語の関数 (main も含む)

書換規則の正規表現 (12 点)

文法の書換規則は形式言語ととらえる。文法の書換規則一個の正規表現を、下記の文法の種類ごとに作りなさい。
(被終端記号は [A-Z] で、終端記号は [a-z] で表し、その他の記号としては → だけ使える。正規表現の記述には |, *, (, ), と ε が使える。)

句構造文法 (Type 0): ([A-Z]|[a-z])([A-Z]|[a-z])*→([A-Z]|[a-z])([A-Z]|[a-z])*

文脈自由文法 (Type 2): [A-Z]→([A-Z]|[a-z])([A-Z]|[a-z])*

正規文法 (Type 3): [A-Z]→[a-z]([A-Z]|ε)

文法と意味 (4 点)

文法的に正しいが、意味を成さない英語の三つの単語の文を二つ書きなさい。

Houses eat music.

Bill costs water.

英語の用語 (20 点)

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

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

Concatenation operation: 連結演算; 二つの語をつないで新しい語を作る

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

Finite state automaton: 有限オートマトン; 状態の数が有限であるオートマトン

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

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

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

Assembly language: アセンブリ言語; 機械語に近いが、人間では未だ読めるプログラム言語

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

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

非決定性のプッシュダウンオートマトン (15 点)

決定性プッシュダウンオートマトンと非決定性プッシュダウンオートマトンの言語の受理能力について例を使って細かく論じなさい。

有限オートマトンと違って、プッシュダウンオートマトン (PDA) の場合、 決定性のものと非決定性のものの受理能力が違います。非決定性のものの受理能力の方が高いです。すなわち、非決定性 PDA で受理できるが、決定性 PDA で受理できない形式言語が存在します。例として次のものがあります: S → ε, S → aSa, S → bSb, すなわち 'a' と 'b' からなる左右対称の語の言語。 左右対処の語は PDA で受理するときに、真ん中まではスタックに記号をプッシュするが、その後はスタックから記号を取りますが、 例えば abababab... というような場合、実際に真ん中を過ぎてもここが真ん中であったということはその時点で決められない。 そのため、真ん中の可能な所ごとに分身を作って、分身ごとに別のスタックを管理する必要になる。実装上大変だが、 幸いながら情報テクノロジーで普通に処理する必要な形式言語では例えば括弧の '(' と ')' とかで左右の違い、 すなわち真ん中、がよく分かるものが普通。

コード生成 (15 点)

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

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

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

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

 switch (a+5)
 {
   case 7:
     b++;
     break;
   case 12:
     a = 8;
   default:
     b = a*3;
 }

        LOAD    R1, a
        CONST   R2, 5
        ADD     R2, R1, R2
        CONST   R3, 7
        SUB     R3, R2, R3
        JUMP!=  R3, case12
        LOAD    R3, b
        CONST   R4, 1
        ADD     R3, R3, R4
        STORE   b, R3

        JUMP    break
case12: CONST   R3, 12
        SUB     R3, R2, R3
        JUMP!=  R3, def
        CONST   R1, 8
        STORE   a, R1
def:    CONST   R2, 3
        MUL     R2, R1, R2
        STORE   b, R2
break:

有限オートマトンの作成 (20 点)

次のそれぞれの条件を満たす語の集合を受理する有限オートマトンの遷移図を書きなさい(アルファベットは説明に明記された記号だけ)。

解析木と構文木 (10 点)

構文解析で使われる解析木と構文木を a = (b+c)*d; を例として使って説明しなさい。

P → aQ
P → aR
P → bQ
Q → cR
Q → bS
R → aT
R → bS
S → a
S → aT
T → bR
T → c

Reading a token: Next token is token PLUS ()
Reducing stack by rule 6 (line 36):
   $1 = nterm term ()
-> $$ = nterm exp ()
Stack now 0
Entering state 6
Next token is token PLUS ()
Shifting token PLUS ()
Entering state 13
Reading a token: Next token is token NUM ()
Shifting token NUM ()
Entering state 1
Reducing stack by rule 10 (line 43):
   $1 = token NUM ()
-> $$ = nterm fac ()
Stack now 0 6 13