言語理論とコンパイラ

有限オートマトンの作成と変換 (合計 16 点)

Σ = { a } の場合、次の語だけを受理する有限オートマトンの遷移図を書きなさい。

a の数が偶数 (3点)

a の数を 3で割ると余りが 2 (3点)

上記の二つの条件を同時に満たす非決定性有限オートマトンを作成しなさい。ヒント: 全体の初期状態ともとの二つの有限オートマトンの初期状態を ε 遷移でつなぐ。 (2点)

左記の NFA を DFA に変換し、その遷移表を書きなさい。状態の書き換えは必要ありません。(8点)

	`a`
→ *{A, B, D}	{C, E}
{C, E}	{B, F}
*{B, F}	{C, D}
{C, D}	{B, E}
*{B, E}	{C, F}
*{C, F}	{B, D}
*{B, D}	{C, E}

英語の用語 (16 点)

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

Syntactic Sugar: 糖衣構文; 本質的な機能ではなく利便性のための構文

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

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

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

Left Recursion: 左再起; 下向き構文解析で最左の非終端記号を繰返し展開し、無限の再帰

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

Kleene Closure: クリーン閉包; 語や言語を0回以上連結する

Right Linear Grammar: 右線形文法; A→aB (右線形規則) と A→a (定数規則) 限定の文法

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

例えば bison にすぐ置き換えられる、式の簡単な文法を書きなさい。終端記号 (トークン) は NUM (実数の定数)、 PLUS ('+')、ASTERISK ('*')、HAT ('＾'、べき乗演算)、LPAREN ('(')、RPAREN (')') に限定される。初期記号は expression (式)。非終端記号にはできる限りわかりやすい名前やその略を使用。結合 ('^' は右結合) や優先順位 ('^' は一番高い) を間違えないように注意。

expression → expression PLUS term
            | term
term       → term ASTERISK factor
            | factor
factor     → expbase HAT factor
            | expbase
expbase    → NUM
            | LPAREN expression RPAREN

導出と構文解析 (12点)

下記の導出方法、そしてその導出方法と構文解析方法の関係を細かく説明しなさい。

最左導出: 最左導出は文法の初期記号から解析木を作るときに、
常に一番左にある非終端記号の節を導出
(すなわち、文法規則を使って置き換える) する方法です。
下向く構文解析、特に再帰的下向き構文解析、
は最左導出と同じ順番で構文解析を行っている。

最右導出: 最右導出は最左導出と違って、常に解析木の一番右の節を展開する。
上向き構文解析、特に LALR 解析など
は最右導出の逆の順番で (全体の解析から見て左下から)
導出の逆 (reduce) の操作によって解析木を作り上げる。
途中で複数の部分木ができることが多い。

文法の導出 (12 点)

次の文法の二つの異なる導出を書いてください。(4 点)

文法: S → cba, S → cDTa, T → EDTa, T → EDa, DE → ED, cE → cc, Da → ba, Db → bb

S ⇒aba

S → cDTa → cDEDaa → cEDDaa → ccDDaa → ccDbaa → ccbbaa

上記の文法で定義されている言語を簡単に説明しなさい。(3 点)

言語は cⁿbⁿaⁿ (n>0)、すなわち一個以上で同数の c と b と a の語の集合である。

上記のような文法は、一般の構文解析機生成機では取り扱えない。その理由を説明しなさい。(5 点)

プログラム言語など情報テクノロジーで取り扱う言語では
「両側に対照的に囲む」 (例:式など) と「決まった順番で複数のものが来る
(例: if-else 文など) がよくあるが、囲むものだけではなく囲まれるその真ん中のものも
同じ数、という現象は一切使われません。

C 言語のコメントの正規表現 (@@8 点)

/@([^@]|@+[^/@])*@+/ は、読みやすさのために /@ @/ に変更した C 言語のコメントを一つマッチする正規表現である。それぞれの部分を説明しなさい。

/@ 先頭の /@

[^@] 文字クラス: @ 以外の文字一つ

@+ 一つ以上の @

[^/@] 文字クラス: @ と / 以外の文字一つ

@+[^/@] 一つ以上の @ の後に @ と / 以外の文字一つ

([^@]|@+[^/@]) 中身一文字または @ の場合、終わりでないことが確認できるまでの部分

([^@]|@+[^/@])* コメントの中身の繰り返し

@+/ 最後の @/、しかし複数の @ を含む

字句解析と構文解析の比較

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

	字句解析	構文解析
解析対象	定数、識別子、予約語、演算子など	式、文、関数など
要点	速さ	能力
記述方法	正規表現	文脈自由文法
演習で使ったツール	flex	bison
そのツールの前身	lex	yacc

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

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

