青山学院大学

前期試験 ・ 2006 年 7 月 28 日 2 時限実施 ・ ページ

授業
科目		 言語理論とコンパイラ 学生番号 学科 学年 組 番 フリ
ガナ		   評点
                   氏名    
担当者 DÜRST, Martin J.

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

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

字句解析: 文字一つ一つから字句 (例えば定数、要約語など) を作り出し、トークンとして構文解析に渡す。

構文解析: トークンの列を文法で分析し、構文木などを作り出す。

意味解析: 主に型が合っているかどうかのチェック。

コード生成: 構文木などからマシーンの命令を作り出す。

最適化: 構文木やマシーンの命令を分析し、もっと効率のいいものにする。

正規表現の作成 (10点)

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

説明正規表現
例a が偶数個の語の集合(aa)*
b が奇数個の語の集合 b(bb)*
c の数が三で割れる語の集合 (ccc)*
d が奇数個で e がゼロ個、又は e が偶数個で d がゼロ個の語の集合 d(dd)*|(ee)*
f の数が四で割って2か3になる語の集合 (ffff)*(ff|fff)
g が3個以上の後に h が偶数で2個以上 gggg*hh(hh)*
初めと終わり km で、その間任意の数の k と m の語の集合 km(k|m)*km
n が1個以上4個以下の語の集合 nn?n?n?
p が偶数で q が任意の数の語の集合 q*(pq*pq*)*
r と s が任意の数で、s が二つ以上続かない語の集合 r*(srr*)*s?
t が偶数で u が一個だけの語の集合 (tt)*(u|tut)(tt)*

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

構文解析には二つの根本的に違う方法がある。その二つの方法を列挙し、それぞれの利点と欠点を含めて簡単に説明しなさい。

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

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

前期試験 ・ 2006 年 7 月 28 日 2 時限実施 ・ ページ

コード生成 (10点)

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

命令 被演算子 説明 (コメント)
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 がある。

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

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

 if ((a>2 && b==3)
      || c<4)
 {
     d *= 5;
 }

         LOAD     R1, a
         CONST    R2, 2
         SUB      R1, R1, R2
         JUMP<=   R1, else
         LOAD     R1, b
         CONST    R2, 3
         SUB      R1, R1, R2
         JUMP==   R2, then
 
         LOAD     R1, c
         CONST    R2, 4
         SUB      R1, R1, R2
         JUMP>=   R1, else
then:    LOAD     R1, d
         CONST    R2, 5
         MUL      R1, R1, R2
         STORE    d, R1
else:

ゴミ集めの手法 (4点)

ゴミ集めの手法を二つ列挙し、簡単に説明しなさい。

参照を数える: メモリの部分ごとに、この部分が何回参照されているかを記録。数がゼロになったらメモリが返せる。

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

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

以下の表を完成しなさい。

字句解析 構文解析
解析対象 定数、識別子、予約語、演算子など 式、文、関数など
要点 速さ 能力
記述方法 正規表現 文脈自由文法
(自動) 解析手段 有限オートマトン プッシュダウンオートマトン

青山学院大学

前期試験 ・ 2006 年 7 月 28 日 2 時限実施 ・ ページ

授業
科目		 言語理論とコンパイラ 学生番号 学科 学年 組 番 フリ
ガナ		   評点
                   氏名    
担当者 DÜRST, Martin J.

英語の用語 (10点)

次の英語の用語の日本語訳を書きなさい。

Deterministic Finite Automaton: 決定性有限オートマトン

Regular Expression: 正規表現

Right Linear Grammar: 右線形文法

Token: トークン

Formal Language: 形式言語

Empty Word: 空語

Kleene Closure: クリーン閉包

Phrase Structure Grammar: 句構造文法

Parsing: 構文解析

State Transition Diagram: 状態遷移図

正規表現と有限オートマトン (8点)

ab|c* の正規表現を有限オートマトンに変更しなさい。

有限オートマトンの最小化 (6点)

次の状態遷移表の有限オートマトンを最小化し、結果を状態遷移図で示しなさい。

0 1
→A B C
*B B C
*C B C

前期試験 ・ 2006 年 7 月 28 日 2 時限実施 ・ ページ

