言語理論とコンパイラ

正規言語の表現方法 (合計 24 点)

正規言語にはｓ様々な表現方法がある。それぞれの方法を説明しなさい。 (各 3点)

DFA

NFA

正規表現

左線形文法

上記の表現が互いに変換可能である。二つの変換を選んで、例を使って細かく説明しなさい。(各 6点)

左線形文法から左線形文法への変換:

英語の用語 (10 点)

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

Symbol Table: 名前表；中間表現の一つ、変数、関数などについての情報を管理する

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

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

Concatenation Operation: 連結演算; 二つの語 (言語) をつないで新しい語 (言語) を作る

Formal Language: 形式言語、言語理論で文法で定義し、オートマトンで受理する言語

簡単な文法の作成 (12 点)

例えば bison にすぐ置き換えられる、電卓の式の簡単な文法を書きなさい。終端記号 (トークン) は NUM (整数の定数)、 PLUS ('+')、MINUS ('-')、ASTERISK ('*')、SLASH ('/')、LPAREN ('(')、RPAREN (')') に限定される。初期記号は expression (式)。非終端記号にはわかりやすい名前やその略を使用。結合や優先順位を間違えないように注意。

expression → expression PLUS term |
          expression MINUS term |
          term
term → term ASTERISK factor |
       term SLASH factor |
       factor
factor → NUM |
       LPAREN expression RPAREN

bison のエラー処理 (6 点)

bison の error トークンによるエラー処理を具体的に説明しなさい。

構文解析の主な方法 (12点)

構文解析には下向き構文解析と上向き構文解析の方法がある。それぞれの利点と欠点を含めて授業で習った一番幅広く使われる実装方法を使って細かく説明しなさい。

下向き構文解析: 下向き構文解析: 構文木を上から下へと作る。
利点は手作業でもプログラムが書ける (再帰的下向き構文解析)。
問題点は少し複雑になる文法だと対応が難しい。

上向き構文解析: 上向き構文解析: 構文木を下から上へと作る。
利点はもうちょっと幅広い文法に対応できる。
問題点は手書きでなかなか作りにくくて、bison みたいなツールが必要。

授業へのコメント (5 点)

この授業で一番分かりにくかったことを書きなさい。 (決まった正解はありません。)

この授業で一番勉強になったことを簡単に説明しなさい。 (決まった正解はありません。)

コード生成と最適化 (22 点)

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

命令	被演算子	説明 (コメント)
`LOAD`	`R1, a`	メモリの変数 `a` の値をレジスタ `R1` に代入
`STORE`	`a, R1`	レジスタ `R1` の値をメモリの変数 `a` に代入
`CONST`	`R1, 5`	レジスタ `R1` に定数 `5` を代入
`JUMP`	`label`	無条件に `label` へジャンプ
`JUMP<`	`R1, label`	レジスタ `R1` の値が `0` より小さい時 `label` へジャンプ (同様に `JUMP<=`, `JUMP==`, `JUMP!=`, `JUMP>=` と `JUMP>` がある。)
`ADD`	`R1, R2, R3`	`R2` と `R3` を足して `R1` に代入。同じレジスタを何回使ってもよい。同様に `SUB`、`MUL`、`DIV` がある。

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

メモリのアドレスは変数名 (小文字) で表す
被演算子の順番は結果を一番左側に書く (上記の例で R1)

コード生成 (12 点)

次のプログラムの断片を超単純アセンブリに書き換えなさい。ただし、レジスタは R1 と R2 だけ使いなさい。

 if (a==5 && b>3)
     c -= 7;
 else
     c -= 5;

        LOAD    R1, a
        CONST   R2, 5
        SUB     R1, R1, R2
        JUMP!=  R1, else
        LOAD    R1, b
        CONST   R2, 3
        SUB     R1, R1, R2
        JUMP<=  R1, else

        LOAD    R1, c
        CONST   R2, 7
        SUB     R1, R1, R2
        STORE   c, R1
        JUMP    end
else:   LOAD    R1, c
        CONST   R2, 5
        SUB     R1, R1, R2
        STORE   c, R1        
end:

最適化 (10 点)

上記ののプログラムの断片をできるだけ最適化しなさい。レジスタは三つ以上使ってよい。 (ヒント: 12個の命令と 3個のレジスタまで減らせる。実行される命令の数は一つぐらいしか減らない。)

        LOAD    R1, a
        CONST   R2, 5
        SUB     R1, R1, R2
        JUMP==  R1, end
        LOAD    R1, b
        CONST   R3, 3

        SUB     R1, R1, R3
        JUMP<=  R1, end
        CONST   R2, 7
end:    LOAD    R1, c
        SUB     R1, R1, R2
        STORE   c, R1

青山学院大学