とにかく木を作る

ゲームに簡単なプログラムを組み込むためにスクリプト言語とそれを実行するインタープリタをC++で作ってしまおうというコーナーです。
スクリプトのソースコードの文字列に意味を与える字句解析、プログラムとしての構造を調べる構文解析の説明をしました。
今度はそういった解析の実際に方法について触れます。

ちょっと書き換え

とりあえず図を描くのに大変なのでいろんな名前を短く書き換えます。
以下のようになりましたが、短くなりすぎて意味がわかりませんね。
でもいいんです。コンパイラだってインタープリタだって意味がわかってて解析してるわけじゃないんですから。
ついでにマクロ構文の書き方も若干変更してます。

マイクロ構文

(1) NL ::= '0' | '1' | '2' | '3' | '4' | '5' | '6' | '7' | '8' | '9'
(2) NZ ::= '1' | '2' | '3' | '4' | '5' | '6' | '7' | '8' | '9'
(3) N ::= '0' | NZ NL*
(4) PM ::= '+' | '-'
(5) MD ::= '*'| '/'
(6) BS ::= '('
(7) BE ::= ')'

マクロ構文

(1) E ::= T
(2) E ::= E PM T
(3) T ::= F
(4) T ::= T MD F
(5) F ::= N
(6) F ::= BS E BE

行きつ戻りつ

えっと、これ、本を見ながら自分なりに解釈しつつ書いてるんですが、そろそろ本の内容についていけなくなって、いや、本の最初からしっかり読んでいけばわかる内容なんですけど、さっさと結果を出したいがためにかなり端折ってました。
さりとて本を読み直して今までやらなかった部分をじっくりやっていくつもりも無いので、木さえできればなんとかなるという馬鹿げた考えのもととにかく木構造を作るという方向で無理に進めていきます。
今回も「15+7-2-2-(2+3)*12/(14-4)」を例に挙げて考えると、字句解析が終わった時点で「N PM N PM N PM N PM BS N PM N BE MD N MD BS N PM N BE」となり、以下のような木の集まり、すなわち森になっています。

「木」というよりは「芽」ですね。
この結果をまた左から読みながら木を作っていくわけです。
この木の作り方には色々あるわけですが、ここは本を読んでわからなかった部分なので我流で行くことにします。
多分これも過去に誰かがやっていてそれなりの名前がついてるんだと思いますがよくわかっていません。
まず一般的な方法から考えるのはやめておいて、例の「15+7-2-2-(2+3)*12/(14-4)」の解析で見ていきます。

まず、最初のN(15)を読むと、Nだけだと当てはまる構文規則が(5)だけしかないので(5)を適用してFになり、Fだけだと(3)しか当てはまらないのでTになって、次は(1)からEになって、これでもう当てはまる構文規則がなくなったので１語目は終わりです。

次にPM(+)を読むと、Nからできた木とPMからできた木の２本になるので、２本の木の根っこを見てみると「E PM」となっています。
こうやって根っこがたまってきたら、一番右から根っこをまとめていけないか考えるのです。
この場合、PMで終わる規則は無いので手も足も出ません。

さらにN(7)を読んでみると、N(15)のときと同じようにTまで進むと、根っこの集まりが「E PM T」の形になって、(2)が使えるようになっています。
(1)も同時に当てはまっていますが、こういう場合は長いほうを優先して考えます。

ということで(2)を適用すると、「E」となり、根っこが一つにまとまりました。

同じ要領でN(12)まで読んでいくと、困ったことが起こります。
本当なら(4)の規則を使って「(2+3)」の木と「*」の木と「12」の木をくっつけなければいけないのに、「(2+3)」の木がそれ以前の木のほうにくっついてしまっているため根っこをくっつけていく方法ではこれ以上解析が進まないのです。
後ろの「MD F」までは(4)に一致しているのにその前が「E」なのでくっつけられないのです。

そんなときは都合の悪い木を少し分解してやります。
「E MD F」だと都合が悪いので最初の「E」を分解して「E PM T」にすると、全体として「E PM T MD F」となり、(4)が適用できるようになるわけです。

で、(4)を適用すると「E PM T MD F」は「E PM T」となり、更に(2)より「E」となるのです。
ちなみに、ばらしてもうまく木が作れなかった場合、ばらしたことはいったん忘れて元に戻しておきます。
もっと先まで読んだらもっときっちり木が作れるかもしれないからです。

こんなふうに木を作ったり時にはばらしたりしながら作っていくと、最終的にこんな木になります。
この手順をプログラムとして書くことができれば木構造が作れるようになり、スクリプトが実行可能となるのです。
この方法で本当にうまく行くのか、というと、実際のところ構文規則の作り方によるようです。

…続く。