ゲームに簡単なプログラムを組み込むためにスクリプト言語とそれを実行するインタープリタをC++で作ってしまおうというコーナーです。
適当に色々決めてみたので、今度はスクリプトを解釈して実行するときに使う解析木について記述します。
木構造
例えば、「1+1」という３文字の文字列を解釈して計算するなら、1があって、+があって、1が続くから、1と1を足して2になるわけです。
簡単ですね。
じゃあ、「15+7-2-2-(2+3)*12/(14-4)」だったらどうでしょう？
1があって、5があって、+があって、7があって、-があって……
だから、15と7を足して、その結果から2を引いて、2を引いて、その結果から、2と3を足したものを……
すっごく簡単な計算なのに、機械的に前から一文字ずつ解釈していって考えるとこんがらがってきますね(答えは12)。
でも、書いたプログラム(ここではスクリプト？)を解釈する、コンパイラとかインタープリタなんかは、こういうのを、いえ、もっと複雑なプログラムでも、こんがらがってしまわないように解釈できてしまうわけです。
これは、つまり、与えられた式の構造をちゃんと把握しないと簡単な計算すらろくにできないということです。
そして、その構造を表すのに、木構造というものがあります。
さっきの「15+7-2-2-(2+3)*12/(14-4)」を木構造に書き直してみると、次のようになります。
これでどうやって計算していくのかというと、まず上から見ていって、「-」があるので、引き算がしたいわけです。
だから、下に向かって延びている２本の線(こういうのを枝と呼ぶみたいですね)を見て、その枝の先を計算した結果２つを引いたのが最終結果というわけです。
枝が複数に分かれていた場合は左から順に見ていくことになっているので、左に進むと、また「-」があります。
だから、更に下の枝を見ていきます。
そしてまた「-」があり、今度は「+」が出てきます。
更に「+」から下を見ていくと、左側の枝の先(これを接点というらしいですね)が「15」でありこれより先はありません。
だから、今度は引き返して、右側の枝を見ます。
すると、右側には「7」があり、これまた終点なので戻ります。
これで、「+」の先の枝の数値が15と7だということがわかったので、足して22という数値が得られます。
そして、「+」は計算し終えたので一つ上の「-」に戻ります。
ここでは左側の数値が22だということはわかっていますが、まだ右側の枝は見ていません。
そこで右側を見ると、2という数値があるので22から2を引いて20とし、更に上に戻ります。
このようにして、まだ見ていない枝はどんどん下に進んでいき、終わったら上に戻る、というのを繰り返していくと、最終的には全部計算し終わって結果が出るというわけです。
解析木
で、さっきの木構造がどのようにスクリプトに使われるのかというと、先ほどは各接点で、対応する計算をしていましたが、スクリプトを解釈するインタープリタでは、テキストとして存在するスクリプトを木構造に変換し、それぞれの接点に対応した処理を実行するのです(計算も処理の一つですね)。
例えば、「if (a==10) b=1; else b=2;」だったら、木構造は次のようになります。
で、例えばこれでaが1だった場合、最初の接点(これを根というそうですね)の「if」を実行するため、左側の枝を見に行きます。
そして左側のa==10は成り立たないので、一番右の枝へ進んで、真ん中の枝の先は実行しません。
aが10だった場合は、今度はa==10が成り立つので真ん中へ進んで一番右は実行しないということになります。
コンパイラを作る場合は、接点を全部順番に見ていって中間コードなり目的コードなりを出力する必要があるのですが、インタープリタでは場合によっては木構造の一部を実行しないことがあるわけです。
この木構造は、構文解析木と呼ばれ、文字通り構文解析した結果に出来上がるものです(たぶん)。
でもこの構文解析が問題なんですよね…。
iがあって、fがあって、スペースがあって、(があって……