言語理論とコンパイラ

形式言語の表 (9 点)

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

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

文法規則の分類 (6 点)

次の文法規則を上記の表の型 (type) で分類しなさい。あくまでも規則だけで判断しなさい。上記の分類に入らない場合には X と書きなさい。

P → aPq, P → xP, xPq → xQaq, xxQa → xxQaa, Q → b 1

S → aA, S → b, A → aS 3

f → Gq, ε → b X

Q → xy, Q → aPb, P → xy 2

M → qqN, M → pqNM, qpqN → xpqN, NM → abc 0

X → Xa, X → Yb, Y → c 3

実用化された正規表と理論的な正規表現 (6 点)

次の理論的な正規表現を出来るだけ短い実用化された正規表現に置き換えてください。

qq* q+

aa|aaa|aaaa a{2,4}

m|n|o|p|q [m-q]

ε|x x?

a|na|n|ε n?a?

a|abb|abbc a(bbc?)?

コード生成 (12 点)

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

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

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

 while (a<100 || b>5)
 {
     b -= 1;
     a += 7;
 }

next:    LOAD     R1, a
         CONST    R2, 100
         SUB      R1, R1, R2
         JUMP<    R1, body
         LOAD     R1, b
         CONST    R2, 5
         SUB      R1, R1, R2
         JUMP<=   R1, end

body:    LOAD     R1, b
         CONST    R2, 1
         SUB      R1, R1, R2
         STORE    b, R1
         LOAD     R1, a
         CONST    R2, 7
         ADD      R1, R1, R2
         STORE    a, R1
         JUMP     next
end:

関数呼び出し (4 点)

関数の呼び出しの関係でスタックに置くものを四つ述べなさい。

戻り番地、引数、戻り値、前の関数フレームのベースポインタ、使われるレジスターの値を退避する一時変数、ローカル変数

プッシュダウンオートマトン (合計 12 点)

プッシュダウンオートマトンのシミュレーション (8 点)

次の状態遷移図のプッシュダウンオートマトンで、「aaabbccc」の入力の場合に遷移する状態とその時のスタックを下記の表で完成しなさい。

入力記号	状態	スタック (左が上)
	P	Z
a	P	AZ
a	P	AAZ
a	P	AAAZ
b	Q	AAAZ
b	Q	AAAZ
c	R	AAZ
c	R	AZ
c	R	Z
ε	S	Z

プッシュダウンオートマトンが受理する言語 (4 点)

上記のプッシュダウンオートマトンが受理する言語を説明しなさい。

a が一つ以上の後、b が一つ以上で、その後 c が a と同じ数。

英語の用語 (12 点)

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

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

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

Bottom-up Parsing: 上向き構文解析; 構文解析を下 (小さい部分) から上 (全体) へ向いて行う。

Symbol Table: 名前表; 関数名、変数名などを管理する表

Control Flow Analysis: 制御フロー解析; 最適化で処理の流れを分析してグラフで表す

Constant Propagation: 定数伝播; 最適化において、(変数に代入された) 定数を追っておいて、入れ換える

Nonterminal Symbol: 非終端記号; 文法でまだ書換ないといけない記号

Rewriting Rules: 書き換え規則; 文法において、初期記号から非終端記号経由で終端記号まで書き替える規則

再帰的下向き構文解析 (8 点)

ある言語を受理するために再帰的下向き構文解析という方法を使うことになった。その方法を説明し、その利点、欠点、そして名前の由来を述べなさい。

方法説明: 被終端記号ごとに関数一つを作ります。その関数の中で次々次のトークンを読み、それによって他の被終端記号を「担当」する関数を読んだり、関数から戻ったりする。

利点: 手作業でプログラムが書ける。一つの被終端記号に対しただ順番と選択だけではなく、繰り返しも同じ関数の中で扱える。

欠点: 手作業でプログラムを書かないといけない。左再帰は使えない。使える文法に制限がある (簡単なものではないとだめ)。

名前の由来: 文法の初期記号から始めるので、下向きになっています。ある被終端記号の書き替え規則の右側に、直接的又は間接的に同じ被終端記号がでたら、関数が再帰的に呼ばれることになるので「再帰的」。

エラー処理の難しさ (3 点)

なぜエラー処理が難しいのか三つの点を挙げてください。

