意思決定木と構文解析
前回までの授業で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”と区切る処理が、字句解析である。
また、バッカス記法での文法に合わせ、以下のような構文木を生成するのが構文解析である。
+ / \ 1 * / \ 23 456
理解度確認
- インタプリタ方式で、処理速度が遅い以外の欠点をあげよ。
- 情報処理技術者試験の正規表現,BNF記法問題にて理解度を確認せよ。
Visual Studio Code で印刷
実験や授業課題のレポート提出で、プログラムを印刷したものを提出してくれるけど、行を移動しながら何度もスクリーンキャプチャで保存した画像ファイルをWordに貼り付けて提出している人が多い。
いままでなら、「秀丸エディタで印刷してよ…」とか言ってたけど、最近は Visual Studio Code を利用しているみたいで、「プログラムの印刷の仕方がわからない」という人が多いようだ。
実際、Visual Studio Code はたまにしか使わないけど、確かに基本機能の中には印刷機能がないな….
今時、プログラムリストなんて紙媒体で印刷しないもんなんだろうけど、プログラム課題のレポートなら、コードは証拠だからな。
Visual Studio Code の PrintCode
こういう場合は、Visual Studio Code の拡張機能の PrintCode をインストールすればいい。
印刷する時は、F1 キーを押して、拡張コマンドの入力で printcode と打てば印刷される。
ただし、PrintCode は JavaScript を使って HTML を生成し印刷を行うため、Windowsでデフォルトブラウザが Internet Explorer の場合は動かない。このためデフォルトブラウザの変更により Chrome などを使う様に変更しておく必要あり。
Sublime Text なら Print to HTML
同じく、エディタが Sublime Text を使っているのなら、これも印刷機能が付いていないので、”Print to HTML”パッケージをインストールし、あとは、Shift+Alt+P で HTML 用に出力できるのでブラウザ側で印刷を行う。