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

(1)

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

第3・4週プログラミング言語の形式的な記述

2014年4月23日金岡晃

(2)

授業計画

1

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

期末試験

2014/4/23 コンパイラとプログラミング言語

(3)

【復習】第 2 週コンパイラの構成

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

2 ^2014/4/23 コンパイラとプログラミング言語

(4)

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

3

ソース

プログラム目的

プログラムコンパイラ

字句解析

構文解析

意味

解析最適化コード生成

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

フェーズ

(5)

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

4

ソース

字句解析

構文解析

意味

論理的な構成とは一致しない

省略されたりする

順序が異なるケースもある

複数行うケースもある

(6)

後置記法の表記例

•

中置記法

A+B*C-D

•

後置記法

ABC*+D-

•

中置記法

E*F+G/H

•

後置記法

EF*GH/+

5

(7)

第

3

週

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

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

(8)

本日の到達目標と概要

•

到達目標

–

バッカス記法（

BNF

）の理解

–

構文図式の理解

•

概要

–

バッカス記法の基本

–

バッカス記法の拡張

–

バッカス記法の例

–

構文図式の概要

–

構文図式の事例

(9)

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

8

ソース

字句解析

構文解析

意味

プログラム言語の文法の

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

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

文法の形式的な記述方式

• バッカス記法

• 構文図式

(10)

バッカス記法

• ALGOL60

の文法記述のために開発された記法

–

構文（プログラム言語の文法や書式）を定義するための言語

•

「言語を決める言語」であることからメタ言語ともいわれる

•

バッカス記法（

Backus Normal Form

）の名称

–

提案者の名前より

–

バッカス

-

ナウア記法（

Backus-Naur Form

）とも

–

省略して

BNF

、あるいは

BNF

記法と呼ばれることが多い

9

「次の規則から生成することができる式はどれか。」というパターンで基本情報技術者試験に出題されることが多い

(11)

BNF

•

終端記号と非終端記号

–

終端記号：これ以上は変換されない記号

•

例）

0-9

の数字、アルファベット（小文字、大文字）など

–

非終端記号：終端記号でないもの。後述する

”<“

と

”>”

で囲まれた要素（構文要素）。

•

基本的な記法

–

さまざまな応用があるが、基本的な記法は以下の

3

つ

10

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

<構成要素>

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

“<“と”>”で囲まれたものにより構成要素であることを示す

(12)

BNF

の基本的記法の例（１）

11

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

<構成要素>

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

“<“と”>”で囲まれたものにより構成要素であることを示す上記3つの表現と終端記号（数値、アルファベット、記号など）を用いて、

構文を定義する例

<数字>::=0|1|2|3|4|5|6|7|8|9 「『数字』という構成要素は0から9 までの数字のいずれか1文字である」

(13)

BNF

の基本的記法の例（２）

12

例

<アルファベット>::=a|b|c|d|e|f|g|h|i|j|k|l|m|n|o|p|q|r|s|t|u|v|w|x|y|z

「『アルファベット』という構成要素はaからzまでの文字のいずれか1文字である」

この例では大文字A,B などは「アルファベットではない」

と定義されている

<数字列>::=<数字>|<数字><数字列>

「『数字列』という構成要素は数字または数字と数字列を並べたものである

定義の中に定義されるものが含まれている

「『数字列』という構成要素は数字が 1文字以上ならんだものである

(14)

BNF

の基本的記法の例（３）

13

問題例次のBNFで定義されるビット列Sであるものはどれか。

<S>::=01|0<S>1 ア、000111

イ、010010 ウ、010101 エ、011111

S

は

01

または

S

を

0

と

1

で挟んだもの

→ 01

と

0011

→ 0011

も

S

であるので、それを

0

と

1

で挟んだもの

000111

も

S

→ 00001111

も

S → 0000011111

も

S →…

答え：ア

(15)

BNF

の基本的記法の例（４）

14

次のBNFで定義される<DNA>に合致するものはどれか。

<コドン> ::= <塩基><塩基><塩基>

<塩基> ::= A | T | G | C ア．AC

イ．ACGCG ウ．AGC エ．ATGC 問題例

(16)

BNF

の拡張

•

基本的な記法

–

終端記号と非終端記号

– <>

– ::=

– |

•

より柔軟に拡張

→EBNF

–

さまざまな拡張があるが、典型的なものとしては以下の

2

つがある

15

{} {}の中の要素を0個以上並べたもの

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

(17)

BNF

の記法例

16

<a列>::={a} 「『a列』という構成要素はaを0個以上並べたもの a, aa, aaa, aaaa はいずれもa列である

<数字列>::=<数字>|<数字><数字列>

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

これら2つは

同じものを定義している

(18)

BNF

の記法例：教科書

p.21, p.22

（１）

17

<ソースプログラム上の文字集合>::=<空白>|<英字>|<数字>|<記号>

<空白>::=Δ

<数字>::=0|1|2|3|4|5|6|7|8|9

<英字>::=a|b|c|d|e|f|g|h|i|j|k|l|m|n|o|p|q|r|s|t|u|v|w|x|y|z|

A|B|C|D|E|F|G|H|I|J|K|L|M|N|O|P|Q|R|S|T|U|V|W|X|Y|Z

