意思決定木と構文解析
前回までの授業で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”と区切る処理が、字句解析である。
また、バッカス記法での文法に合わせ、以下のような構文木を生成するのが構文解析である。
+ / \ 1 * / \ 23 456
理解度確認
- インタプリタ方式で、処理速度が遅い以外の欠点をあげよ。
- 情報処理技術者試験の正規表現,BNF記法問題にて理解度を確認せよ。
コンパイラの技術と関数電卓プログラム(1)
コンパイラを作るための技術の基礎を学んでもらうために、 簡単な関数電卓プログラム作成を課題とする。 基本は、printf( “%d” , eval( “1+2*3”) ) みたいな計算プログラムを作成する。
計算式から、計算処理を行う場合、演算子の優先順位を正しく処理できることが求められる。
一般的には、計算の機械語を生成する場合、データを準備して計算という方法であり、 逆ポーランド記法変換が行われる。
たとえば、”1+2×3″は、”1,2,+,3,×” といった表記に改められ、変換後の式は スタックを用いて、「値はpush,演算子はpop,pop,計算して,push」という 単純なルールで処理すれば、計算を行うことができる。
字句解析と構文解析
このような、計算式の処理を実行する場合、”1“,”+“,”2“,”✳︎“,”3“という 字句に切り分ける処理を、字句解析という。 この結果から、”式✳︎式”なら掛け算、”式+式”は足し算といった、 前後の字句の組合せから、構文木を生成する処理は、構文解析という。 コンパイラであれば、この後、最適化、コード生成などが行われる。
C言語であれば、コンパイル前後には以下の処理が行われる。
- プリプロセッサ処理
↓(#の無いCコード) - コンパイル処理
- 字句解析 — 今回の実験
- 構文解析 — 今回の実験のキモ
- コード生成
↓(中間コード)
- リンク処理 ← ライブラリ
↓ - 機械語
字句解析と正規表現
字句(トークン)の切り出しでは、その文法を説明する際には、正規表現などを用いる。
今回の実験の後半では、正規表現に合わせたプログラミングツール(flex)を用いるが、前半では正規表現に合わせた文字列処理をプログラムする必要がある。
簡単な正規表現 . 任意の文字 * 直前の0回以上の繰り返し + 直前の1回以上の繰り返し [0-9a-z] カッコの中の文字のいずれか - は範囲を示す。 (a|b|c) 丸カッコの|区切りのうちのどれか。 (例) C言語の変数の正規表現 [a-zA-Z_][a-zA-Z0-9_]*
構文解析の方法
構文解析では、構文を状態遷移として考え、この式の後にくる可能性のある状態は? という考えで解析を行う。 このような構文は、一般的にバッカス・ナウア記法(BNF)などで表現されることが多い。 また、簡単な構文解析であれば、
などが用いられる。
再帰下降パーサ
簡単な再帰下降パーサの演習として、1桁の数字と+,*演算子の処理プログラムを 考える。
加減,乗除の式のバッカス記法(BNF) exp_加減 ::= exp_乗除 '+' exp_乗除 | exp_乗除 '-' exp_乗除 | exp_乗除 (注意)このBNFは若干間違っているよ!! ; exp_乗除 ::= DIGIT '*' exp_乗除 | DIGIT '/' exp_乗除 | DIGIT ; DIGIT ::= [0-9] ;
練習として、上に示す再帰下降パーサに、 (1) “(“,”)” を含めた場合の、BNF 記法を考え、(2) 数値として複数桁が使えるようにし、 (3) 式を読みやすくする空白を処理できるように 改造せよ。
副問合せと相関副問合せと集約関数
SQLの副問い合せ
前節の結合処理は時として効率が悪い。このような場合は、副問い合わせを用いる場合も多い。
SELECT S.業者名, S.所在 FROM S WHERE S.業者番号 IN ( SELECT SG.業者番号 FROM SG WHERE SG.商品番号 = 'G2' AND SG.在庫量 >= 200 ) ;
- 実験環境で副問い合わせ(学内のみ)
まず、『◯ IN { … }』 の比較演算子は、◯が{…}の中に含まれていれば真となる。また、SQLの中の (…) の中が副問い合わせである。
この SQL では、副問い合わせの内部には、テーブル S に関係する要素が含まれない。この場合、副問い合わせ(商品番号がG2で在庫量が200以上)は先に実行される。
{(S1,G2,200),(S2,G2,400),(S3,G2,200),(S4,G2,200)}が該当し、その業者番号の{S1,S2,S3,S4}が副問い合わせの結果となる。最終的に SELECT … FROM S WHERE S.業者番号 IN {‘S1′,’S2′,’S3′,’S4’} を実行する。
相関副問い合わせ
SELECT G.商品名, G.色, G.価格 FROM G WHERE 'S4' IN ( SELECT SG.業者番号 FROM SG WHERE SG.商品番号 = G.商品番号 ) ;
- 実験環境で相関副問い合わせ(学内のみ)
この副問い合わせでは、内部に G.商品番号 が含まれており、単純に()内を先に実行することはできない。こういった副問い合わせは、相関副問い合わせと呼ばれる。
処理は、Gのそれぞれの要素毎に、副問い合わせを実行し、その結果を使って WHERE節の判定を行う。WHERE節の選択で残った結果について、射影で商品名,色,価格が抽出される。
// 概念の説明用に、C言語風とSQL風を混在して記載する for( int i = 0 ; i < sizeofarray( G ) ; i++ ) { SELECT SG.業者番号 FROM SG WHERE SG.商品番号 = G[i].商品番号 を実行 if ( WHERE 'S4' IN 副query の結果が真なら ) { printf( ... ) ; } } // 全てのG 副queryの結果 WHERE 射影 // G1 -> {S1,S2} // G2 -> {S1,S2,S3,S4} -> ◯ -> (ノート,青,170) // G3 -> {S1} // G4 -> {S1,S4} -> ◯ -> (消しゴム,白,50) // G5 -> {S1,S4} -> ◯ -> (筆箱,青,300) // G6 -> {S1}
特殊な条件演算子
WHERE 節の中で使える特殊な条件演算子を紹介する。
... AND ... WHERE S.業者番号 <= 100 AND S.業者番号 >= 200 ; ... OR ... WHERE S.業者番号 >= 100 OR S.業者番号 <= 200 ; NOT ... WHERE NOT S.業者番号 >= 100 ; ... IN ... WHERE S.業者番号 IN ( 'S1' , 'S4' ) ; ... BETWEEN A AND B WHERE S.優良度 BETWEEN 50 AND 100 ; ... LIKE ... WHERE S.業者名 LIKE 'A_C社' ; _ は任意の1文字 ABC社 ADC社 WHERE S.業者名 LIKE 'A%社' ; % は任意の0~N文字 A社, AA社 ABC社 ... IS NULL WHERE S.業者名 IS NULL WHERE S.業者名 IS NOT NULL
集約関数
集約関数は、SQL の SELECT の射影部分で使える関数で、出力対象となった項目に対して、COUNT(),SUM(),AVG()といった計算を行うもの。
COUNT() - 項目の数 SUM() - 項目の合計 AVG() - 項目の平均 MAX() - 項目の最大値 MIN() - 項目の最低値 SELECT COUNT(S.業者番号) FROM S WHERE S.優良度 > 20 ;
- 実験環境で集約関数(学内のみ)
集合計算
複数の SQL の結果に対し、集合和, 集合積, 集合差などの処理を行う。
... UNION ... 集合和 ... EXPECT ... 集合差 ... INTERSECT ... 集合積 SELECT S.業者名 FROM S WHERE S.所在 = '福井' UNION SELECT S.業者名 FROM S WHERE S.所在 = '東京'
- 実験環境で集合計算(学内のみ)
演習課題
SQLの実験環境を使って、自分で考えたSQLの命令を2つ実行すること。実行した命令とその意味を説明し、出力された結果と一致することを確認すること。
さらにこの実行と同じ結果が出力される様なC言語のプログラムを作成し、おなじく結果を確認すること。
考察として、SQLで書いたプログラムとCで書いたプログラムの違いや便利な点や、Cでのプログラムの速度を早めるにはどう書くと良いかを比較検討すること。