コンパイラとプログラミング⾔語

コンパイラとプログラミング⾔語

第

9

2013年6⽉12⽇

⾦岡 晃

授業計画

第

1

(4/10)

コンパイラの概要 第

2

(4/24)

コンパイラの構成 第

3

(5/1)

プログラミング⾔語の形式的な 記述

第

4

(5/8)

字句解析の概要と⾮決定性有限 オートマトン

第

5

(5/15)

決定性有限オートマトン・字句 解析プログラム

第

6

(5/22)

中間試験 第

7

(5/29)

構⽂解析の概要

/

第

8

(6/5)

下向き構⽂解析

/

第

9

(6/12)

中間表現と意味解析 第

10

(6/19)

Java

11

(6/26)

条件分岐⽂と繰り返し⽂の コード⽣成

第

12

(7/3)

関数呼び出しのコード⽣成 第

13

(7/10)

休講

(7/24 or  7/31)

期末試験

【復習】第 8 週

下向き構⽂解析 / 構⽂解析プログラム

コンパイラとプログラミング⾔語

コンパイラの論理的な構成

プログラムソース ⽬的

プログラム

コンパイラ

字句解析 構⽂

解析 意味

解析 最適化 コード

⽣成

中間情報（中間語、名前表）

フェーズ

構⽂解析

• 字句解析が出⼒したトークンを読み込みながら、そのトークンの列 がプログラム⾔語の⽂法で許されているパターンと合うかを解析す る

プログラムソース 字句解析 トークントークン 構⽂解析

構⽂⽊

構⽂⽊

名前表

•

•

構⽂解析法

上向き構⽂解析法

（bottom-up parser)

下向き構⽂解析法

（top-down parser)

⼊⼒した記号列が構⽂規則の 右辺と⼀致した場合に左辺の 記号に置き換えていく

記号列として次に何が来るの かを仮定しながら構⽂解析を

進めていく _{a ＊ ( b + c )}

名前 名前

因⼦

項 式

名前 因⼦

項 式

因⼦

項

因⼦

項

上向き 式

解析法構⽂

下向き構⽂

解析法

左再帰的に記述されていると 解析が⾏えない場合がある

下向き構⽂解析の問題点（１）

左再帰性の問題 左再帰性：

⽣成規則の左辺の記号が右辺の最 左の記号になっている

左再帰性のある構⽂規則の例

<式> ::= <項> | <式>+<項>

<項> ::= <因⼦>| <項>＊<因⼦>

<因⼦> ::= <名前>|(<式>)

<名前> ::= a|b|c

解析時に無限にループしてしまう

下向き構⽂解析の問題点（２）

効率が悪くなる バックトラック

（後戻り）

なぜ起こるか？

構⽂規則

<S> ::= a<A>bd

<A> ::= cb|c

双⽅のケースが

同じ終端記号（ここでは

”c”

対策の1つ 括り出し：

共通の部分を別の規則で 独⽴させる

<S> ::= a<A>bd

<A> ::= c<B>

<B> ::= b|ε

“ε”

する

LL 構⽂解析

⼊⼒された記号列の先頭（最も左）の⾮終端記号に適⽤すべき

⽣成規則を、それ以降の記号列を調べることによって⼀意に決 定することが可能となるようにする

LL： Left to right scan

Left most derivation

LL(k)構⽂解析

先読み記号を最⼤k個まで許すことを意味する

k=1 のとき、バックトラックのない下向き構⽂解析が可能。

そのとき、LL(1)構⽂解析を可能にする⽂法をLL(1)⽂法という

LL(1) ⽂法

与えられた⽂法Gに対する任意の⽣成規則

<A> ::= | |…|

