コンパイラの主な処理 (5 点)

コンパイラが行う主な五つの処理を順番通りに列挙しなさい。

1. 字句解析
2. 構文解析
3. 意味解析
4. コード生成
5. 最適化

形式言語の表 (6 点)

次の表の空白を埋めなさい。

字句解析と構文解析 (5 点)

なぜコンパイラなどで字句解析と構文解析が分けられているかを簡単に説明しなさい。

字句解析は文字毎の処理なので効率が非常に大事。 正規表現・有限オートマトンで効率のよい実装ができる。構文解析には文脈自由言語が必要だが、 効率は少し落ちてもよい。全体に二つに分けると構造的にコンパイラが作れる。 (字句解析と構文解析は自然言語の単語の輸出と文の解析にも相当する。)

正規表現の作成 (6 点)

次の形式言語を受理する正規表現を作りなさい。使える記号は |, *, (, ) と ε である。

有限オートマトン (合計 25点)

次の遷移図で定義されている有限オートマトンがある。

(非決定性) 有限オートマトンの定義 (8 点)

(非決定性) 有限オートマトンは次の 5字組で定義されている: <Q, Σ, δ, q₀, F>。次の表にぞれそれの定義と上記の遷移図の 場合の値を記入しなさい。

DFA へ変換 (5 点)

上記の図の NFA を DFA に変更し、そのオートマトンの遷移図を示しなさい。

                             0
-> ( E ) --------> (( F )) -----> (( G ))
            1, 0      ^              |
                      |______________|
                             1

この問題は次ページに続く。

有限オートマトンの簡単化 (4 点)

前ページのオートマトンを簡単化しなさい。

          
    このオートマトンはそれ以上簡単化できません
         
                   
                   

オートマトンから文法への変換 (4 点)

前ページのオートマトンに相当する文法を作りなさい (NFA からでも DFA からでもよい)

E -> 1                          E -> 0
E -> 1 F                        E -> 0 F
F -> 0 G                        F -> 0
G -> 1                          G -> 1 F

以上のオートマトン・文法が受理する言語を言葉で説明しなさ合い (4 点)

1 や 0 一個の後に、0 を 前頭に 0 と 1 が交互に 0 記号以上来る。

正規表現から語の出現 (6 点)

次の表の正規表現に合う語を三つ例づつ記述しなさい。

エラー処理 (6 点)

コンパイラでの解析中のエラー処理は難しいとされている。よいエラー処理に要求されるものを三つ列挙しなさい。

1. 分かりやすいエラーメッセージを出す; 2. 一つだけではなく、複数のエラーを見つける; 3. 二次エラーをできるだけ出さない

簡単な文法を作る (bison 用) (合計 15 点)

Perl プログラム言語には文字列の足し算と掛け算みたいなものがある。足し算の演算子は "." (ドット) で、二つの文字列をつなぐ。掛け算の演算子は "x" で、左にある文字列 を右にある整数で繰り返すことになる。掛け算は足し算より優先で、結合は二つの演算とも左結合である。
例: ("aA" . "bB") x 2 . "c" x 3 の値は aAbBaAbBccc である。

この簡単な文法を受理して、式の値を計算するプログラムを bison で段階的に作る。そのために使えるものは 次のとおりである。

次のトークンが定義されていて、字句解析で識別される: DOT: ドット、 EKS: "x"、 STRING: 文字列、 INT: 整数、 OPENP: 始め丸括弧 CLOSEP: 終わり丸括弧。

実装のために string のデータ型と string concat(string, string); の二つの文字列をつなぐ関数と int i; の繰り返し用の変数が用意されている。(bison なので C 言語だが、文字列のメモリの用意は気にしなくてよい。)

例: 二つの文字列だけを足し算だけで結ばれる入力を扱うものは以下のようになる。

expr  : term { printf ("Result is: %s\n", $1); } ;
term  : STRING DOT STRING { $$ = concat ($1, $2); } ;

足し算を二つ以上できるように文法を拡張しなさい (5 点)

expr  : term { printf ("Result is: %s\n", $1); } ;
term  : term DOT STRING { $$ = concat ($1, $2); } ;
      | STRING { $$ = $1; }
      ;

掛け算と括弧を追加し文法を完成しなさい (10 点)

expr  : term { printf ("Result is: %s\n", $1); } ;
term  : term DOT factor { $$ = concat ($1, $2); } ;
      | factor { $$ = $1; }
      ;
factor: factor EKS INT { $$ = ""; for (i=0; i<$3; i++)
                                      $$ = concat($$, $1); }
      | OPENP STRING CLOSEP { $$ = $2; }
      | STRING { $$ = $1; }
      ;

bison の動作 (5 点)

次に bison -v で作られている file.output の 一部 (一つの状態についての情報) を示す。