1. エラー処理にはよい理論が無い、2. 正しいプログラムより間違ったプログラムが大変多い、3. 人間がしやすい間違いとしにくい間違えが区別できない。

DFA と NFA (4 点)

DFA と NFA がどう違うのか説明しなさい。

DFA にはエプシロン遷移が可能だが、NFA にはエプシロン遷移が無い。DFA では同じ入力記号に対して複数の状態に遷移が出来る (俗に言えば、分身が出来る) が、NFA ではたかだか一か所にしか遷移が出来ない。

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

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

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

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

次の有限オートマトンを線形文法に変更しなさい。

S → aB | a | bC
A → bE | cE | aD | a | cD | c
B → cA | aE | bE
C → aA
D → bD | b | dD | d | cC | dC
E → cD | c | cE | dE

NFA と DFA (10 点)

上記の NFA を DFA に変更し、その状態遷移表を書きなさい (状態を書き替える必要は無い)。

	a	b	c	d
→{S}	{B}	{C}	{}	{}
{B}*	{E}	{E}	{A}	{}
{C}	{A}	{}	{}	{}
{E}	{}	{}	{D,E}	{E}
{A}	{D}	{E}	{D,E}	{}
{D,E}*	{}	{D}	{C,D,E}	{C,D,E}
{D}*	{}	{D}	{C}	{C,D}
{C,D,E}*	{A}	{D}	{C,D,E}	{C,D,E}
{C,D}*	{A}	{D}	{C}	{C,D}

正規表現の問題点 (8 点)

下記の正規表現は C プログラム言語の /* */ のコメントを一つマッチするために作られましたが、問題が多い。それぞれの正規表現の問題点 (例えばマッチしすぎるものやマッチしないもの) を簡単に説明しなさい。読みやすいために、コメントを /@ @/ に変更した。

/@.*@/ 複数のコメントをまとめてマッチ

/@([^@]|@+[^/])*@/ 一個目のコメントの終わりに @@/ があれば次のコメントも一緒にマッチ

/@@/ コメントの中に何も許されない。

/@ *@/ コメントの中にスペースしか許されない。

/@[a-zA-Z]*@/ コメントの中にローマ字しか許されない

/@([^@]|@+[^/@])*@+/ 問題はありません

/@.+@/ 空のコメント (/@@/) を許されない

/@[^@]*@/ /@@@/ をコメントとしてマッチしない

文法の作成 (10 点)

簡単な図形を定義する言語の文法を書きなさい。図形は 1 以上の線からなる。線は二つの点で定義されて、点と点の間には '---' 演算子があって、';' で終わる。点と点の足し算と引き算ができる。点を実数で掛けたり、割ったりすることが出来る。普通の演算と同じように、足し算、引き算より掛け算、割り算の方が優先度が高いです。優先度を丸括弧 '(' と ')' で変更出来る。点は '[' と ']' で囲んだ、',' で区切った二つの実数で表される。

トークンとして実数を表す NUM、演算子の '+'、'-'、'*'、'/' と '---'、括弧類の '('、')'、'['、と ']'、そして ';' を使い、優先度が正しくなるようにしなさい。

言語の実例:

[0, 0] --- [20.3, 20]; [50 , 30]*3 - [23.32, 40] --- ([300, 500]-
  [20, 70])/100 + [80, 60];

Drawing → Line Drawing
Drawing → Line
Line → Point '---' Point ';'
Point → Point '+' PointTerm
Point → Point '-' PointTerm
Point → PointTerm
PointTerm → PointTerm '*' NUM
PointTerm → PointTerm '/' NUM
PointTerm → PointFactor
PointFactor → '(' Point ')'
PointFactor → '[' NUM ',' NUM ']'

青山学院大学

形式言語の表 (9 点)

文法規則の分類 (6 点)

実用化された正規表と理論的な正規表現 (6 点)

コード生成 (12 点)

関数呼び出し (4 点)

青山学院大学

プッシュダウンオートマトン (合計 12 点)

プッシュダウンオートマトンのシミュレーション (8 点)

プッシュダウンオートマトンが受理する言語 (4 点)

英語の用語 (12 点)

再帰的下向き構文解析 (8 点)

エラー処理の難しさ (3 点)

DFA と NFA (4 点)

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

青山学院大学

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

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

NFA と DFA (10 点)

正規表現の問題点 (8 点)

文法の作成 (10 点)