ホーム » 「意思決定木」タグがついた投稿
タグアーカイブ: 意思決定木
AVLと意思決定木と演算子
前回、2分探索木へのデータ追加の説明と、演習課題を行っていたが、演習時間としては短いので、今日も前半講義で残り時間は演習とする。
2分探索木へのデータ追加と不均一な木の成長
先週の講義で説明していた、entry() では、データを追加すべき末端を探し、追加する処理であった。
しかし、前回のプログラムで、以下のような順序でデータを与えたら、どのような木が出来上がるであろうか？
- 86, 53, 11 – 降順のデータ
- 12, 24, 42 – 昇順のデータ
この順序でデータが与えられると、以下のような木が出来上がってしまう。このような木では、データを探しても1回の比較でもデータ件数が1つ減るだけで、O(N)となってしまう。通常のデタラメな順序でデータが与えられれば、木はほぼ左右均等に成長するはずである。
AVL木
このような、不均一な木が出来上がっても、ポインタの繋ぎ変えで検索回数を改善できる。例えば、以下のような木では、赤の左側に偏っている。(赤の左の枝は深さ=3段、青の枝は深さ=1段)
このような場合でも、最初、青の状態であっても、不均一な部分で赤のようなポインタの繋ぎ変えを行えば、2分探索木の要件を満たしたまま、木の段数を均一に近づけることができる。この例では、11,65,92の木が、右回転して 11 の木の位置が上がっている。(右回転)
この様に、左右の枝の大きさが不均一な場所を見つけ、右回転や左回転を行う処理を繰り返すことで、段数が均一な2分探索木に修正ができる。この様な処理でバランスの良い木に修正された木は、AVL木と呼ばれる。
理解確認
- 木の根からの段数を求める関数 tree_depth() を作成せよ。
例えば、上のAVL木の説明の図であれば、4段なので4を返すこと。
// 木の段数を数える関数
_____ tree_depth( _______________ p ) {
if ( p == NULL ) {
return _____ ;
} else {
int d_L = ______________ ;
int d_R = ______________ ;
if ( d_L > d_R )
return _____ ;
else
return _____ :
}
}
// pをつなぎ替え上部を返り値で返す。
struct Tree*rot_right( struct Tree* p ) {
struct Tree* pl = p->left ;
struct Tree* pr = pl->right ;
pl->right = p ;
p->left = = pr ;
return pl ;
}
int main() {
printf( "%d¥n" , tree_depth( top ) ) ;
top = rot_right( top ) ;
return 0 ;
}
ここまで2分探索木に関連したデータ構造の説明をしてきたが、このデータ構造は他のデータを扱う際にも用いられる。ここで、意思決定木を紹介する。
意思決定木
意思決定木の説明ということで、yes/noクイズの例を示しながら、2分木になっていることを 説明しプログラムを紹介。
((意思決定木の例:小さい子供が発熱した時)) 38.5℃以上の発熱がある？ no／ ＼yes 元気がある？ むねがひいひい？ yes／ ＼no no／ ＼yes 様子をみる 氷枕で病院 解熱剤で病院 速攻で病院
このような判断を行うための情報は、yesの木 と noの木の2つの枝を持つデータである。これは2分木と同じである。左右に枝のあるものは質問であり、yesの枝もnoの枝もない末端は最終決断を表す。このようなデータ構造は意思決定木と呼ばれ、質問と決断の処理は以下のように記述ができる。
struct Tree {
char *qa ;
struct Tree* yes ;
struct Tree* no ;
} ;
struct Tree* dtree( char *s ,
struct Tree* l , struct Tree* r )
{ struct Tree* n ;
n = (struct Tree*)malloc( sizeof( struct Tree ) ) ;
if ( n != NULL ) {
n->qa = s ;
n->yes = l ;
n->no = r ;
}
return n ;
}
void main() {
struct Tree* p =
dtree( "38.5℃以上の発熱がある?" ,
dtree( "胸がひぃひぃ?" ,
dtree( "速攻で病院", NULL,NULL ) ,
dtree( "解熱剤で病院",NULL,NULL ) ) ,
dtree( "元気がある?" ,
dtree( "様子をみる", NULL,NULL ) ,
dtree( "氷枕で病院", NULL,NULL ) ) ) ;
// 決定木をたどる
struct Tree* d = p ;
while( d->yes != NULL || d->no != NULL ) {
printf( "%s¥n" , d->qa ) ;
scanf( "%d" , &ans ) ;
// 回答に応じてyes/noの枝に進む。
if ( ans == 1 ) // yesを選択
d = d->yes ;
else if ( ans == 0 ) // noを選択
d = d->no ;
}
// 最終決定を表示
printf( "%s¥n" , d->qa ) ;
}
2分木の応用として式の表現の説明を行うけど、その前に計算式の一般論の説明を行う。
逆ポーランド記法
一般的に 1*2 + 3*4 と記載すると、数学的には演算子の優先順位を考慮して、(1*2)+(3*4) のように乗算を先に行う。このような優先順位を表現する時に、()を使わない方法として、逆ポーランド記法がある。
演算子の書き方には、前置記法、中置記法、後置記法があり、後置記法は、「2と3を掛ける、それに1を加える」と捉えると、日本語の処理と似ている。
中置記法 1+2*3 前置記法 +,1,*,2,3 後置記法 1,2,3,*,+ # 1と「2と3をかけた値」をたす。
後置記法は、一般的に逆ポーランド記法(Reverse Polish Notation)とも呼ばれ、式をコンピュータで実行する際の処理と似ている。
演算子の右結合・左結合
例えば、”1/2*3″という式が与えられたとする。この結果は、1/6だろうか？3/2だろうか？
一般的な数学では、優先順位が同じ演算子が並んだ場合、左側から計算を行う。つまり”1/2*3″は、”(1/2)*3″を意味する。こういった左側の優先順位が高い演算子は左結合の演算子という。
ただしC言語では、”a = b = c = 0″ と書くと、”a = (b = (c = 0))” として扱われる。こういった代入演算子は、 右結合の演算子である。
理解度確認
以下の式を指定された書き方で表現せよ。
逆ポーランド記法 1,2,*,3,4,*,+ を中置記法で表現せよ。 中置記法 (1+2)*3-4*5 を逆ポーランド記法で表現せよ。
以前の情報処理技術者試験では、スタックの概念の理解の例題として、逆ポーランド記法への変換アルゴリズムのプログラム作成が出題されることが多かったが、最近は出題されることはなくなってきた。
意思決定木と構文解析
前回までの授業で2分探索木の説明をしてきたが、このデータ構造は他のデータを扱う際にも用いられる。ここで、意思決定木と構文木を紹介する。
意思決定木
意思決定木の説明ということで、yes/noクイズの例を示しながら、2分木になっていることを 説明しプログラムを紹介。
((意思決定木の例:うちの子供が発熱した時)) 38.5℃以上の発熱がある？ no／ ＼yes 元気がある？ むねがひいひい？ yes／ ＼no no／ ＼yes 様子をみる 氷枕で病院 解熱剤で病院 速攻で病院
このような判断を行うための情報は、yesの木 と noの木の2つの枝を持つデータである。これは2分木と同じであり、このような処理は以下のように記述ができる。
struct Tree {
char *qa ;
struct Tree* yes ;
struct Tree* no ;
} ;
struct Tree* dtree( char *s ,
struct Tree* l , struct Tree* r )
{ struct Tree* n ;
n = (struct Tree*)malloc( sizeof( struct Tree ) ) ;
if ( n != NULL ) {
n->qa = s ;
n->yes = l ;
n->no = r ;
}
return n ;
}
void main() {
struct Tree* p =
dtree( "38.5℃以上の発熱がある?" ,
dtree( "胸がひぃひぃ?" ,
dtree( "速攻で病院",NULL,NULL ) ,
dtree( "解熱剤で病院",NULL,NULL ) ) ,
dtree( "元気がある?" ,
dtree( "様子をみる",NULL,NULL ) ,
dtree( "氷枕で病院",NULL,NULL ) ) ) ;
// 決定木をたどる
struct Tree* d = p ;
while( d->yes != NULL || d->no != NULL ) {
printf( "%s¥n" , d->qa ) ;
scanf( "%d" , &ans ) ;
// 回答に応じてyes/noの枝に進む。
if ( ans == 1 ) // yesを選択
d = d->yes ;
else if ( ans == 0 ) // noを選択
d = d->no ;
}
// 最終決定を表示
printf( "%s¥n" , d->qa ) ;
}
コンパイラと言語処理系
2分木の応用の構文木について、この後説明を行うが、構文木を使うコンパイラなどの一般知識を事前に説明しておく。
高級言語で書かれたプログラムを計算機で実行するソフトウェアは、言語処理系と呼ばれる。その実行形式により
- インタプリタ(interpreter:通訳)
- ソースプログラムの意味を解析しながら、その意味に沿った処理を行う
- コンパイラ(compiler:翻訳)
- ソースプログラムから機械語を生成し、実行する際には機械語を実行
- トランスコンパイラ
- ソースから他の言語のソースコードを生成し、それをさらにコンパイルし実行
最初のC++の実装では、C++をトランスレータにかけてC言語を生成し、C言語のコンパイラで動かしていた。
- ソースから他の言語のソースコードを生成し、それをさらにコンパイルし実行
- バイトコードインタプリタ
- ソースからバイトコード(機械語に近いコードを生成)、実行時にはバイトコードの命令に沿った処理を行う
- エミュレーター
- 異なるCPUのコンピュータで、システムの動作や機能を模倣して動かすシステム。
近々の例であれば、AppleのARMベースM1チップで intel CPU の動きを真似て動作させる Rosetta2 がトピック。パソコンで古いファミコンのソフトを動かすといった技術もエミュレータ。- 同じCPUで異なるOSを動かす場合は、CPU仮想化。
- 異なるCPUのコンピュータで、システムの動作や機能を模倣して動かすシステム。
に分けられる。
C言語で機械語が生成されるまで
C言語のプログラムから、機械語の命令が生成されるまでは、以下のような処理が行われる。
一般的にコンパイラの処理というと、ソースコードから機械語を生成するまでの処理を指すが、C言語ではプリプロセッサ処理を含んだり、コンパイラの処理(ソースコードからオブジェクトファイル生成まで)のほかにリンク処理を含んで使われることも多い。
foo.c C言語のソース ↓ プリプロセッサ処理 foo.c(#行の無いC言語のソース) ↓ コンパイラ foo.obj(オブジェクトファイル/中間コード) ↓ (+) ← ライブラリ(scanf,printfなどの組み込み関数などをまとめたもの) ↓ リンカ(リンケージエディタ) foo.exe
コンパイラの処理
コンパイラが命令を処理する際には、以下の処理が行われる。
- 字句解析(lexical analysys)
文字列を言語要素(token)に分解 - 構文解析(syntax analysys)
tokenの並び順に意味を反映した構造を生成 - 意味解析(semantics analysys)
命令に合わせた中間コードを生成 - 最適化(code optimization)
中間コードを変形して効率よいプログラムに変換 - コード生成(code generation)
実際の命令コード(オブジェクトファイル)として出力
バイトコードインタプリタとは
例年だと説明していなかったけど最近利用されるプログラム言語の特徴を説明。
通常、コンパイラとかインタプリタの説明をすると、Java がコンパイラとか、JavaScript はインタプリタといった説明となる。しかし、最近のこういった言語がどのように処理されるのかは、微妙である。
(( Java の場合 )) foo.java (ソースコード) ↓ Java コンパイラ foo.class (中間コード) ↓ JRE(Java Runtime Engine)の上で 中間コードをインタプリタ方式で実行
あらかじめコンパイルされた中間コードを、JREの上でインタプリタ的に実行するものは、バイトコードインタプリタ方式と呼ぶ。
ただし、JRE でのインタプリタ実行では遅いため、最近では JIT コンパイラ(Just-In-Time Compiler)により、中間コードを機械語に変換してから実行する。
また、JavaScriptなどは(というか最近のインタプリタの殆どPython,PHP,Perl,…は)、一般的にはインタプリタに分類されるが、実行開始時に高級言語でかかれたコードから中間コードを生成し、そのバイトコードをインタプリタ的に動かしている。
しかし、インタプリタは、ソースコードがユーザの所に配布されて実行するので、プログラムの内容が見られてしまう。プログラムの考え方が盗まれてしまう。このため、変数名を短くしたり、空白を除去したり(…部分的に暗号化したり)といった難読化を行うのが一般的である。
トークンと正規表現(字句解析)
規定されたパターンの文字列を表現する方法として、正規表現(regular expression)が用いられる。
((正規表現の書き方)) 選言 「abd|acd」は、abd または acd にマッチする。 グループ化 「a(b|c)d」は、真ん中の c|b をグループ化 量化 パターンの後ろに、繰り返し何回を指定 ? 直前パターンが0個か1個 「colou?r」 * 直前パターンが0個以上繰り返す 「go*gle」は、ggle,gogle,google + 直前パターンが1個以上繰り返す 「go+gle」は、gogle,google,gooogle
正規表現は、sed,awk,Perl,PHPといった文字列処理の得意なプログラム言語でも利用できる。こういった言語では、以下のようなパターンを記述できる。
[文字1-文字2...] 文字コード1以上、文字コード2以下 「[0-9]+」012,31415,...数字の列 ^ 行頭にマッチ $ 行末にマッチ ((例)) [a-zA-Z_][a-zA-Z_0-9]* C言語の変数名にマッチする正規表現
構文とバッカス記法
言語の文法を表現する時、バッカス記法(BNF)が良く使われる。
((バッカス記法)) <表現> ::= <表現1...> | <表現2...> | <表現3...> | ... ;
例えば、加減乗除記号と数字だけの式の場合、以下の様なBNFとなる。
((加減乗除式のバッカス記法))
<加算式> ::= <乗算式> '+' <乗算式>
| <乗算式> '-' <乗算式>
| <乗算式>
;
<乗算式> ::= <数字> '*' <乗算式>
| <数字> '/' <乗算式>
| <数字>
;
<数字> ::= [0-9]+
;
上記のバッカス記法には、間違いがある。”1+2+3″を正しく認識できない。どこが間違っているだろうか?
このような構文が与えられた時、”1+23*456″と入力されたものを、“1,+,23,*,456”と区切る処理が、字句解析である。
また、バッカス記法での文法に合わせ、以下のような構文木を生成するのが構文解析である。
＋ ／ ＼ １ ＊ ／ ＼ 23 456
理解度確認
- インタプリタ方式で、処理速度が遅い以外の欠点をあげよ。
- 情報処理技術者試験の正規表現,BNF記法問題にて理解度を確認せよ。
意思決定木と構文解析
前回までの授業で2分探索木の説明をしてきたが、このデータ構造は他のデータを扱う際にも用いられる。ここで、意思決定木と構文木を紹介する。
意思決定木
意思決定木の説明ということで、yes/noクイズの例を示しながら、2分木になっていることを 説明しプログラムを紹介。
((意思決定木の例:うちの子供が発熱した時)) 38.5℃以上の発熱がある？ no／ ＼yes 元気がある？ むねがひいひい？ yes／ ＼no no／ ＼yes 様子をみる 氷枕で病院 解熱剤で病院 速攻で病院
このような判断を行うための情報は、yesの木 と noの木の2つの枝を持つデータである。これは2分木と同じであり、このような処理は以下のように記述ができる。
struct Tree {
char *qa ;
struct Tree* yes ;
struct Tree* no ;
} ;
struct Tree* dtree( char *s ,
struct Tree* l , struct Tree* r )
{ struct Tree* n ;
n = (struct Tree*)malloc( sizeof( struct Tree ) ) ;
if ( n != NULL ) {
n->qa = s ;
n->yes = l ;
n->no = r ;
}
return n ;
}
void main() {
struct Tree* p =
dtree( "38.5℃以上の発熱がある?" ,
dtree( "胸がひぃひぃ?" ,
dtree( "速攻で病院",NULL,NULL ) ,
dtree( "解熱剤で病院",NULL,NULL ) ) ,
dtree( "元気がある?" ,
dtree( "様子をみる",NULL,NULL ) ,
dtree( "氷枕で病院",NULL,NULL ) ) ) ;
// 決定木をたどる
struct Tree* d = p ;
while( d->yes != NULL || d->no != NULL ) {
printf( "%s¥n" , d->qa ) ;
scanf( "%d" , &ans ) ;
// 回答に応じてyes/noの枝に進む。
if ( ans == 1 ) // yesを選択
d = d->yes ;
else if ( ans == 0 ) // noを選択
d = d->no ;
}
// 最終決定を表示
printf( "%s¥n" , d->qa ) ;
}
コンパイラと言語処理系
2分木の応用の構文木について、この後説明を行うが、構文木を使うコンパイラなどの一般知識を事前に説明しておく。
高級言語で書かれたプログラムを計算機で実行するソフトウェアは、言語処理系と呼ばれる。その実行形式により
- インタプリタ(interpreter:翻訳)
- ソースプログラムの意味を解析しながら、その意味に沿った処理を行う
- コンパイラ(compiler:通訳)
- ソースプログラムから機械語を生成し、実行する際には機械語を実行
- トランスコンパイラ
- ソースから他の言語のソースコードを生成し、それをさらにコンパイルし実行
最初のC++の実装では、C++をトランスレータにかけてC言語を生成し、C言語のコンパイラで動かしていた。
- ソースから他の言語のソースコードを生成し、それをさらにコンパイルし実行
- バイトコードインタプリタ
- ソースからバイトコード(機械語に近いコードを生成)、実行時にはバイトコードの命令に沿った処理を行う
- エミュレーター
- 異なるCPUのコンピュータで、システムの動作や機能を模倣して動かすシステム。
近々の例であれば、AppleのARMベースM1チップで intel CPU の動きを真似て動作させる Rosetta2 がトピック。パソコンで古いファミコンのソフトを動かすといった技術もエミュレータ。- 同じCPUで異なるOSを動かす場合は、CPU仮想化。
- 異なるCPUのコンピュータで、システムの動作や機能を模倣して動かすシステム。
に分けられる。
コンパイラが命令を処理する際には、以下の処理が行われる。
- 字句解析(lexical analysys)
文字列を言語要素(token)に分解 - 構文解析(syntax analysys)
tokenの並び順に意味を反映した構造を生成 - 意味解析(semantics analysys)
命令に合わせた中間コードを生成 - 最適化(code optimization)
中間コードを変形して効率よいプログラムに変換 - コード生成(code generation)
実際の命令コードとして出力
バイトコードインタプリタとは
例年だと説明していなかったけど最近利用されるプログラム言語の特徴を説明。
通常、コンパイラとかインタプリタの説明をすると、Java がコンパイラとか、JavaScript はインタプリタといった説明となる。しかし、最近のこういった言語がどのように処理されるのかは、微妙である。
(( Java の場合 )) foo.java (ソースコード) ↓ Java コンパイラ foo.class (中間コード) ↓ JRE(Java Runtime Engine)の上で 中間コードをインタプリタ方式で実行
あらかじめコンパイルされた中間コードを、JREの上でインタプリタ的に実行するものは、バイトコードインタプリタ方式と呼ぶ。
ただし、JRE でのインタプリタ実行では遅いため、最近では JIT コンパイラ(Just-In-Time Compiler)により、中間コードを機械語に変換してから実行する。
また、JavaScriptなどは(というか最近のインタプリタの殆どPython,PHP,Perl,…は)、一般的にはインタプリタに分類されるが、実行開始時に高級言語でかかれたコードから中間コードを生成し、そのバイトコードをインタプリタ的に動かしている。
しかし、インタプリタは、ソースコードがユーザの所に配布されて実行するので、プログラムの内容が見られてしまう。プログラムの考え方が盗まれてしまう。このため、変数名を短くしたり、空白を除去したり(…部分的に暗号化したり)といった難読化を行うのが一般的である。
トークンと正規表現(字句解析)
規定されたパターンの文字列を表現する方法として、正規表現(regular expression)が用いられる。
((正規表現の書き方)) 選言 「abd|acd」は、abd または acd にマッチする。 グループ化 「a(b|c)d」は、真ん中の c|b をグループ化 量化 パターンの後ろに、繰り返し何回を指定 ? 直前パターンが0個か1個 「colou?r」 * 直前パターンが0個以上繰り返す 「go*gle」は、ggle,gogle,google + 直前パターンが1個以上繰り返す 「go+gle」は、gogle,google,gooogle
正規表現は、sed,awk,Perl,PHPといった文字列処理の得意なプログラム言語でも利用できる。こういった言語では、以下のようなパターンを記述できる。
[文字1-文字2...] 文字コード1以上、文字コード2以下 「[0-9]+」012,31415,...数字の列 ^ 行頭にマッチ $ 行末にマッチ ((例)) [a-zA-Z_][a-zA-Z_0-9]* C言語の変数名にマッチする正規表現
構文とバッカス記法
言語の文法を表現する時、バッカス記法(BNF)が良く使われる。
((バッカス記法)) <表現> ::= <表現1...> | <表現2...> | <表現3...> | ... ;
例えば、加減乗除記号と数字だけの式の場合、以下の様なBNFとなる。
((加減乗除式のバッカス記法))
<加算式> ::= <乗算式> '+' <乗算式>
| <乗算式> '-' <乗算式>
| <乗算式>
;
<乗算式> ::= <数字> '*' <乗算式>
| <数字> '/' <乗算式>
| <数字>
;
<数字> ::= [0-9]+
;
上記のバッカス記法には、間違いがある。”1+2+3″を正しく認識できない。どこが間違っているだろうか?
このような構文が与えられた時、”1+23*456″と入力されたものを、“1,+,23,*,456”と区切る処理が、字句解析である。
また、バッカス記法での文法に合わせ、以下のような構文木を生成するのが構文解析である。
＋ ／ ＼ １ ＊ ／ ＼ 23 456
理解度確認
- インタプリタ方式で、処理速度が遅い以外の欠点をあげよ。
- 情報処理技術者試験の正規表現,BNF記法問題にて理解度を確認せよ。
意思決定木と構文解析
前回までの授業で2分探索木の説明をしてきたが、このデータ構造は他のデータを扱う際にも用いられる。ここで、意思決定木と構文木を紹介する。
意思決定木
意思決定木の説明ということで、yes/noクイズの例を示す。これは2分木であり、質問を繰り返し最後に答えを示すのであれば、以下のようなプログラムになるであろう。
((意思決定木の例:うちの子供が発熱した時)) 38.5℃以上の発熱がある？ no／ ＼yes 元気がある？ むねがひいひい？ yes／ ＼no no／ ＼yes 様子をみる 氷枕で病院 解熱剤で病院 速攻で病院
このような判断を行うための情報は、yesの木 と noの木の2つの枝を持つデータである。また、各ノードは質問のための文字列を持ち、末端のノードでは質問への回答の文字列となる。
struct Tree {
char *qa ;
struct Tree* yes ;
struct Tree* no ;
} ;
struct Tree* dtree( char *s ,
struct Tree* l , struct Tree* r )
{ struct Tree* n ;
n = (struct Tree*)malloc( sizeof( struct Tree ) ) ;
if ( n != NULL ) {
n->qa = s ;
n->yes = l ;
n->no = r ;
}
return n ;
}
void main() {
struct Tree* p =
dtree( "38.5℃以上の発熱がある?" ,
dtree( "胸がひぃひぃ?" ,
dtree( "速攻で病院",NULL,NULL ) ,
dtree( "解熱剤で病院",NULL,NULL ) ) ,
dtree( "元気がある?" ,
dtree( "様子をみる",NULL,NULL ) ,
dtree( "氷枕で病院",NULL,NULL ) ) ) ;
// 決定木をたどる
struct Tree* d = p ;
while( d->yes != NULL || d->no != NULL ) {
printf( "%s¥n" , d->qa ) ;
scanf( "%d" , &ans ) ;
// 回答に応じてyes/noの枝に進む。
if ( ans == 1 ) // yesを選択
d = d->yes ;
else if ( ans == 0 ) // noを選択
d = d->no ;
}
// 最終決定を表示
printf( "%s¥n" , d->qa ) ;
}
コンパイラと言語処理系
2分木の応用の構文木について、この後説明を行うが、構文木を使うコンパイラなどの一般知識を事前に説明しておく。
高級言語で書かれたプログラムを計算機で実行するソフトウェアは、言語処理系と呼ばれる。その実行形式により
- インタプリタ(interpreter:翻訳)
- ソースプログラムの意味を解析しながら、その意味に沿った処理を行う
- コンパイラ(compiler:通訳)
- ソースプログラムから機械語を生成し、実行する際には機械語を実行
- トランスコンパイラ
- ソースから他の言語のソースコードを生成し、それをさらにコンパイルし実行
- バイトコードインタプリタ
- ソースからバイトコード(機械語に近いコードを生成)、実行時にはバイトコードの命令に沿った処理を行う
に分けられる。
コンパイラが命令を処理する際には、以下の処理が行われる。
- 字句解析(lexical analysys)
文字列を言語要素(トークン: token)に分解 - 構文解析(syntax analysys)
トークンの並び順に意味を反映した構造を生成 - 意味解析(semantics analysys)
命令に合わせた中間コードを生成 - 最適化(code optimization)
中間コードを変形して効率よいプログラムに変換 - コード生成(code generation)
実際の命令コードとして出力
バイトコードインタプリタとは
例年だと説明していなかったけど最近利用されるプログラム言語の特徴を説明。
通常、コンパイラとかインタプリタの説明をすると、Java がコンパイラとか、JavaScript はインタプリタといった説明となる。しかし、最近のこういった言語がどのように処理されるのかは、微妙である。
(( Java の場合 )) foo.java (ソースコード) ↓ Java コンパイラ foo.class (中間コード) ↓ JRE(Java Runtime Engine)の上で 中間コードをインタプリタ方式で実行
あらかじめコンパイルされた中間コードを、JREの上でインタプリタ的に実行するものは、バイトコードインタプリタ方式と呼ぶ。
ただし、JRE でのインタプリタ実行では遅いため、最近では JIT コンパイラ(Just-In-Time Compiler)により、中間コードを機械語に変換してから実行する。
また、JavaScriptなどは(というか最近のインタプリタの殆どPython,PHP,Perl,…は)、一般的にはインタプリタに分類されるが、実行開始時に高級言語でかかれたコードから中間コードを生成し、そのバイトコードをインタプリタ的に動かしている。
しかし、インタプリタは、ソースコードがユーザの所に配布されて実行するので、プログラムの内容が見られてしまう。プログラムの考え方が盗まれてしまう。このため、変数名を短くしたり、空白を除去したり(…部分的に暗号化したり)といった難読化を行うのが一般的である。
トークンと正規表現(字句解析)
規定されたパターンの文字列を表現する方法として、正規表現(regular expression)が用いられる。
((正規表現の書き方)) 選言 「abd|acd」は、abd または acd にマッチする。 グループ化 「a(b|c)d」は、真ん中の c|b をグループ化 量化 パターンの後ろに、繰り返し何回を指定 ? 直前パターンが0個か1個 「colou?r」 * 直前パターンが0個以上繰り返す 「go*gle」は、ggle,gogle,google + 直前パターンが1個以上繰り返す 「go+gle」は、gogle,google,gooogle
正規表現は、sed,awk,Perl,PHPといった文字列処理の得意なプログラム言語でも利用できる。こういった言語では、以下のようなパターンを記述できる。
[文字1-文字2...] 文字コード1以上、文字コード2以下 「[0-9]+」012,31415,...数字の列 ^ 行頭にマッチ $ 行末にマッチ ((例)) [a-zA-Z_][a-zA-Z_0-9]* C言語の変数名にマッチする正規表現
構文とバッカス記法
言語の文法を表現する時、バッカス記法(BNF)が良く使われる。
((バッカス記法)) <表現> ::= <表現1...> | <表現2...> | <表現3...> | ... ;
例えば、加減乗除記号と数字だけの式の場合、以下の様なBNFとなる。
((加減乗除式のバッカス記法))
<加算式> ::= <乗算式> '+' <乗算式>
| <乗算式> '-' <乗算式>
| <乗算式>
;
<乗算式> ::= <数字> '*' <乗算式>
| <数字> '/' <乗算式>
| <数字>
;
<数字> ::= [0-9]+
;
# 上記のバッカス記法には、間違いがある。”1+2+3″を正しく認識できない。
# どこが間違っているだろうか?
このような構文が与えられた時、”1+23*456″と入力されたものを、“1,+,23,*,456”と区切る処理が、字句解析である。
また、バッカス記法での文法に合わせ、以下のような構文木を生成するのが構文解析である。
＋ ／ ＼ １ ＊ ／ ＼ 23 456
理解度確認
- インタプリタ方式で、処理速度が遅い以外の欠点をあげよ。
- 情報処理技術者試験の正規表現,BNF記法問題にて理解度を確認せよ。