ゲームに簡単なプログラムを組み込むためにスクリプト言語とそれを実行するインタープリタをC++で作ってしまおうというコーナーです。
前回の続きであります。
これからは不定期更新とさせていただきます(元々滞りがちでしたが)。
で、まあ、今回は配列の実装について考えてみようかなー。なんて考えてみたのですけど、やっぱり順序立てて作っていったほうがよさそうだったので、既に完成した字句解析の続きの構文解析を作る方法を考えたいと思います。
第７回で、木を作るアルゴリズムについて触れましたが、あの方式には時々木をばらす必要があるためばらすための情報を保持しておかなければならなかったりする問題がありました。
ばらすと作り直すのが面倒だし、一度先へ進んだものをわざわざ戻ってくるというのも面倒なわけです。
というわけで、後々ばらすことになりそうなときは、早まって進めたりせず、先を見るだけ見てどうするかを決めるのです。
こういうのを先読みといいます。たぶん。
このことを考えつつ処理の流れを考えると、次のようになります。
- 語句を１つ読み込み、スタックに入れる。
- スタックの最後が何にも一致していなければ次に進む（１に戻る）。
- 一致する構文が１つあり、それ以外に可能性がなければそれに置き換えて次に進む（１に戻る）。
- 一致する構文以外に可能性があれば更に語句を１つ先読みする（スタックに入れない）。
- 読み込んだ語句を使ってその可能性を検証し、今一致している構文と将来一致するであろう構文のどちらかを選ぶ。
- 今一致している構文を選んだ場合は３と同じ。
- 将来一致するであろう構文を選んだ場合は何もせず次へ進む（１に戻る）。
- それ以外の場合は知らん。