@@@@

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

@@@@

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

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

命令	被演算子	説明 (コメント)
`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, R2,... で表し、数の制限は無い。被演算子の順番は結果を一番左側に書く。

コード生成の逆変換 (10 点)

次の超単純アセンブリ言語の断片を、普通の C 言語のプログラマが書くプログラムに変換しなさい (goto 無し)。

        CONST   R1, 5
        STORE   d, R1
label1: LOAD    R2, d
        CONST   R3, 100
        SUB     R2, R2, R3
        JUMP>=  R2, label3
        CONST   R1, 2
        LOAD    R2, d
        MUL     R1, R1, R2
        CONST   R2, 3

        ADD     R1, R1, R2
        LOAD    R2, a
        ADD     R1, R1, R2
        STORE   a, R1
label2: LOAD    R3, d
        CONST   R4, 7
        ADD     R5, R3, R4
        STORE   d, R5
        JUMP    label1
label3:

for (d=5; d<100; d+=7)
{
    a += d*2 + 3;
}

基本ブロック (5 点)

上記のプログラム断片を基本ブロックに分割し、結果を下記の表に記入しなさい (基本ブロックの数はあいている行の数以下)。

最初の行	最後の行	行の数
`CONST R1, 5`	`STORE d, R1`	2
`label1: LOAD R2, d`	`JUMP>= R2, label3`	4
`CONST R1, 2`	`STORE a, R1`	8
`label2: LOAD R3, d`	`JUMP label1`	5
`label3:`	`label3:`	1

最適化 (10 点)

上記のプログラム断片をできるだけ最適化しなさい。 (ヒント: 6個のレジスタを使って、全体は 13個の命令まで、繰り返し内は 6個の命令まで減らせる。)

        LOAD    R4, a
        CONST   R2, 5
        CONST   R3, 3
        CONST   R6, 7
        CONST   R5, 100 
cont:   ADD     R1, R2, R2
        ADD     R1, R1, R3

        ADD     R4, R4, R1
        ADD     R2, R2, R6
        SUB     R1, R2, R5
        JUMP<   R1, cont
        STORE   d, R2
        STORE   a, R4

形式言語の表 (合計 18 点)

次の表の空白を埋めなさい。 (9 点)

文法	Type	言語	オートマトン
句構造文法	0	句構造言語	チューリング機械
文脈依存文法	1	文脈依存言語	線形拘束オートマトン
文脈自由文法	2	文脈自由言語	プッシュダウンオートマトン
正規文法	3	正規言語	有限オートマトン

上記の表の各行において、その行の言語に対してその行の文法の役割を専門用語で説明しなさい。 (3 点)

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

上記の表の各行において、その行の言語に対してオートマトンの役割を専門用語で説明しなさい。 (3 点)

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

Type の大小関係によって行と行のそれぞれの言語の間に成り立つ関係を専門用語で説明しなさい。 (3 点)

Type の番号が小さい方の言語は番号の大きい方の言語をすべて含まれている。

ゴミ集めの手法 (8 点)

ゴミ集めの手法の一つを列挙し、細かく説明しなさい。

印掃式: メモリの部分ごとに印をつけて、これを初め off にして、たどれるメモリの部分の印を全て on にした後に off の部分を返す。

ゴミ集めの意義や目的を説明しなさい。

動的メモリの管理は例えば本格的な C 言語のプログラムにおいてプログラミングやディバッギングの多くの時間を必要とする。ゴミ集めによってこれが必要無くなるため、プログラミング効率が大分上がる。

名前表 (合計 10 点)

名前表が扱うデータを列挙しなさい。(6 点)

名前の種類 (変数、関数、型など)、定義か宣言だけか、変数、関数などの型、
名前が有効な領域 (例えば関数、ブロック)、変数などの場合: 大きさ (必要なメモリ)、関数、変数などの (相対) アドレス

名前表の二つの要点を説明しなさい。(4 点)

1. 使うことが多く、名前の数が多いので効率が大切
2. 同じ名前が複数ある可能性があるので区別が必要

青山学院大学

有限オートマトンの作成と変換 (合計 16 点)

英語の用語 (16 点)

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

導出と構文解析 (12点)

文法の導出 (12 点)

青山学院大学

C 言語のコメントの正規表現 (@@8 点)

字句解析と構文解析の比較

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

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

コード生成の逆変換 (10 点)

基本ブロック (5 点)

最適化 (10 点)

青山学院大学

形式言語の表 (合計 18 点)

ゴミ集めの手法 (8 点)

名前表 (合計 10 点)