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

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

第5週 字句解析の概要と非決定性有限オートマトン、

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

2014年5月7日 金岡 晃

授業計画

第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)

期末試験

【復習】第 3,4 週

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

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

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

ソース

プログラム 目的

プログラム コンパイラ

字句 解析

構文 解析

意味

解析 最適化 コード 生成

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

フェーズ

コンパイラの開発における重要なポイント

ソース

プログラム 目的

プログラム コンパイラ

字句 解析

構文 解析

意味

解析 最適化 コード 生成

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

プログラム言語の文法の

出来の良し悪しが最重要事項

→ 言語の仕様範囲と文法を厳密に定める必要

文法の形式的な記述方式

• バッカス記法

• 構文図式

バッカス記法（ BNF ）

•

–

•

0-9

–

”<“

”>”

::= この記号の左に来る非終端記号を右に来た表現で定義する

<構成要素>

| 「または（or）」を意味する

“<“と”>”で囲まれたものにより構成要素であることを示す {} {}の中の要素を0個以上並べたもの

[] []の中の要素を0個または1個書いたもの

構文図式

• BNF

：終端記号

：構成要素

：「または」

：ループ

構文図式

<文>::=<変数宣言>;|<代入文>|<手続き呼び出し文>|<if文>

|<while文>|<ブロック>|<返戻文>

<文>

変数宣言

識別子 = ^式 ；

；

関数呼び出し ；

if ( ^条件式 ) ^式

ブロック

return ^式 ；

コンパイラの開発における重要なポイント

ソース

プログラム 目的

プログラム コンパイラ

字句 解析

構文 解析

意味

解析 最適化 コード 生成

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

プログラム言語の文法の

出来の良し悪しが最重要事項

→ 言語の仕様範囲と文法を厳密に定める必要

文法の形式的な記述方式

• バッカス記法

• 構文図式

第

5

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

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

本日の到達目標と概要

•

–

–

–

•

–

–

–

–

–

–

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

ソース

プログラム 目的

プログラム コンパイラ

字句 解析

構文 解析

意味

解析 最適化 コード 生成

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

フェーズ

今日の内容

字句解析の概要

•

ソース

プログラム 目的

プログラム コンパイラ

字句 解析

構文 解析

意味

解析 最適化 コード 生成

トークン

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

字句解析の概要（２）

•

–

–

•

import java.io.*;

class Sample throws IOException{

public static void main(String[] args){

BufferedReader br = ….

}

} • 人間から見るとプログラム

• コンピュータから見ると文字列

import java.io.*;class Sample throws IOException{public static void main(String[] args){BufferedReader br = …. }}

import java

. io * ;

class Sample

throws IOException

public static ・・・

トークン

字句解析の流れ

ソース プログラム

字句解析

構文

文字（列） 解析

読み取り 字句

読み取り トークン

• 人間から見るとプログラム

• コンピュータから見ると文字列 ただの文字列

扱い

意味を持つ 要素に分割

分割されたトークンの集まりが 文法として間違っていないかチェック

（ここでBNFを使って定義された 文法と照らし合わせる）

文字読み取り / 文字列読み取り

•

–

1

1

正規表現の概要

•

–

1

1

–

例１ 人を呼ぶときの声 おい おーい

おーーい おーーー ーーーー ーーーー

ーーい

1つの表現で 表したい

おー*い

“

*

直前の文字が１個以上連続す る」という意味

正規表現があると何が便利か

• 検索で便利

– 「人を呼ぶ時の声」が書かれた文書を探したい…など

• コンパイラにも利用可能

– 字句解析時に、複数の表現方法をとり得るトークンを抽出する場合

<整数>::=<数字>{<数字>}

<数字>::=0|1|2|3|4|5|6|7|8|9 BFNによる文法定義

整数は1文字以上の数字が ならんだ文字列

1 73

59835 099 37

37 25680 整数の文字列集合

19750705 これは整数か？

¥d+

正規表現では

は0-9¥dまでの 数字

は直前の+ 文字が1個 以上連続す

ることを 示す

有限オートマトン

•

1. 状態の集合 𝑆 2. 入力文字の集合

3. 状態と記号の対を、次の状態の集合へ遷移する状態遷移関数 4. 𝑆 の特定の要素である開始状態 𝑆₀

5. 𝑆 の部分集合である最終状態 𝐹

：状態

：遷移

最終状態

有限オートマトンに入力し、

最終状態に到達するかを確認

有限オートマトンの利用によるチェック

開始状態

最終状態

19750705

これは整数か？

整数の

有限オートマトン

非決定性有限オートマトンと 決定性有限オートマトン

非決定性有限オートマトン

決定性有限オートマトン

ある状態・ある入力に対して遷移可能な状態を複数とるこ とができる有限オートマトン

遷移しなくてもよい状態や、1つの状態から 複数への遷移がある（非決定的）

非決定性有限オートマトンから非決定的な遷移を取り除いたもの

非決定性有限オートマトンと 決定性有限オートマトンの例

a(b|c)*

正規表現

最初にaが来て、

その後はbかcが無いか1個以上連続する a, abbc, ab, ac, abcbcc, abcc, …

ε

1 2 3 4

0

a ε

b

c ε

ε 非決定性有限オートマトン

決定性有限オートマトン

1 0

b a

ε：空列記号

正規表現のいくつかの表現

|

*

+

?

()

演習：次の非決定性有限オートマトンを正規表現 に変換せよ

第1問

2

0 b

a a 1

a

第2問

2

0 b

a a 1

a

来週は中間試験です

•

60

•

•

V

5103

•