線形文法と有限オートマトン (8点)

次の線形文法を有限オートマトンに変更し、その状態遷移図を示しなさい。ただし S を初期状態とする。

S → 0A
S → 0
S → 1C
A → 1B
B → 0A
B → 0
C → 1B
C → 1D
D → 1A
D → 1
D → 0B

文法の相違い (15点)

文法 A と B の両者を見比べて、それぞれのペアにおいて受理する言語や出来上がる構文木はどう違うのかを簡単に説明しなさい。例を使ってもよい。 NUM は整数のトークンで、一重引用符内の文字はその演算子のトークンを表す。

番号 文法 A 文法 B 解答 
exp → NUM '*' NUM
 
exp → exp '*' NUM
exp → NUM
 
 
 
 
 
 
 A の場合には一回の掛け算しかだめなのに、B では複数 (無限) の掛け算を許す。 
exp → exp '-' NUM
exp → NUM
 
exp → NUM '-' exp
exp → NUM
 
 
 
 
 
 
 A は左結合で、B は右結合 
exp → exp '+' NUM
exp → exp '*' NUM
exp → NUM
 
exp → exp '+' ter
exp → ter
ter → ter '*' NUM
ter → NUM
 
 
 
 
 A では + と * の優先度が同じくで、左から計算されるが、B では * が + より優先 
exp → exp '-' NUM
exp → NUM
 
sta → exp
exp → exp '-' NUM
exp → NUM
 
 
 
 
 
 A では式だけなので、一部の全体の区別が付かないが、B では全体に sta を定義して、例えば全体の式の結果を印刷するようにできる 
exp → exp '*' exp
exp → NUM
 
exp → exp '*' NUM
exp → NUM
 
 
 
 
 
 
 A は曖昧性があるが、B は曖昧性がありません。

青山学院大学

前期試験 ・ 2006 年 7 月 28 日 2 時限実施 ・ ページ

授業
科目		 言語理論とコンパイラ 学生番号 学科 学年 組 番 フリ
ガナ		   評点
                   氏名    
担当者 DÜRST, Martin J.

正規表現の説明 (8点)

次の flex で使われる正規表現とそれぞれの下で文字で示された部分を簡単に説明しなさい。

(([0-9]+(\.[0-9]*)?)|\.[0-9]+)([Ee][-+]?[0-9]+)?
  cccccccccccccccccc  dddddddd  eeeefffffgggggg
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbbbb

全体: 浮動小数点数の定数を認識する

a: 浮動小数点数の E 以前の部分を認識する。c と d のどちらか

b: 浮動小数点数の E とその後の部分 (En は *10n)

c: 一つ以上の数字の後に小数点とそれに続く数字が来るかむ知れません

d: 小数点の前に数字がないとその後に必ず一つ以上数字が来る必要がある

e: 大文字の E か小文字の e のどちらかの文字クラス

f: E の後の任意の符号

g: E の乗数@@@

正規表現の文法 (10点)

正規表現も形式言語と考えられる。正規表現の文法を書きなさい。トークンとして一般の文字を表す CHAR、演算子を表す '|'、'?'、'+' と '*'、そして '(' と ')' を使い、優先度が正しくなるようにしなさい。

RegExp  → RegExp '|' RegTerm
RegExp  → RegTerm
RegTerm → RegTerm RegFact
RegTerm → RegFact
RegFact → RegPart '?'
RegFact → RegPart '+'
RegFact → RegPart '*'
RegFact → RegPart
RegPart → '(' RegExp ')'
RegPart → CHAR

前期試験 ・ 2006 年 7 月 28 日 2 時限実施 ・ ページ

NFA から DFA への変換 (12点)

次の状態遷移表で定義された有限オートマトンを決定性有限オートマトンに変換し、その状態遷移図を書きなさい。
決定性オートマトンの状態のラベルに元のオートマトンの状態の集合をそのまま (書き換えを行わず) 使いなさい。

abε
→S{T, U}{T}{}
T{}{U, X}{}
U{V}{}{}
V{X}{T, X}{}
*X{}{}{Z}
Y{V, X}{}{}
Z{V}{Y}{}