【C++】インタプリタを初めから丁寧に（第01回）

アプリケーションがスクリプトにより動作を変更できるようにするのは、応用範囲も広く（他人に仕事を任せれるため）大変重要です。特にゲームなどでは、敵の動作などをハードコーディングしてしまった場合プログラムを製作した人しか変更することが難しく、その変更も非常に面倒になってきます。

インタプリタを製作するには yacc や lex を使うと大変便利ですが、内部動作をよく理解するために最初は手書きで作ってみることが必要でしょう。第01回はインタプリタの内部動作についてを学習します。

まず、一口にインタプリタといっても規模による違いがあります。

クラス、関数作成まで行うことができるもの
変数理解や条件分岐は行えるもの
プログラマが定義した関数使用しかできないもの

このコラムでは 2. を取り上げて解説します。

まず、インタプリタとは以下の処理を行います。

1. 字句解析

字句解析とは、

α. a = 0       a…識別子
=…演算子
0…整数
β. if(!a)      if…制御文判別子
( …区切り記号
! …演算子
a …識別子
) …区切り記号
γ. printf("a")     printf…関数判別子
(　　  …区切り記号
"a"   …文字列
)       …区切り記号

のように、文字を判別してそれが何であるかを理解します。
「ここでは１単語が何であるか？」ということのみに着目するため、「その文が正しいかどうか？」ということは判断しません。

2. 構文解析

構文解析にはいくつか種類がありますが、ここでは yacc を使わないためLR構文解析は行いません。
演算子順位構文解析法により演算子そのもの及び演算子の左右に優先順位をつけていきます。
例として、

a = b * c + d と a = b * (c + d)
について考えます。

a = b * c + d を左から読んだ場合

識別子(a) 演算子(=) 識別子(b) 演算子(*) 識別子(c) 演算子(+) 識別子(d)

となります。
このとき左辺 a は右辺 b * c + d の計算後に代入しますので = 演算子の左右の優先順位は左辺<右辺となります。また最後に実行されるため演算子の優先順位はこの中では一番低いと考えられます。

また次に右辺を右から読んだ場合 * 演算子と + 演算子があります。
= 演算子と同様に考えるとすると * と + の演算子優先順位を考え * と + の左右の優先順位を判別します。

以上をまとめると優先順位はこのようになります。

演算子　演算子そのものの優先順位　左右の優先順位
　　=　　　　　　　　　　　0　　　　　　　　　　　　左<右
　　+　　　　　　　　　　　1　　　　　　　　　　　　左=右
　　*　　　　　　　　　　　2　　　　　　　　　　　　左=右

次に a = b * (c + d) を考えます
= 演算子までは同じです。
しかし右辺に（）、区切り記号があります。
区切り記号内はこの式の中で最優先になります。{ } や、[ ] が出てきたときも同様に考えます。
これを考慮して考えると以下のようになります。

演算子	演算子そのものの優先順位	左右の優先順位
`=`	0	左 < 右
+	1	左 = 右
`*`	2	左 = 右
`(`	3	左 < 右
`)`	3	左 < 右

さらに、プログラムに直しやすくするために表を作り変えます。左右の優先順位の重みが同じものも順位をつけます。

演算子	左右の優先順位
=	1 < 2
+	4 > 3
*	6 < 5
(	0 > 8
)	7 > 0

また式の終わりを判別するため、ダミー演算子を用意します。
これが読み出された場合式を終了と判断します。

これらを表を元にスタックにつみ、ダミーが呼ばれた段階で次のステップに移行します。

3．意味解析

意味解析とは、この式が正しいものであるかどうかの正当性を検証します。
例えば、

ans = i + j;

といった式があるとします。
ここで確認することは、

ans, i, j は前もって定義されているかどうか。
ans, i, j の型は何か。
i, j に演算子 + は適用できるのか
ansに右辺を代入できるのか

といったことを確認します。

4. 実行

実行ステップとは、

int i = 2 + 3;

という式にたいして、

int 型のためのメモリを確保
変数名 i を登録
式を評価して結果を i に代入
変数に初期値を代入

というステップを行います。

以上でインタプリタ内部動作の大まかな解説は終了です。次回からそれらをプログラムとして動作するようにソースを書いていきたいと思います。