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

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

第9週 中間表現と意味解析

2014年6月4日 金岡 晃

授業計画

第

1

(4/9)

コンパイラの概要 第

2

(4/16)

コンパイラの構成 第

3

(4/23)

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

第

4

(4/30)

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

第

5

(5/7)

字句解析の概要と非決定性有限 オートマトン、決定性有限オー トマトン・字句解析プログラム 第

6

(5/14)

中間試験 第

7

(5/21)

構文解析の概要

/

第

8

(5/28)

下向き構文解析

/

第

9

(6/4)

中間表現と意味解析 第

10

(6/11)

Java

11

(6/18)

条件分岐文と繰り返し文の コード生成

第

12

(6/25)

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

13

(7/2)

休講 第

14

(7/9)

休講

(7/23- 8/5)

期末試験

【復習】第 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;

第2回 の資料より

フェーズ概要：字句解析

int a,b,c,d;

a=b+c*d;

予約語 int 名前a 名前b 名前c

名前d

記号コンマ 記号コンマ

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

記号セミコロン

名前a 名前b 名前c

名前d

記号等号 記号加算

記号乗算 字句解析

第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

第2回 の資料より

フェーズ概要：構文解析

記号セミコロン

名前a 名前b 名前c

名前d

記号等号 記号加算

記号乗算

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

名前a 名前b 名前c 名前d 記号乗算 記号加算 記号等号 第2回

の資料より

フェーズ概要：意味解析

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

乗算 名前表＃

3

4

5

2

5

6

1

6

第2回 の資料より

名前表と検索

• 意味解析では、構文解析によって検出した名前を名前表で検索する必要がある

• 代表的な検索手法

– 線型検索

• 表の先頭から順に検索対象の文字列と等しいかを調べる方法

• 検索にかかる手間： 𝑛 + 1 2

• 実装が容易

– 二分検索

• 二分木を用意して検索

• 検索の効率は線型検索に比べて良い

• 検索にかかる手間：log₂ 𝑛 + 1 – ハッシュ表の利用

• 表のインデックス（それぞれのデータの番号）にハッシュ値を利用

• ハッシュ値：入力されたデータをハッシュ関数により値に変換 – 値の分布が一様

• 検索したい文字列をハッシュ関数にかけて得たインデックスを呼び出す

• 検索にかかる手間：1

本日の到達目標と概要

• 到達目標

– 構文解析の中間出力としての構文木と四つ組の理解 – 意味解析の概要理解

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

• 概要

– 四つ組と構文木

– 意味解析

– 名前表と探索

• 線型探索

• 二分探索

• ハッシュ法