コンパイラとプログラミング言語 第 3 4 週 プログラミング言語の形式的な記述 2014 年 4 月 23 日 金岡晃
授業計画 第 1 週 (4/9) コンパイラの概要 第 8 週 (5/28) 下向き構文解析 / 構文解析プログラム 第 2 週 (4/16) コンパイラの構成 第 9 週 (6/4) 中間表現と意味解析 第 3 週 (4/23) プログラミング言語の形式的な記述 第 10 週 (6/11) Java 仮想マシンとその機械語 第 4 週 (4/30) プログラミング言語の形式的な記述 第 11 週 (6/18) 条件分岐文と繰り返し文のコード生成 第 5 週 (5/7) 第 6 週 (5/14) 第 7 週 (5/21) 字句解析の概要と非決定性有限オートマトン 決定性有限オートマトン 字句解析プログラム 中間試験 構文解析の概要 / 上向き構文解析 第 12 週 (6/25) 第 13 週 (7/2) 第 14 週 (7/9) (7/23-8/5) 関数呼び出しのコード生成 休講 休講 期末試験 1
コンパイラとプログラミング言語 復習 第 2 週コンパイラの構成 2
コンパイラの論理的な構成 コンパイラ フェーズ ソースプログラム 字句解析 構文解析 意味解析 最適化 コード生成 目的プログラム 中間情報 ( 中間語 名前表 ) 3
コンパイラの物理的な構成 論理的な構成とは一致しない 順序が異なるケースもある コンパイラ ソースプログラム 字句解析 構文解析 意味解析 最適化 コード生成 目的プログラム 省略されたりする 中間情報 ( 中間語 名前表 ) 複数行うケースもある 4
後置記法の表記例 中置記法 A+B*C-D 後置記法 ABC*+D- 中置記法 E*F+G/H 後置記法 EF*GH/+ 5
コンパイラとプログラミング言語 第 3 週 プログラミング言語の形式的な記述 6
本日の到達目標と概要 到達目標 バッカス記法 (BNF) の理解 構文図式の理解 概要 バッカス記法の基本 バッカス記法の拡張 バッカス記法の例 構文図式の概要 構文図式の事例 7
コンパイラの開発における重要なポイント コンパイラ ソースプログラム 字句解析 構文解析 意味解析 最適化 コード生成 目的プログラム 中間情報 ( 中間語 名前表 ) プログラム言語の文法の出来の良し悪しが最重要事項 言語の仕様範囲と文法を厳密に定める必要 文法の形式的な記述方式 バッカス記法 構文図式 8
バッカス記法 ALGOL60の文法記述のために開発された記法 構文 ( プログラム言語の文法や書式 ) を定義するための言語 言語を決める言語 であることからメタ言語ともいわれる バッカス記法 (Backus Normal Form) の名称 提案者の名前より バッカス-ナウア記法 (Backus-Naur Form) とも 省略してBNF あるいはBNF 記法と呼ばれることが多い 次の規則から生成することができる式はどれか というパターンで基本情報技術者試験に出題されることが多い 9
BNF 終端記号と非終端記号 終端記号 : これ以上は変換されない記号 例 )0-9 の数字 アルファベット ( 小文字 大文字 ) など 非終端記号 : 終端記号でないもの 後述する < と > で囲まれた要素 ( 構文要素 ) 基本的な記法 さまざまな応用があるが 基本的な記法は以下の 3 つ ::= この記号の左に来る非終端記号を右に来た表現で定義する または (or) を意味する < 構成要素 > < と > で囲まれたものにより構成要素であることを示す 10
BNF の基本的記法の例 (1) ::= この記号の左に来る非終端記号を右に来た表現で定義する または (or) を意味する < 構成要素 > < と > で囲まれたものにより構成要素であることを示す 上記 3 つの表現と終端記号 ( 数値 アルファベット 記号など ) を用いて 構文を定義する 例 < 数字 >::=0 1 2 3 4 5 6 7 8 9 数字 という構成要素は 0 から 9 までの数字のいずれか 1 文字である 11
BNF の基本的記法の例 (2) 例 < アルファベット >::=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 文字以上ならんだものである 12
BNF の基本的記法の例 (3) 問題例 次の 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 答え : ア 13
BNF の基本的記法の例 (4) 問題例 次の BNF で定義される <DNA> に合致するものはどれか <DNA> ::= < コドン > <DNA>< コドン > < コドン > ::= < 塩基 >< 塩基 >< 塩基 > < 塩基 > ::= A T G C ア.AC イ.ACGCG ウ.AGC エ.ATGC 14
BNF の拡張 基本的な記法 終端記号と非終端記号 <> ::= より柔軟に拡張 EBNF さまざまな拡張があるが 典型的なものとしては以下の 2 つがある {} {} の中の要素を 0 個以上並べたもの [] [] の中の要素を 0 個または 1 個書いたもの 15
BNF の記法例 <a 列 >::={a} a 列 という構成要素は a を 0 個以上並べたもの a, aa, aaa, aaaa はいずれも a 列である < 数字列 >::=< 数字 > < 数字 >< 数字列 > < 数字列 >::=< 数字 >{< 数字 >} これら 2 つは同じものを定義している 16
BNF の記法例 : 教科書 p.21, p.22(1) < ソースプログラム上の文字集合 >::=< 空白 > < 英字 > < 数字 > < 記号 > < 空白 >::=Δ < 数字 >::=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 17
BNF の記法例 : 教科書 p.21, p.22(2) < プログラム >::=[< 変数宣言 >; < 関数定義 >] < 関数定義 >::=< 返戻型 >< 識別子 >([< 変数宣言 >{,< 変数宣言 >}])< ブロック > < 変数宣言 >::=< 要素型 >< 識別子 > < ブロック >::= { {< 文 >} } < 文 >::=< 変数宣言 >; < 代入文 > < 手続き呼び出し文 > <if 文 > <while 文 > < ブロック > < 返戻文 > < 代入文 >::=< 識別子 >=< 式 >; < 手続き呼び出し文 >::=< 関数呼び出し >; <if 文 >::=if(< 条件式 >)< 文 > <while 文 >::=while(< 条件式 >)< 文 > < 返戻文 >::=return[< 式 >]; 18
BNF の記法例 : 教科書 p.21, p.22(3) < 式 >::=< 項 >{< 加減演算子 >< 項 >} < 項 >::=< 因数 >{< 乗除演算子 >< 因数 >} < 因数 >::=< 加減演算子 >< 因数 > (< 式 >) < 関数呼び出し > < 識別子 > < 整数 > < 関数呼び出し >::=< 識別子 >([< 式 >{,< 式 >}]) < 条件式 >::=< 式 >< 比較演算子 >< 式 > < 比較演算子 >::===!= > > = < < = < 加減演算子 >::=+ - < 乗除演算子 >::=* / < 返戻型 >::=< 要素型 > void < 要素型 >::=int 19
教科書 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
教科書 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
構文図式 BNF と記述能力は変わらないが 直感的な記載方法 : 終端記号 : 構成要素 : または : ループ 22
BNF と構文図式 (1) < 数字 >::=0 1 2 3 4 5 6 7 8 9 < 数字 > 23 0 1 2 3 4 5 6 7 8 9
BNF と構文図式 (2) < 文 >::=< 変数宣言 >; < 代入文 > < 手続き呼び出し文 > <if 文 > <while 文 > < ブロック > < 返戻文 > < 文 > 変数宣言 ; 識別子 = 式 ; 関数呼び出し ; if ( 条件式 ) 式 while ( 条件式 ) 文 ブロック return 式 ; 24
本日の到達目標と概要 到達目標 バッカス記法 (BNF) の理解 構文図式の理解 概要 バッカス記法の基本 バッカス記法の拡張 バッカス記法の例 構文図式の概要 構文図式の事例 25
関数定義 返戻型 int substitutiona ( ) { int a1002; a1002 = 100; return a1002; } 識別子 ブロック 変数宣言 代入文 いずれも文 返戻文 26
< 整数 >::=< 数字 >{< 数字 >} 数字 数字 数字 どっちでもいい < 識別子 >::=< 英字 >{< 英字 > < 数字 >} 英字 英字 数字 27
< 関数定義 >::=< 返戻型 >< 識別子 >([< 変数宣言 >{,< 変数宣言 >}])< ブロック > 返戻型識別子 ( ) ブロック 変数宣言 変数宣言, 28