state 17

   21 addExpression: mulExpression .
   22 mulExpression: mulExpression . '*' unaryExpression
   23              | mulExpression . '/' unaryExpression
   24              | mulExpression . '%' unaryExpression

    '*'  shift, and go to state 34
    '/'  shift, and go to state 35
    '%'  shift, and go to state 36

    $default  reduce using rule 21 (addExpression)

以上のファイルの一部を簡単に説明しなさい。

bison が作っている状態表の一つの状態の情報です。 分析の現在の現状は '.' で示されている。 mulExpression (因子) を認識したところで、次になにをするのかを決めるところです。 '*', '/' と '%' ではその演算子を shift して、それそれ 34, 35, 36 番の 状態に移る。それ以外のトーケンでしたら 21 番の文法規則を使って単独の mulExpression を addExpression として認識する。

コードの最適化の方法を五つ列挙しなさい (5 点)

1. 静式評価 (constant folding, 定数たたみこみ)
2. 定数伝播 (constant propagation)
3. 無用命令の削除 (dead code elimination)
4. 演算の変更
5. 命令の順番変更

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

次の機械命令を使って C のプログラムの部分のコードを生成しなさい。

Command  Operand      Comment
LOAD     a, R1        変数 a の値をレジスタ R1 に代入 
STORE    R1, a        レジスタ R1 の値を変数 a に代入 
CONST    5, R1        レジスタ R1 に 5 と言う定数を代入
JUMP     label        無条件のジャンプ
JUMP<    R1, label    レジスタ R1 が 0 より小さい時 label へジャンプ 
                            (同様に JUMP<=, JUMP==, JUMP!=, JUMP>= と 
                             JUMP> がある。) 
ADD      R1, R2, R3   R1 と R2 を足して R3 に代入。同じレジスタ 
                            を何回使ってもよい。 
SUB      R1, R2, R3   ADD と同様の引き算 (R1 から R2 を引く)

コード生成の例

 if (a > 2)
 {    
     b = a;
 }

 Label   Command  Operand

         LOAD     a, R1
         CONST    2, R2
         SUB      R1, R2, R2

 Label   Command  Operand

         JUMP<=   R2, endif
         STORE    R1, b
 endif                      

if - else のコード生成 (9 点)

左欄にある C のプログラム部分のコードを右の二欄に書きなさい。

 if (a > 2
     && b > 2)
 {
         b = a;
 }
 else if (b < 0)
 {
         a = b;
 }

         LOAD     a, R1
         CONST    2, R2
         SUB      R1, R2, R2
         JUMP<=   R2, else
         LOAD     b, R1
         CONST    2, R2
         SUB      R1, R2, R2
         JUMP<=   R2, else

         LOAD     a, R1
         STORE    R1, b
         JUMP     endif
 else    LOAD     b, R1
         JUMP>=   R1, endif
         LOAD     a, R1
         STORE    R1, b
 endif                     

この問題は次ページに続く。

for 文の最適化 (9 点)

次の非常に簡単な for 文の最適前のコードは表の左にある。このコードの最適化したものを表の右に書き込みなさい。 (ヒント: レジスタの数を増やし (例えば R1-R5)、有効に使う。繰り返し実行される命令は現在の 13個から 5個まで減らせる。繰り返しの外の命令は若干増えても大丈夫。) コメントは必要ない。

 for (i=0; i<100; i++)
     sum += i;

 Label   Command  Operand     Comment
         CONST    0, R1       i = 0
         STORE    R1, i
 next    LOAD     i, R2       i < 100
         CONST    100, R3
         SUB      R2, R3, R3
         JUMP>=   R3, endfor  i-100 >= 0
         LOAD     sum, R1     sum += i;
         LOAD     i, R2
         ADD      R1, R2, R2
         STORE    R2, sum
         LOAD     i, R1       i++;
         CONST    1, R2
         ADD      R1, R2, R2
         STORE    R2, i
         JUMP     next        continue
 endfor                       after loop

 Label   Command  Operand     
         CONST    0, R1       
         LOAD     sum, R2    
         CONST    100, R3    
         CONST    1, R5
 label1  SUB      R1, R3, R4 
         JUMP>=   R4, label2  
         ADD      R1, R2, R2 
         ADD      R1, R5, R1  
         JUMP     label1     
 label2  STORE    R2, sum    
         STORE    R1, i        

形式言語の例 (8 点)

次の言語の簡単な例をあげなさい。(ヒント: 決定可能と言うことは受理できる機械がつくれると言うこと)

正規言語

1 が二以上の後 0 が 0 以上続く語の集合

文脈自由言語であるが、正規言語ではない

b と c が同じ数でる語の集合

決定可能な形式言語であるが、文脈自由言語ではない

b が n この後 c が n 個、その後 d が n 個

形式言語であるが、決定可能ではない

将来の天気を表す語の集合