青山学院大学

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

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

正規表現の作成 (10点)

次の形式言語を受理する理論的な正規表現 （使える記号は |, *, ( と )) 又は実用化された正規表現を作りなさい。

説明 正規表現
理論的な正規表現
b の数が偶数の語の集合 (bb)*
c の数が4で割っての余りが2か3になる語の集合 (cccc)*(cc|ccc)
任意の数の母音の語の集合 (a|e|i|o|u)*
最初が g で最後が h で、g と h の数が任意で、h が二つ以上続かない語の集合 gg*(hgg*)*h
p が二個の後に q が奇数個、又は q が一個の後に p が偶数個の語の集合 ppq(qq)*|q(pp)*
実用化された正規表現
y の数が3以上で12以下の語の集合 y{3,12}
任意の数の母音の語の集合 [aeiou]*
z の数が7で割って2か3か4になる語の集合 (z{7})*(c{2,4})
k, g, d, t の子音と母音の音節の語の集合 [kgdt][aeiou]
x の数が 10, 20, 30, 40 の倍数の語の集合 ((x{10}){1,4})*

解析木の構築 (15 点)

下記のトークンの列が入力されるときに、下記の文法から bison で作った解析機における解析木の構築を途中経過を含め書きなさい。(num は数値、plus は '+', ast は '*' を表す。)

トークンの列： num plus num ast num

文法：

E → E plus T | T
T → T ast num | num
sequence of syntax tree fragments

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

文法の問題点 (20 点)

下記の引き算の式の文法はそれぞれ問題点を持っている。その問題点を説明しなさい。

初期記号は式を表す E、終端記号は整数を表す num と一重引用符で囲まれている文字がある。 24 - 13 - 17 は入力の式の例で、評価の結果は -6 になる。(*) のついた問題では実装に再帰的下向き構文解析が使われると仮定しなさい。

番号文法問題点
例 E → num '+' num 引き算のためではなく、足し算のための文法である
E → num '-' num 三つ以上の項の引き算はできない
E → E '-' E 終端記号 num は文法に現れないので式を導出でない
E → num '-' E | num 構文木が右に傾き、右結合で計算結果が正しくない
E → E '-' E | num 文法があいまいで、計算結果は一定ではない
(*) E → E '-' num | num 左再帰で、再帰的下向き構文解析で対応できない

一般の引き算でも使える再帰的下向き構文解析の文法を書きなさい。

E → num EE
EE → '-' num EE | ε

中間表現 (8 点)

コンパイラで使う中間表現の二つをそれぞれ説明しなさい。

名前表: 名前表では字句解析、構文解析で見つかった 型、変数、関数の名前、その種類、定義や宣言の場所、型、有効範囲、必要なメモリ、相対アドレスなどを記録。 同じ名前で有効範囲が違うこともあることの考慮も必要。

構文木： 構文木は構文解析の結果を、 必要ないトークン (例： 括弧類) を除去してプログラムの構造を抽象化した形で表す。
ノードごとに属性 (例： 式の評価値、レジスタなど) をつけることがよくある。

コードの最適化に使われる解析 (8 点)

コードの最適化に使われる二つの解析手法をそれぞれ説明しなさい。

制御うフロー解析ではプログラムを基本ブロックに 分ける。
各基本ブロックにおいて、最初だけが (ジャンプによる) 入り口、最後だけが出口になる。この基本ブロックでグラフを作る。

データフロー解析では制御うフロー解析の結果を利用し、 どこの変数の代入がどこの変数の値に影響を及ぼすかを分析する。

青山学院大学

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

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

ゴミ集めの理由 (8 点)

最近のプログラム言語はほとんど例外なくゴミ集めを実装している。その理由を細かく説明しなさい。

C/C++ みたいな低レベルの言語や昔出来た言語にはゴミ集めがなく、動的に
メモリが必要になる時に malloc などで用意しないといけない。誰がどこで返すか
はっきりしない、はっきりしても忘れると、メモリリークにつながる。まだ使ううちに返す
ときも再利用され、参照エラーになる。このようなエラーは、ある程度のツールを
使っても非常に見つけにくくて、プログラマに大変な苦労を強いられている。
計算機がどんどん速くなるので、ゴミ集めの形で自動化した方がよかった。

英語の用語 (20 点)

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

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

Parsing: 構文解析、トークンを入力として文の構成を解析する

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

Terminal Symbol: 終端記号、文法でもう書き換えられない記号 (構文解析の場合トークン)

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

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

