本当のコンパイラは,ファイルから文字列を読み込んで構文の解析 (文字列を木構造に変換する処理)を行い, その後でコード生成を行っています. 構文解析のプログラムもPrologで作成しようと思えば可能なのですが, ここでは,すでに構文解析は終わっているものとし, 命令は,Prologの項として与えられるとします. 命令中の変数は,Prologの記号(アトム)で表します.
また,コンパイル結果としては CASL プログラムを生成するとします.
たとえば,代入命令 a = a + b を以下のようにコンパイルしたいのです (実際には,このように簡潔なコードを生成するのは少し難しいのですが...).
| ?- c(a = a+b). LD GR1,a GR1に a の値をロード ADD GR1,b GR1に b の値を加える ST GR1,a GR1の値を a にストアこの場合,構文解析にあたる処理は,Prologが自動的に行っているのです.
まず,代入命令のコンパイルについて考えてみましょう. 代入命令をコンパイルするための述語名を c_assign として, それを呼び出すようにします.
c(X = A) :- /* 代入命令の場合 */ !, /* 他の規則は使わない */ c_assign(X, A). /* c_assign でコンパイルを行う */c_assignの中では,左辺がアトムかどうかを調べます. アトムでなければエラーと考えて,失敗します.
c_assign(X, A) :- atom(X), /* 左辺がアトムか? */ !, /* アトムなら他の規則は使わない */ ????? /* 代入命令のコードを生成 */ c_assign(_, _) :- /* 左辺がアトムでない場合 */ write('代入文の左辺は変数でなければならない'), fail.アトムの場合は,まず右辺の式をコンパイルする必要があります. 式をコンパイルする述語を c_exp とします. また, 右辺の式の結果が,どこに入っているかを決めておかなければなりません. ここでは,レジスタ GR1 に入っているとします. とすれば,代入は ST GR1,X で行えます(Xは変数であることに注意).
c_assign(X, A) :- atom(X), /* 左辺がアトムか? */ !, /* アトムなら他の規則は使わない */ c_exp(A), /* 右辺のコード生成,結果はGR1 */ ????? /* ST GR1,X を生成 */ c_assign(_, _) :- /* 左辺がアトムでない場合 */ write('代入文の左辺は変数でなければならない'), fail.CASL命令の生成は,プログラム中で何度も必要になるので, 述語を用意しておきましょう. instr(ニーモニック, オペランドのリスト) として呼び出します.
% % CASL命令の表示 % instr(Instr, Args) :- put(9), /* タブを表示 */ write(Instr), /* ニーモニック欄の表示 */ put(9), /* タブを表示 */ instr_args(Args), /* オペランド欄の表示 */ nl. /* 改行 */ instr_args([]). instr_args([A]) :- !, write(A). instr_args([A|Args]) :- write(A), write(','), instr_args(Args).すると,c_assign は以下のようになります.
c_assign(X, A) :- atom(X), /* 左辺がアトムか? */ !, /* アトムなら他の規則は使わない */ c_exp(A), /* 右辺のコード生成,結果はGR1 */ instr('ST', ['GR1',X]). /* ST GR1,X を生成 */ c_assign(_, _) :- /* 左辺がアトムでない場合 */ write('代入文の左辺は変数でなければならない'), fail.あとは,c_expを完成させる必要があります. つまり,色々な式のパターンに応じて,命令を生成するようにプログラム するわけです.
まず,整数の場合は,その値を GR1 にロードする命令を生成します (LEA命令を使います).
c_exp(A) :- integer(A), /* 整数の場合 */ !, instr('LEA', ['GR1',A]). /* LEA GR1,A を生成 */アトムの場合は,もとのプログラムの変数ですから, そのメモリの内容を GR1 にロードする命令を生成します(LD命令を使います).
c_exp(A) :- atom(A), /* 変数の場合 */ !, instr('LD', ['GR1',A]). /* LD GR1,A を生成 */A + Bの形の式の場合,まず B を計算する命令を生成して, その結果をスタックにプッシュする命令を生成します. 次に,A を計算する命令を生成して, スタックのてっぺんにある値(Bの値)を GR1 に加える命令を 生成します(GR4 が,スタックトップを指していることに注意). そして,スタックをポップする命令を生成すれば良いのです. ポップした値は必要ないのですが,POPを実行しておかないと, スタックポインタ GR4 が減る一方になってしまうので,POPを含めておきます. POPではなく,
LEA GR4,1,GR4
として,GR4 をインクリメントするのでもOKです.
c_exp(A + B) :- !, c_exp(B), /* Bのコードを生成 */ instr('PUSH', [0,'GR1']), /* PUSH 0,GR1 */ c_exp(A), /* Aのコードを生成 */ instr('ADD', ['GR1',0,'GR4']), /* ADD GR1,0,GR4 */ instr('POP', ['GR0']). /* POP GR0 */たとえば,a = a + b をコンパイルすると以下のようになります.
| ?- c(a = a+b). LD GR1,b bの値をGR1にロード PUSH 0,GR1 GR1の値をスタックにプッシュ LD GR1,a aの値をGR1にロード ADD GR1,0,GR4 スタックトップの値をGR1に加える POP GR0 スタックポップ ST GR1,a GR1の値をaにストア上のCASLプログラムの動作を C で書いてみると次のようになります.
GR1 = b; bの値をGR1にロード *(--GR4) = GR1 + 0; GR1の値をスタックにプッシュ GR1 = a; aの値をGR1にロード GR1 = GR1 + *GR4; GR1にスタックトップの値を加える GR0 = *GR4++; スタックポップ a = GR1; GR1の値をaにストアわかりにくいのは,2, 4, 5行目だと思います. 2行目では,まずGR4の値がデクリメントされ, GR4をアドレスと考えて,その番地に GR1 の値を書き込みます. 4行目でも,GR4をアドレスと考えて,その番地の内容を GR1 に加えています. 5行目も同様に,GR4をアドレスと考えて,その番地の内容を GR0 に代入し, GR4の値はインクリメントされます. GR0の値は利用しません.
最後に,プログラムの全体を示します.
% % 簡単なコンパイラ % % % 命令文のコンパイル % c(X = A) :- !, c_assign(X, A). % 代入命令 c_assign(X, A) :- atom(X), !, c_exp(A), instr('ST', ['GR1',X]). c_assign(_, _) :- write('代入命令の左辺は変数でなければならない'), fail. % % 式のコンパイル % c_exp(A) :- integer(A), !, instr('LEA', ['GR1',A]). c_exp(A) :- atom(A), !, instr('LD', ['GR1',A]). c_exp(A + B) :- !, c_exp(B), instr('PUSH', [0,'GR1']), c_exp(A), instr('ADD', ['GR1',0,'GR4']), instr('POP', ['GR0']). % % CASL命令の表示 % instr(Instr, Args) :- put(9), write(Instr), put(9), instr_args(Args), nl. instr_args([]). instr_args([A]) :- !, write(A). instr_args([A|Args]) :- write(A), write(','), instr_args(Args).以下にコンパイル例を示します(コメントも付け加えました).
| ?- c(a = x + y + 123). LEA GR1,123 GR1 = 123 PUSH 0,GR1 GR1 をスタックにPUSH LD GR1,y GR1 = y PUSH 0,GR1 GR1 をスタックにPUSH LD GR1,x GR1 = x ADD GR1,0,GR4 GR1 = GR1 + スタックトップ POP GR0 スタックPOP ADD GR1,0,GR4 GR1 = GR1 + スタックトップ POP GR0 スタックPOP ST GR1,a a = GR1うーむ,賢くない(10命令もあります). 次のようなコードが生成されればベストなのですが... このようなコードを生成することは,できるでしょうか? 皆さんの使っている C コンパイラなどでは, この程度は当たり前,もっとすごいコードを生成しています.
LD GR1,x GR1 = x ADD GR1,y GR1 = GR1 + y LEA GR1,123,GR1 GR1 = GR1 + 123 ST GR1,a a = GR1コンパイラについて,さらに勉強したい人は, 言語工学 のページにあげてある「関連する分野の参考書」を参考にしてください.