川合のプログラミング言語自作のためのテキスト第三版#8
(1) HL-8
- 今回は、ブロックifとfor文を追加します。
- （以下準備中）
#include <stdlib.h>
#include <string.h>
#include <time.h>
typedef unsigned char *String; // こう書くと String は unsigned char * の代用になる.
int loadText(String path, String t, int siz) → HL-4と同じなので省略
///////////////////////////////////////////////////////////////////////////////
#define MAX_TC 1000 // トークンコードの最大値.
String ts[MAX_TC + 1]; // トークンの内容(文字列)を記憶.
int tl[MAX_TC + 1]; // トークンの長さ.
unsigned char tcBuf[(MAX_TC + 1) * 10]; // トークン1つ当たり平均10バイトを想定.
int tcs = 0, tcb = 0;
int var[MAX_TC + 1]; // 変数.
int getTc(String s, int len) → HL-4と同じなので省略
///////////////////////////////////////////////////////////////////////////////
int isAlphabetOrNumber(unsigned char c) → HL-2と同じなので省略
int lexer(String s, int tc[]) → HL-2と同じなので省略
int tc[10000]; // トークンコード.
enum { TcSemi = 0, TcDot, TcWiCard, Tc0, Tc1, Tc2, Tc3, Tc4, Tc5, Tc6, Tc7, Tc8, TcEEq, TcNEq, TcLt, TcGe, TcLe, TcGt,
TcBrOpn, TcBrCls, TcSqBrOpn, TcSqBrCls, TcPlus, TcMinus, TcAster, TcSlash, TcPerce, TcAnd, TcShr, TcPlPlus, TcEqu,
TcComma, TcExpr, TcExpr0, TcTmp0, TcTmp1, TcTmp2, TcTmp3, TcTmp4, TcTmp5, TcTmp6, TcTmp7, TcTmp8, TcTmp9 };
char tcInit[] = "; . !!* 0 1 2 3 4 5 6 7 8 == != < >= <= > ( ) [ ] + - * / % & >> ++ = , !!** !!*** _t0 _t1 _t2 _t3 _t4 _t5 _t6 _t7 _t8 _t9";
///////////////////////////////////////////////////////////////////////////////
int phrCmp_tc[32 * 100], ppc1, wpc[9], wpc1[9]; // ppc1:一致したフレーズの次のトークンをさす, wpc[]:ワイルドカードのトークンの場所をさす.
int phrCmp(int pid, String phr, int pc) → HL-7と同じなので省略
///////////////////////////////////////////////////////////////////////////////
typedef int *IntP; // こう書くと IntP は int * の代わりに使えるようになる.
enum { OpCpy = 0, OpAdd, OpSub, OpMul, OpDiv, OpMod, OpAnd, OpShr, OpCeq, OpCne, OpClt, OpCge, OpCle, OpCgt,
OpAdd1, OpNeg, OpGoto, OpJeq, OpJne, OpJlt, OpJge, OpJle, OpJgt, OpLop, OpPrint, OpTime, OpEnd };
IntP ic[10000], *icq; // ic[]:内部コード、icq:ic[]への書き込み用ポインタ.
void putIc(int op, IntP p0, IntP p1, IntP p2, IntP p3) → HL-6と同じなので省略
///////////////////////////////////////////////////////////////////////////////
char tmp_flag[10]; // 一時変数の利用状況を管理.
int tmpAlloc() → HL-7と同じなので省略
void tmpFree(int i) → HL-7と同じなので省略
///////////////////////////////////////////////////////////////////////////////
int epc, epc1; // exprのためのpcとpc1.
int exprSub(int priority); // exprSub1()が参照するので、プロトタイプ宣言.
int expr(int j);
int exprSub1(int i, int priority, int op) → HL-7と同じなので省略
int exprSub(int priority) → HL-7と同じなので省略
int expr(int j) → HL-7と同じなので省略
///////////////////////////////////////////////////////////////////////////////
enum { IfTrue = 0, IfFalse = 1 };
void ifgoto(int i, int not, int label)
{
int j = wpc[i];
if (j + 3 == wpc1[i] && TcEEq <= tc[j + 1] && tc[j + 1] <= TcGt) { // 条件式の長さが3トークンで、真ん中が比較演算子だったら.
putIc(((tc[j + 1] - TcEEq) ^ not) + OpJeq, &var[label], &var[tc[j]], &var[tc[j + 2]], 0);
} else {
i = expr(i);
putIc(OpJne - not, &var[label], &var[i], &var[Tc0], 0);
tmpFree(i);
}
}
int tmpLabelNo;
int tmpLabelAlloc()
{
char s[10];
sprintf(s, "_l%d", tmpLabelNo);
tmpLabelNo++;
return getTc(s, strlen(s));
}
#define BInfSiz 10
int binf[BInfSiz * 100], bd, lbd; // binf:block-info, bd:block-depth, lbd:loop-block-depth
enum { BlkIf = 1, BlkFor };
enum { IfLabel0 = 1, IfLabel1 };
enum { ForLopBgn = 1, ForCont, ForBrk, ForLbd0, ForWpc01, ForWpc11, ForWpc02, ForWpc12 };
///////////////////////////////////////////////////////////////////////////////
int compile(String s)
{
! int pc, pc1, i, j;
! IntP *icq1, *icp;
pc1 = lexer(s, tc);
tc[pc1++] = TcSemi; // 末尾に「;」を付け忘れることが多いので、付けてあげる.
tc[pc1] = tc[pc1 + 1] = tc[pc1 + 2] = tc[pc1 + 3] = TcDot; // エラー表示用のために末尾にピリオドを登録しておく.
icq = ic;
for (i = 0; i < 10; i++) { ・// 一時変数をすべて未使用にする.
tmp_flag[i] = 0;
}
+ tmpLabelNo = 0; // new
+ bd = lbd = 0;
for (pc = 0; pc < pc1; ) { // コンパイル開始.
! int e0 = 0, e2 = 0;
if (phrCmp( 1, "!!*0 = !!*1;", pc)) { // 単純代入.
putIc(OpCpy, &var[tc[wpc[0]]], &var[tc[wpc[1]]], 0, 0);
} else if (phrCmp(10, "!!*0 = !!*1 + 1; if (!!*2 < !!*3) goto !!*4;", pc) && tc[wpc[0]] == tc[wpc[1]] && tc[wpc[0]] == tc[wpc[2]]) {
putIc(OpLop, &var[tc[wpc[4]]], &var[tc[wpc[0]]], &var[tc[wpc[3]]], 0);
} else if (phrCmp( 9, "!!*0 = !!*1 + 1;", pc) && tc[wpc[0]] == tc[wpc[1]]) { // 高速化のために+1専用の命令を用意(せこくてすみません).
putIc(OpAdd1, &var[tc[wpc[0]]], 0, 0, 0);
} else if (phrCmp( 2, "!!*0 = !!*1 + !!*2;", pc)) { // 加算.
putIc(OpAdd, &var[tc[wpc[0]]], &var[tc[wpc[1]]], &var[tc[wpc[2]]], 0);
} else if (phrCmp( 3, "!!*0 = !!*1 - !!*2;", pc)) { // 減算.
putIc(OpSub, &var[tc[wpc[0]]], &var[tc[wpc[1]]], &var[tc[wpc[2]]], 0);
} else if (phrCmp( 4, "print !!**0;", pc)) { // print.
e0 = expr(0);
putIc(OpPrint, &var[e0], 0, 0, 0);
} else if (phrCmp( 0, "!!*0:", pc)) { // ラベル定義命令.
var[tc[wpc[0]]] = icq - ic; // ラベルに対応するicqを記録しておく.
} else if (phrCmp( 5, "goto !!*0;", pc)) { // goto.
! putIc(OpGoto, &var[tc[wpc[0]]], &var[tc[wpc[0]]], 0, 0); // OpGotoの仕様変更.
! } else if (phrCmp( 6, "if (!!**0) goto !!*1;", pc) && TcEEq <= tc[wpc[1]] && tc[wpc[1]] <= TcLt) {
! ifgoto(0, IfTrue, tc[wpc[1]]);
} else if (phrCmp( 7, "time;", pc)) {
putIc(OpTime, 0, 0, 0, 0);
} else if (phrCmp( 8, "!!***0;", pc)) { // これはかなりマッチしやすいので最後にする.
e0 = expr(0);
} else
goto err;
tmpFree(e0);
+ tmpFree(e2);
! if (e0 < 0 || e2 < 0) goto err;
pc = ppc1;
}
if (bd > 0) {
printf("block nesting error (bd=%d, lbd=%d, pc=%d, pc1=%d\n", bd, lbd, pc, pc1);
return -1;
}
putIc(OpEnd, 0, 0, 0, 0);
icq1 = icq;
for (icq = ic; icq < icq1; icq += 5) { // goto先の設定.
i = (int) icq[0];
if (OpGoto <= i && i <= OpLop) {
+ icp = *icq[1] + ic;
+ while ((int) icp[0] == OpGoto) { // 飛び先がOpGotoだったら、さらにその先を読む(最適化).
+ icp = *icp[2] + ic;
+ }
! icq[1] = (IntP) icp;
}
}
return icq1 - ic;
err:
printf("syntax error : %s %s %s %s\n", ts[tc[pc]], ts[tc[pc + 1]], ts[tc[pc + 2]], ts[tc[pc + 3]]);
return -1;
}
void exec()
{
（中略）
+ case OpJge: if (*icp[2] >= *icp[3]) { icp = (IntP *) icp[1]; continue; } icp += 5; continue;
+ case OpJle: if (*icp[2] <= *icp[3]) { icp = (IntP *) icp[1]; continue; } icp += 5; continue;
+ case OpJgt: if (*icp[2] > *icp[3]) { icp = (IntP *) icp[1]; continue; } icp += 5; continue;
（中略）
}
int run(String s) → HL-6と同じなので省略
///////////////////////////////////////////////////////////////////////////////
int main(int argc, const char **argv) → HL-5と同じなので省略
- トータルの行数は445行になっています。かなり増えました。しかしかっこよさもかなり増しています。
- 次に、連続代入ができるようになりました。「x = y = z = 0;」とかそういうやつです。
- HL-6aまでは、なんかこう「おもちゃ言語」の感じがしていた気がするのですが、一気にまともになった気がします！
(2) HL-7の簡単な説明
- 関数：
- void loadText(String path, String t, int siz)
- ファイルパスpathで指定されたソースファイルをtに読み込む。sizはtの最大サイズを表す（これを超える長さのファイルは途中で打ち切られる）。
- int getTc(String s, int len)
- トークン（単語）をsに渡すと、それに対応するトークンコード（整数）を返す。
- int isAlphabetOrNumber(unsigned char c)
- 引数で渡された文字コードが、英数字であれば1を返す。それ以外なら0を返す。
- アンダースコアもHL-6の中ではアルファベットということにしておく。そうすることで、変数の一文字目に使えるようになる。
- この関数は以下のlexer()の下請け。
- int lexer(String s, int tc[])
- sにプログラムのソースコードを渡す。すると、tc[]にトークンコード（単語番号）に変換させられた数列が入って返される。
- より詳しい動作は、a21_txt01_2aを参照のこと。
- int phrCmp(int pid, String phr, int pc)
- tc[pc]からのトークンコード列がphrで指定されたトークン列と一致するかどうか調べる。
- pidはフレーズIDで、この番号を使ってphrCmp_tc[]のどこにphrのlexer結果をしまっておくかを決めている。
- なお、処理できるフレーズの最大長はこのプログラムの場合は31トークンである。
- HL-7以降のphrCmpでは、以下の3種類のワイルドカードが使える。
- [1] !!*# : 任意の1トークンにマッチする（#は0～8までの数字）（これはHL-5のバージョンでも使えた）
- [2] !!**# : 任意の式にマッチする（#は0～8までの数字）（ただし式は1トークン以上の長さでなければいけない）
- [3] !!***# : 任意の式にマッチする（#は0～8までの数字）（ただし式は長さゼロでもよい）
- void putIc(int op, IntP p1, IntP p2, IntP p3, IntP p4)
- 引数で渡された内容を内部コードのic[]に書き込む関数。関数compile()を書きやすくするための便利関数。
- int tmpAlloc()
- 未使用の一時変数を確保。変数名のトークンコードで返す。
- compile()の下請け関数。
- void tmpFree(int i)
- iが一時変数を指すトークンコードであれば、その一時変数を未使用状態に戻す。
- そうでなければ、何もしない。
- compile()の下請け関数。
- int exprSub1(int i, int priority, int op)
- 二項演算子処理の標準形。exprSub()の下請け関数。
- int exprSub(int priority)
- 式の解釈の処理の主要部分。expr()の下請け関数。
- int expr(int j)
- 式の解釈処理のための便利関数。
- exprSub()が動けるように、変数epc、epc1などを準備して、その上でexprSub()を呼び出す。
- exprSub()の中でphrCmp()やexpr()を呼び出すこともあり得るので、wpc[]などの退避・復元処理も行う。
- 引数jは、ワイルドカード番号で、そのワイルドカードにマッチした式をコンパイルしてic[]に書き込む。
- int compile(String s)
- 与えられた文字列をプログラムだと解釈して、内部コードを生成しic[]へ出力する。
- 関数run()の下請け関数。
- void exec()
- ic[]に格納された内部コードを高速に実行する。
- 関数run()の下請け関数。
- int run(String s)
- 言語処理の本体。HL-3までのmain()に相当。
- 内部的にはcompile()してrun()しているだけ。
- int main(int argc, const char **argv)
- 変数：
- String ts[]
- getTc()が管理している配列変数で、トークンコードからトークン文字列を得るために使う。
- int tl[]
- getTc()が管理している配列変数で、トークンコードからトークン文字列の長さを得るために使う。
- unsigned char tcBuf[]
- getTc()が管理している変数で、トークン文字列の実体を保存しておくための場所。
- int tcs, tcb
- どちらもgetTc()が管理している変数で、tcsは今までに発行したトークンコードの個数（0～tcs-1が発行済み）。
- tcbはtcBuf[]の未使用領域を指している。
- もしtcBuf[]やtcbの役割がピンとこない場合は、a21_txt01_2bを参照。
- int var[]
- 変数の値を記憶しておくための変数。トークンコードをそのまま変数番号に転用している。
- int tc[]
- プログラムをトークンコード列に変換したものがここに入る。
- int phrCmp_tc[]
- phrCmp()が管理している変数で、phrCmp_tc[]にはフレーズのlexer()の結果を保存する。
- int ppc1, wpc[], wpc1[]
- フレーズが一致した場合、ppc1に一致したフレーズの次のトークンの位置が入る。
- wpc[]にはワイルドカードで一致した位置が入る。
- ワイルドカードが式の場合、wpc1[]には式の終端が入る（厳密には式の直後のトークンを指す）
- IntP ic[], *icq
- ic[]は内部コード（internal-code）を格納しておくための変数。icqはputIc()関数が次にicのどこに書き込むのかを覚えておくための変数。
- int epc, epc1
- HL-7の見どころは何といっても式の評価です。しかもそれをスタックの仕組みを一切使わず、それでいて難解にもならずに仕上げられたところが、私としては気に入っています。だからそこを中心に説明したいと思います。
(3) 式の評価について （exprSub(), exprSub1(), tmpAlloc(), tmpFree()）
- ここでの式の評価というのは、つまり
print a + b - c * d + e
- みたいなプログラムをコンパイルした時に
OpAdd(_t0, a, b ); // _t0 = a + b
OpMul(_t1, c, d ); // _t1 = c * d
OpSub(_t2, _t0, _t1); // _t2 = _t0 - _t1
OpAdd(_t0, _t2, e ); // _t0 = _t2 + e
OpPrint(_t0);
- みたいな内部コード列に変換することです。基本的には式を左から右へ評価しつつも（足し算・引き算）、途中で高い優先度を持つ演算子（掛け算）が来たときは、先にそれを計算して、その結果を一つのかたまりとして加減算を再開します。
- これが難なくできるようになることがゴールです。このことだけに集中すれば、式の評価なんて大したことはありません。
- exprSub()という関数が、この式の評価の大半を処理しています。
- それではここで、exprSub(99)した場合を考えてみましょう。
- exprSub()では、変数epcを使って式を解釈していきます。
- 関数に入ると、まずはepcの場所にカッコや前置演算子が来ていないかどうかを確認します。もしそれらがあれば、対応する処理をしなければいけません。でもいきなり最初からかっこや前置演算子の話をするとややこしくなるだけなので、今はそれらは全くない場合だけを考えます。
- そうすると処理は
} else { // 変数もしくは定数.
i = tc[epc];
epc++;
}
- ここに来ます。これで、iに変数のトークンコード番号が入ります。
- もし「print a;」のように、後続の演算子がなければ、このiの値（＝aのトークンコード）がそのままreturnされます。何も難しいことはありません。
- さてもしこの後に演算子が来るとどうでしょうか。たとえば二項演算子の「+」がある場合を考えましょう。その場合、ここに来ることになります。
} else if (TcPlus <= tc[epc] && tc[epc] <= TcMinus && priority >= 5) {
i = exprSub1(i, 4, tc[epc] - TcPlus + OpAdd); // 左結合なので5より1小さくする.
- このif文の意味するところは、epcの場所に書いてあるトークンが「+」もしくは「-」で、かつexprSub()を呼ばれたときの引数が5よりも大きかったら、ということです。今は99で呼んでいるわけですから、ここは問題なく成立します。あとでこの条件の必要性も説明しますので、今は気にしないでください。
- このif文が成立するとどうなるのかというと、exprSub1()を使って二項演算子の処理をするのですが、それではその部分を説明のために上記の引数で展開してみます。
epc++;
j = exprSub(4);
k = tmpAlloc();
putIc(op, &var[k], &var[i], &var[j], 0);
tmpFree(i);
tmpFree(j);
i = k;
- やっていることは、まずepc++して、「+」を読み進めます。
- 次に、exprSub(4)を呼び出して、その結果をjで受けます。これはつまり、演算子の後ろにある項を1つ取ってこいという意味です。そしてその際には、優先度が4以下の優先度の高い演算ついてはどんどん結合して演算して結果を出してから帰ってこい、と、そういうことなのです。しかし優先度5以上の優先度の低いものは勝手に計算してまとめてはいけません。ちなみに優先度5というのは「+」や「-」のことです。
- こうすることで、掛け算とか割り算を含む項が後続していれば、それについては演算した結果を渡してもらえることになります。そうでなければ、単に次のトークンコードが返ってくることになります。
- その次に tmpAlloc() を実行して、それをkに入れます。これはつまり、_t0みたいな変数をひとつ持ってくるだけです。とにかく加算結果をどこかの変数に入れなければいけないので、適当な一時変数を準備しているのです。
- 次のputIc()で内部コードを生成しています。opの部分は、「+」だったらOpAdd、「-」だったらOpSubになります。今の例では加算命令を出力することになります。
- 次の2つのtmpFree()で、もしiやjが一時変数であったら、未使用状態に戻します。なぜならもう演算のために使ったので、今後参照されることはないからです。もしtmpFree()の引数が一時変数でなければ特に何もしません。そういう仕様です（そうすることでif文を書く手間を減らしました）。
- そして最後に、iにkを代入します。これは、「ここまでの計算結果が入っている変数」がkに変わったということです。
- 以降はこの処理を、式の終わりまでやるか、もしくは指定された優先順位より大きい演算子（＝優先度の低い演算子）にぶつかるかするまで繰り返せば、私たちの欲しいものは得られるのです。
(4) 左結合と右結合について
- C言語のほとんどの演算子は左結合ですが、一部右結合のものがあります。まずは結合の違いを説明します。
- 「a + b - c」という式は、+も-も左結合の演算子なので、一番最初に実行されるのは、「_t0 = a + b」です。そしてその次に「_t1 = _t0 - c」が実行されます。優先度が同じものがあった場合、左を先に演算するという、ただそれだけのことです。これは当たり前に感じられるでしょう。
- 意外なのは右結合の演算子です。「a = b = 3」の場合、=は右結合の演算子なので、最初に実行されるのは「a = b」ではありません。「b = 3」なのです。そのあとに「a = b」が実行されます。
- でもこれは、そうでなければ困るというのがわかるでしょうか。「a = b = 3」と書いた時は、aもbも3になることが期待されているのです。もし左結合だったら、bしか3にならず、aはbの古い値が入っているだけになってしまうのです。
- exprSub()でこの右結合を実現するにはどうすればいいでしょうか。それは、優先度15の=の処理の時に、exprSub(14)ではなくexprSub(15)をすることなのです。そうすれば、後続の項の中に=が含まれていれば、それを全部putIc()で出力してから帰ってくるからです。
- 結局、左結合か右結合かは、exprSub()の再起呼び出しの際に、優先度を1引くか、そのままにするか、それだけの違いになります。
(5) その他のこまごまとした説明 （expr(), phrCmp(), comiple(), exec()）
- 関数expr()は、exprSub()を利用する際に必要な準備をして、exprSubを引数99で呼び出し、さらに呼び出し後の後片付けをしてくれる便利関数です。
- expr()の引数では、wpc[]の番号を指定します。この仕様にしておくと、compile()内で呼び出すのがすごく楽になるのでそうしました。
- そしてexpr()の処理中にphrCmp()やexpr()を利用するかもしれないことを考えて、epc値やepc[]値を保存しておき、それからepc, epc1に式の範囲をセットして、exprSub(99)を実行しています。
- その後は、保存した値をすべて復元して、終了しています。
- phrCmp()もHL-6aまでの内容に対してバージョンアップしています。
- 主な変更点は、任意の式にマッチする !!** や !!*** というワイルドカードを追加したことです。
- ただし、phrCmp()での式の判定はすごく雑で、「a + b」や「-3*a」みたいな正しい式にマッチする一方「+ +」とか「a b c」など、意味不明なトークンの並びでも通してしまいます。これは何をもって式とするのかは、将来的に考えが変わるかもしれないので、とにかくルーズにしておこうと思ったのです（それに判定をまじめにやるとプログラムが長くて複雑になる）。現状では、カッコの対応関係を雑にみている程度です。まあそれでも、対象が正しいプログラムであれば、これで問題なくマッチができています。
- ただそれだけであまりにも心配だと思ったので、expr()内で、式がちゃんと最後まで評価できているかをチェックするようにはしています。変な式だと評価が途中で終わるので、その場合はエラーにしています。
- compile()では、print命令と最後の任意の式のところだけに「!!**」や「!!***」を使いました。いきなりたくさん導入しても混乱すると思ったからです。
- 最後に任意の式の評価があるのだから、もう「!!*0 = !!*1 + !!*2;」とか「!!*0 = !!*1 - !!*2;」とかはいらないと思うかもしれません。でもこれはわざと残しました（まあ消すのが面倒だったということもありますが）。
- exec()では、追加された演算に対する演算命令をたくさん追加しました。でも難しいところは特にないはずです。
次回に続く
こめんと欄
![[PukiWiki]](image/pukiwiki.png "[PukiWiki]")