State Transition Table: 状態遷移表、どの状態からどの入力の場合どの状態に遷移するかの表

Finite State Automaton: 有限オートマトン、状態の数 (とメモリ) が有限であるオートマトン

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

Empty Word: 空語、長さ0の語

形式言語の表 (12 点)

次の表の空白を埋めなさい。「書換え規則の形」では終端記号と非終端記号の組合せの列に α、β などを使いなさい。

文法 Type 言語 オートマトン 書換え規則の形
句構造文法 0 句構造言語 チューリング機械 α → β (制限なし)
文脈依存文法 1 文脈依存言語 線形拘束オートマトン αAβ → αγβ
文脈自由文法 2 文脈自由言語 プッシュダウンオートマトン A → β
正規文法 3 正規言語 有限オートマトン A → aB

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

有限オートマトンと flex (合計 36 点)

言語理論で定義されている有限オートマトンは flex で実装できる字句解析機で応用されている。その応用にあたって幾つかの留意点や変更点があるので、 それについて考える。.lex ファイルの真ん中の部分:

aaab?   { return B; }
aaa?c*  { return C; }
abd     { return D; }

が与えられたとする (B, C, D はトークン)。

最初と最後の正規表現に相当する (できるだけ簡単な) 有限オートマトンを書きなさい。 それぞれの受理状態の近くにそこで返すトークンを書きなさい。(各 3 点)

aaab? aaa?c* abd
A finite automaton for aaab? A finite automaton for aaa?c* A finite automaton for abd

三つの有限オートマトンの初期状態の重ね合わせでできる有限オートマトンを決定性有限オートマトンに変換し、 その決定性有限オートマトンの遷移図を書きなさい。それぞれの受理状態の近くにその状態で返すことが可能なトークンを書きなさい。(12 点)

A deterministic finite automaton for all three regular expressions

入力 abdaaabaaacaaccaadabeaaadaabe に対する flex で作った字句解析機の結果をトークンとトークンとして認識できなかった文字の列として書きなさい。(5 点)

DBCCCdabeBdCbe

作った DFA の一つの状態には返すことが可能なトークンが二つある。 実際にその状態でトークンを返すことになるとき、どちらのトークンを返すか、またその理由を書きなさい。(3 点)

B を返す。flex では長さが同じときには最初に書いたルールが優先。

flex が非決定性オートマトンを決定性オートマトンに変更する利用を説明しなさい。(4 点)

NFA の場合には同時に複数の状態にいることが可能で、処理がややこしくて遅い。 DFA の場合、同時に一つの状態にしかいないし、次の状態も簡単に決まる。実装が簡単で、素早い。

作った DFA の場合には止まったときに受理状態にいたらその状態に相当するトークンを返し、 非受理状態にいたらそこまでの文字列を出力すればよい。しかし一般的にはそれだけではうまくいかない。 aaab? の正規表現を aaa(bb)? に変更した場合、入力が aaab を例にとって対策を提案しなさい。(6 点)

この例の場合、一端受理状態を通過してから非受理状態にいく。 最後に通過した受理状態を記憶し、それに相当するトークンを返し、 そこから読込んだ文字を再読込みしながら初期状態から次の受理を開始すればよい。

青山学院大学

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

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

コード生成 (16 点)

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

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

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

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

 for (i=0; i<length; i++)
 {
     length -= i;
 }
 
        CONST   R1, 0
        STORE   i, R1
next:   LOAD    R1, i
        LOAD    R2, length
        SUB     R1, R1, R2
        JUMP>=  R1, end
        LOAD    R1, length
        LOAD    R2, i
 
        SUB     R1, R1, R2
        STORE   length, R1
        LOAD    R1, i
        CONST   R2, 1
        ADD     R1, R1, R2
        STORE   i, R1
        JUMP    next
end:

線形文法と文脈自由文法 (12 点)

線形文法、即ち左線形規則、右線形規則と定数規則の書換え規則を許す文法が正規文法の能力を超えていることを次のステップにそって証明しなさい。

正規文法で表せない言語を一つ選び、明記しなさい。

複数の a の後に同数の b が来る語の言語 (anbn)。

この言語がなぜ正規文法の表現力を超えているのか説明しなさい。

a の数を (幾らまでも) 数える必要があって、正規言語を受理する有限オートマトンで状態の数が有限なので不可能。

この言語を線形文法で表しなさい。

S -> aB | ε； B -> Sb