<記号>::=+|-|*|/|=|!|”<“|”>”|;|,|(|)|”{“|”}”

<語>::=<予約語>|<識別子>|<整数>

<識別子>::=<英字>{<英字>|<数字>}

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

<予約語>::=if|while|return|void|int

(19)

BNF

の記法例：教科書

p.21, p.22

（２）

18

<プログラム>::=[<変数宣言>;|<関数定義>]

<関数定義>::=<返戻型><識別子>([<変数宣言>{,<変数宣言>}])<ブロック>

<変数宣言>::=<要素型><識別子>

<ブロック>::=“{“{<文>}”}”

<文>::=<変数宣言>;|<代入文>|<手続き呼び出し文>|<if文>|<while文>|<ブロック>|<返戻文>

<代入文>::=<識別子>=<式>;

<手続き呼び出し文>::=<関数呼び出し>;

<if文>::=if(<条件式>)<文>

<while文>::=while(<条件式>)<文>

<返戻文>::=return[<式>];

(20)

BNF

の記法例：教科書

p.21, p.22

（３）

19

<式>::=<項>{<加減演算子><項>}

<項>::=<因数>{<乗除演算子><因数>}

<因数>::=<加減演算子><因数>|(<式>)|<関数呼び出し>|<識別子>|<整数>

<関数呼び出し>::=<識別子>([<式>{,<式>}])

<条件式>::=<式><比較演算子><式>

<比較演算子>::===|!=|”>”|”>”=|”<“|”<“=

<加減演算子>::=+|-

<乗除演算子>::=*|/

<返戻型>::=<要素型>|void

<要素型>::=int

(21)

教科書

p.21, p.22

の例を利用する

(1)

int a1001;

int substitutionA(){

int a1002;

a1002 = 100;

return a1002;

}

int substitutionB(int inputA){

int a1002;

a1002 = inputA;

return a1002;

}

20

(22)

教科書

p.21, p.22

の例を利用する

(1)

void callSubstitutionB(){

int a1003;

int a1004;

a1003 = 100;

a1004 = substitutionB(a1003);

return a1004;

}

int useIf(int inputA){

if(inputA > 100){

return 100;

}

return 0;

}

21

(23)

構文図式

• BNF

と記述能力は変わらないが、直感的な記載方法

22

：終端記号

：構成要素

：「または」

：ループ

(24)

BNF

と構文図式（１）

23

<数字>::=0|1|2|3|4|5|6|7|8|9

<数字>

0 1 2 3 4 5 6 7 8 9

(25)

BNF

と構文図式（２）

24

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

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

<文> _変数宣言

識別子 = ^式；

；

関数呼び出し；

if ( ^条件式 ) ^式

ブロック

return ^式；

条件式 ) 文

while (

(26)

本日の到達目標と概要

•

到達目標

–

バッカス記法（

BNF

）の理解

–

構文図式の理解

•

概要

–

バッカス記法の基本

–

バッカス記法の拡張

–

バッカス記法の例

–

構文図式の概要

–

構文図式の事例

(27)

26

int substitutionA ( ) { int a1002;

a1002 = 100;

return a1002;

}

関数定義

返戻型識別子

ブロック

変数宣言代入文

返戻文

いずれも文

(28)

27

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

数字

数字数字

どっちでもいい

<識別子>::=<英字>{<英字>|<数字>}

英字

英字数字

(29)

28

<関数定義>::=<返戻型><識別子>([<変数宣言>{,<変数宣言>}])<ブロック>

返戻型識別子 ( ) ブロック

変数宣言

変数 , 宣言

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

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

授業計画

【復習】第 2 週 コンパイラの構 成

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

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

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

後置記法の表記例

中置記法

後置記法

中置記法

後置記法

第

週

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

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

本日の到達目標と概要

到達目標

バッカス記法（

）の理解

構文図式の理解

概要

バッカス記法の基本

バッカス記法の拡張

バッカス記法の例

構文図式の概要

構文図式の事例

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

バッカス記法

の文法記述のために開発された記法

構文（プログラム言語の文法や書式）を定義するための言語

「言語を決める言語」であることからメタ言語ともいわれる

バッカス記法（

）の名称

提案者の名前より

バッカス

ナウア記法（

）とも

省略して

、あるいは

記法と呼ばれることが多い

終端記号と非終端記号

終端記号：これ以上は変換されない記号

例）

の数字、アルファベット（小文字、大文字）など

非終端記号：終端記号でないもの。後述する

と

で囲まれた 要素（構文要素）。

基本的な記法

さまざまな応用があるが、基本的な記法は以下の

つ

の基本的記法の例（１）

の基本的記法の例（２）

の基本的記法の例（３）

は

または

を

と

で挟んだもの

と

も

であるので、それを

と

で挟んだもの

も

も

も

の基本的記法の例（４）

の拡張

基本的な記法

終端記号と非終端記号

より柔軟に拡張

さまざまな拡張があるが、典型的なものとしては以下の

つがあ る

の記法例

の記法例：教科書

（１）

の記法例：教科書

（２）

の記法例：教科書

【復習】第 2 週コンパイラの構成

で囲まれた要素（構文要素）。

つがある