に対してDirector(

A,

∩

A,

First集合

First( ) = {

| ∈ ,

⇒ ⋯

⇒

∈

Director集合

Follow( ) = {

| ∈ ,

⇒ ⋯ ⋯

Director(

,

| ∈ , ∈

⇒

∈

終端記号の集合は

第 9 週

中間表現と意味解析

コンパイラとプログラミング⾔語

本⽇の到達⽬標と概要

• 到達⽬標

– 構⽂解析の中間出⼒としての構⽂⽊と四つ組の理解 – 意味解析の概要理解

– 名前表への検索⼿法の理解

• 概要

– 四つ組と構⽂⽊

– 意味解析

– 名前表と探索

• 線型探索

• ⼆分探索

• ハッシュ法

構⽂解析とその出⼒

• 字句解析が出⼒したトークンを読み込みながら、そのトークンの列 がプログラム⾔語の⽂法で許されているパターンと合うかを解析す る

プログラムソース 字句解析 トークントークン 構⽂解析

構⽂⽊

構⽂⽊

名前表

•

•

構⽂解析法

上向き構⽂解析法

（bottom-up parser)

下向き構⽂解析法

（top-down parser)

⼊⼒した記号列が構⽂規則の 右辺と⼀致した場合に左辺の 記号に置き換えていく

記号列として次に何が来るの かを仮定しながら構⽂解析を

進めていく _{a ＊ ( b + c )}

名前 名前

因⼦

項 式

名前 因⼦

項 式

因⼦

項

因⼦

項

上向き 式

解析法構⽂

下向き構⽂

解析法

構⽂⽊の表現⽅法：⼆分⽊と四つ組

• ⼆分⽊

– ⼆項演算⼦から成る式や代⼊⽂で利⽤される

– 演算⼦というノード（節点）が 2 つの⼦を持つ。

– 2 つの⼦がオペランド

– 変数や定数は⼦を持たない（葉ノード）

• 四つ組

– 演算⼦、 2 つのオペランド、演算結果の保管先アドレス、という 4 つのデータを 1 つの組として保管する⽅法

– ⼆分⽊に⽐べ、メモリ消費が少ない

=

a +

+ b ^{c tmp#1}

= tmp#1 ^a

⼆分⽊による構⽂⽊表現

• ⼆項演算⼦から成る式や代⼊⽂で利⽤される

• 演算⼦というノード（節点）が 2 つの⼦を持つ。

• 2 つの⼦がオペランド

• 変数や定数は⼦を持たない（葉ノード）

d=a*(b+c)

=

d *

a +

b c

z=y+1/(x‐1)

=

z +

y /

1 ‐

x 1

例：⼆分⽊を拡張する

• ⼆項演算⼦以外にも適⽤できる ようにする

– 3 項以上も O.K.

– 関数呼び出しにも対応

• call というノードで「関数 を呼び出す」を⽰す

• call の左の⼦ノードが「関 数名」

• call の右の⼦ノードを arg_vector というノード にし、その⼦ノードに

「引数」がくるようにす る

y+find_max(a+b, c, 0)/(x‐1)

y /

call

find_max arg_vector

+ c

a b

0

‐

x 1

+

四つ組

• 演算⼦、 2 つのオペランド、演算結果の保管先アドレス、という 4 つの データを 1 つの組として保管する⽅法

1. 演算⼦の情報

2. 第 1 オペランドの情報 3. 第 2 オペランドの情報 4. 演算結果の保存先

• ⼆分⽊に⽐べ、メモリ消費が少ない

+ b c tmp#1

* a tmp#1 tmp#2

= tmp#2 d

d=a*(b+c)

=

d *

a +

b c

四つ組の例

z=y+1/(x‐1)

=

z +

y /

1 ‐

x 1

‐ x 1 tmp#1

/ 1 tmp#1 tmp#2

+ y tmp#2 tmp#3

= tmp#3 z

コンパイラの論理的な構成

プログラムソース ⽬的

プログラム

コンパイラ

字句解析 構⽂

解析 意味

解析 最適化 コード

⽣成

中間情報（中間語、名前表）

フェーズ

意味解析

• 名前表を利⽤したエラーチェック

– ある識別⼦がプログラム中に現れたときに、構⽂的には正しく ても、意味が不明になるケースが現れたらエラーを返す

• 例

– データ宣⾔部の処理に、同じ名前を複数回宣⾔していないかと いう⼆重宣⾔のチェック

– 実⾏部の処理に、宣⾔されていない名前を⽤いてないかの チェック

– 代⼊の場合、左辺は利⽤可能な名前かどうかのチェック

– 演算や代⼊処理に合わせて型の整合をとるためのチェック

名前表

• ソースプログラム中のデータ宣⾔部より、ユーザが名前を付けた変 数や配列、関数についての情報がまとめられた表

• 書かれる情報例

– 形式：変数、配列、関数、ユーザ定義型など – 型：整数、実数、⽂字列、ポインタなど

– 語⻑： 1 バイト、 4 バイト、 8 バイト – 種類：グローバル、仮引数

– メモリ上の番地

– …

1 a int 12 4

2 b int 16 4

3 c int 20 4

4 d int 24 4

5 $wk1 int 28 4

6 $wk2 int 32 4

フェーズ概要：ソースプログラム

int a,b,c,d;

a=b+c*d;

回）

4/24

2

の資料より

フェーズ概要：字句解析

int a,b,c,d;

a=b+c*d;

予約語

int

a

b

c

名前

d

記号コンマ 記号コンマ

記号コンマ 記号セミコロン

記号セミコロン

名前

a

b

c

名前

d

記号等号 記号加算

記号乗算 字句解析

回）

4/24

2

の資料より

フェーズ概要：構⽂解析

予約語

int

a

b

c

名前

d

記号コンマ 記号コンマ

記号コンマ 記号セミコロン

名前表に登録 エントリ番号 名前 データ型 番地 領域⻑

1 a int 12 4

2 b int 16 4

3 c int 20 4

4 d int 24 4

5 $wk1 int 28 4

6 $wk2 int 32 4

回）

4/24

2

の資料より

フェーズ概要：構⽂解析

記号セミコロン

名前

a

b

c

名前

d

記号等号 記号加算

記号乗算

中置記法から後置記法に変換

名前

a

b

c

d

4/24

2

の資料より

フェーズ概要：意味解析

名前を名前表と照合し、エントリ番号に置き換え 算術式を複数の演算に分解

乗算 名前表＃

3

4

5

2

5

6

1

6

回）

4/24

2

の資料より

名前表と検索

•

•

–

•

•

1 2 ⁄

•

–

•

•

•

log 1 –

•

•

–

•

•

1

本⽇の到達⽬標と概要

• 到達⽬標

– 構⽂解析の中間出⼒としての構⽂⽊と四つ組の理解 – 意味解析の概要理解

– 名前表への検索⼿法の理解

• 概要

– 四つ組と構⽂⽊

– 意味解析

– 名前表と探索

• 線型探索

• ⼆分探索

• ハッシュ法