川合のプログラミング言語自作のためのテキスト第三版#8a
(1) HL-8a
- もう少し詳しく言うと、こんな感じです。
- [1]変数の値（var[]）の型をintではなく、intptr_tにする。
- こうすることで、変数にポインタの値を入れることもできるようになります。それを使って配列や文字列リテラルをサポートします。
- intのままでも32bitなら問題ないけど、x64などのようにintとポインタの幅が異なる環境ではうまくいかなくなるので、一般的にはintptr_tにしたほうがよいのです。
- [2]getTc()やlexer()を改造して、文字列リテラルを受け付けるようにする。
- そしてcompile()にprints命令を追加して、exec()にOpPrintsを追加して、文字リテラルを表示できるようにします。
- [3]配列については、OpArySet, OpAryGet, OpAryNew, OpAryInitという内部命令を追加して、配列の操作をする。exprSub()とcompile()とexec()を改造して対応させる。
| icp[0] | icp[1] | icp[2] | icp[3] | icp[4] | 動作 | 説明 |
| OpPrints | p1 | | | | printf("%s\n", p1); | 文字列の表示 |
| OpAryNew | p1 | p2 | | | p1=new intptr_t[p2]; | 配列の準備 |
| OpAryInit | p1 | p2 | p3 | | memcpy(p1,p2,p3*sizeof(inttr_t)); | 配列への初期値代入 |
| OpArySet | p1 | p2 | p3 | | p1[p2]=p3; | 変数の値を配列へ代入 |
| OpAryGet | p1 | p2 | p3 | | p3=p1[p2]; | 配列の値を変数へ代入 |
- [4]ついでのおまけ。HL-8まででは加算と減算だけ「a=b+c;」みたいな形式を1内部命令にコンパイルする最適化をサポートしていたが、これをすべての二項演算子に拡大する。
#include <stdlib.h>
#include <string.h>
#include <time.h>
#include <stdint.h> // intptr_tを使うため.
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;
intptr_t var[MAX_TC + 1]; // 変数. (!)
int getTc(String s, int len) // トークン番号を得るための関数.
{
int i;
for (i = 0; i < tcs; i++) { // 登録済みの中から探す.
if (len == tl[i] && strncmp(s, ts[i], len) == 0)
break;
}
if (i == tcs) {
if (tcs >= MAX_TC) {
printf("too many tokens\n");
exit(1);
}
strncpy(&tcBuf[tcb], s, len); // 見つからなかったので新規登録.
tcBuf[tcb + len] = 0; // 終端文字コード.
ts[i] = &tcBuf[tcb];
tl[i] = len;
tcb += len + 1;
tcs++;
var[i] = strtol(ts[i], 0, 0); // 定数だった場合に初期値を設定（定数ではないときは0になる）.
+ if (ts[i][0] == 34) { // 先頭がダブルクォーテーション
+ char *p = malloc(len - 1);
+ var[i] = (intptr_t) p;
+ memcpy(p, ts[i] + 1, len - 2); // 手抜き実装.
+ p[len - 2] = 0;
+ }
}
return i;
}
///////////////////////////////////////////////////////////////////////////////
int isAlphabetOrNumber(unsigned char c) → HL-2と同じなので省略
int lexer(String s, int tc[]) // プログラムをトークンコード列に変換する.
{
int i = 0, j = 0, len; // i:今s[]のどこを読んでいるか、j:これまでに変換したトークン列の長さ.
for (;;) {
if (s[i] == ' ' || s[i] == '\t' || s[i] == '\n' || s[i] == '\r') { // スペース、タブ、改行.
i++;
continue;
}
if (s[i] == 0) // ファイル終端.
return j;
len = 0;
if (strchr("(){}[];,", s[i]) != 0) { // 1文字記号.
len = 1;
} else if (isAlphabetOrNumber(s[i])) { // 1文字目が英数字.
while (isAlphabetOrNumber(s[i + len]))
len++;
} else if (strchr("=+-*/!%&~|<>?:.#", s[i]) != 0) { // 1文字目が普通の記号.
while (strchr("=+-*/!%&~|<>?:.#", s[i + len]) != 0 && s[i + len] != 0)
len++;
+ } else if (s[i] == 34 || s[i] == 39) { // "文字列" or '文字'.
+ len = 1;
+ while (s[i + len] != s[i] && s[i + len] >= ' ')
+ len++;
+ if (s[i + len] == s[i])
+ len++;
} else {
printf("syntax error : %.10s\n", &s[i]);
exit(1);
}
tc[j] = getTc(&s[i], len);
i += len;
j++;
}
}
int tc[10000]; // トークンコード.
enum { TcSemi = 0, TcDot, TcWiCard, Tc0, Tc1, Tc2, Tc3, Tc4, Tc5, Tc6, Tc7, Tc8, TcBrOpn, TcBrCls, TcSqBrOpn, TcSqBrCls, TcCrBrOpn, TcCrBrCls,
TcEEq, TcNEq, TcLt, TcGe, TcLe, TcGt, 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 intptr_t *IntP; // こう書くと IntP は intptr_t * の代わりに使えるようになる. (!)
enum { OpCpy = 0, OpCeq, OpCne, OpClt, OpCge, OpCle, OpCgt, OpAdd, OpSub, OpMul, OpDiv, OpMod, OpAnd, OpShr,
! OpAdd1, OpNeg, OpGoto, OpJeq, OpJne, OpJlt, OpJge, OpJle, OpJgt, OpLop, OpPrint, OpTime, OpEnd,
+ OpPrints, OpAryNew, OpAryInit, OpArySet, OpAryGet };
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)
{
! int i = -1, e0 = 0, e1 = 0;
ppc1 = 0;
（中略）
for (;;) {
tmpFree(e0);
+ tmpFree(e1);
! if (i < 0 || e0 < 0|| e1 < 0) return -1; // ここまででエラーがあれば、処理を打ち切り.
if (epc >= epc1) break;
! e0 = e1 = 0;
if (tc[epc] == TcPlPlus) { // 後置インクリメント.
epc++;
e0 = i;
i = tmpAlloc();
putIc(OpCpy, &var[i], &var[e0], 0, 0);
putIc(OpAdd1, &var[e0], 0, 0, 0);
+ } else if (phrCmp(70, "[!!**0]=", epc) && priority >= 15) {
+ e1 = i;
+ e0 = expr(0);
+ epc = ppc1;
+ i = exprSub(15);
+ putIc(OpArySet, &var[e1], &var[e0], &var[i], 0);
+ } else if (phrCmp(71, "[!!**0]", epc)) {
+ e1 = i;
+ i = tmpAlloc();
+ e0 = expr(0);
+ putIc(OpAryGet, &var[e1], &var[e0], &var[i], 0);
+ epc = ppc1;
} else if (TcAster <= tc[epc] && tc[epc] <= TcPerce && priority >= 4) { // * / %
i = exprSub1(i, 3, tc[epc] - TcAster + OpMul); // 左結合なので4より1小さくする.
（中略）
}
int expr(int j) → HL-7と同じなので省略
///////////////////////////////////////////////////////////////////////////////
enum { IfTrue = 0, IfFalse = 1 };
void ifgoto(int i, int not, int label) → HL-8と同じなので省略
int tmpLabelNo;
int tmpLabelAlloc() → HL-8と同じなので省略
#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)
{
（中略）
} 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 !!*3;", pc) && TcEEq <= tc[wpc[2]] && tc[wpc[2]] <= TcShr) { // 加算, 減算など.
! putIc(tc[wpc[2]] - TcEEq + OpCeq, &var[tc[wpc[0]]], &var[tc[wpc[1]]], &var[tc[wpc[3]]], 0);
} else if (phrCmp( 4, "print !!**0;", pc)) { // print.
e0 = expr(0);
putIc(OpPrint, &var[e0], 0, 0, 0);
（中略）
} else if (phrCmp(19, "if ( !!**0 ) break;", pc) && lbd > 0) {
ifgoto(0, IfTrue, binf[lbd + ForBrk ]);
+ } else if (phrCmp(20, "prints !!**0;", pc)) { // prints.
+ e0 = expr(0);
+ putIc(OpPrints, &var[e0], 0, 0, 0);
+ } else if (phrCmp(21, "int !!*0[!!**2];", pc)) {
+ e2 = expr(2);
+ putIc(OpAryNew, &var[tc[wpc[0]]], &var[e2], 0, 0);
+ } else if (phrCmp(22, "int !!*0[!!**2] = {", pc)) {
+ e2 = expr(2);
+ putIc(OpAryNew, &var[tc[wpc[0]]], &var[e2], 0, 0);
+ j = 0;
+ for (i = ppc1; i < pc1; i++) { // コンマ以外のトークンを数える.
+ if (tc[i] == TcCrBrCls) break;
+ if (tc[i] != TcComma) {
+ j++;
+ }
+ }
+ if (i >= pc1) goto err;
+ intptr_t *ip = malloc(j * sizeof (intptr_t));
+ j = 0;
+ for (i = ppc1; tc[i] != TcCrBrCls; i++) {
+ if (tc[i] == TcCrBrCls) break;
+ if (tc[i] != TcComma) {
+ ip[j] = var[tc[i]];
+ j++;
+ }
+ }
+ putIc(OpAryInit, &var[tc[wpc[0]]], (IntP) ip, (IntP) j, 0);
+ ppc1 = i + 2; // } と ; の分.
} else if (phrCmp( 8, "!!***0;", pc)) { // これはかなりマッチしやすいので最後にする.
e0 = expr(0);
（中略）
}
void exec()
{
clock_t t0 = clock();
IntP *icp = ic;
! intptr_t i, *a;
for (;;) {
switch ((int) icp[0]) {
（中略）
+ case OpPrints:
+ printf("%s\n", (char *) *icp[1]);
+ icp += 5;
+ continue;
+ case OpAryNew:
+ *icp[1] = (intptr_t) malloc(*icp[2] * sizeof (intptr_t));
+ memset((char *) *icp[1], 0, *icp[2] * sizeof (intptr_t));
+ icp += 5;
+ continue;
+ case OpAryInit:
+ memcpy((char *) *icp[1], (char *) icp[2], ((int) icp[3]) * sizeof (intptr_t));
+ icp += 5;
+ continue;
+ case OpArySet:
+ a = (intptr_t *) *icp[1];
+ i = *icp[2];
+ a[i] = *icp[3];
+ icp += 5;
+ continue;
+ case OpAryGet:
+ a = (intptr_t *) *icp[1];
+ i = *icp[2];
+ *icp[3] = a[i];
+ icp += 5;
+ continue;
}
}
}
int run(String s) → HL-6と同じなので省略
///////////////////////////////////////////////////////////////////////////////
int main(int argc, const char **argv) → HL-5と同じなので省略
- トータルの行数は560行になっています。
- 後で説明しますが、ブロックifとfor文を入れただけではなく、OpGotoの最適化の追加や、今までサボっていたOpJge, OpJle, OpJgtの追加もしました。
(2) HL-8の簡単な説明
- 今回からは、HL-8で新規に追加されたもの、変更を加えた部分のみ説明します（長くなってきたので）。
- 関数：
- void ifgoto(int i, int not, int label)
- 条件式wpc[i]を評価して、その結果に応じてlabel（トークンコード）に分岐するコードを内部コードに出力します。
- notはフラグで、IfTrueの場合は、条件が成立した場合に分岐させます。IfFalseの場合は、条件が不成立の場合に分岐させます。
- int tmpLabelAlloc()
- 一時ラベル（一時変数のラベル版）を発行してトークンコードで返します。
- 一時ラベルは使い終わった後に再利用するということはないので、Freeはありません。
- 変数：
- int tmpLabelNo
- 一時ラベルのラベル名を重複なく生成するための通し番号です。
- int binf[], bd, lbd;
- binf[]はblock-info.で、つまりコードブロックの情報です。bdはblock-depthで、ブロックの深さ、lbdはループ命令（今はforしかないですが）のbdです。
- bdやlbdは1ずつ増減するのではなく、BInfSizずつ増減します。
- binf[bd]は今のコードブロックが何のコードブロックなのかを表します。現状では、BlkIfかBlkForしかありません。
- binf[bd - BInfSiz]は今のコードブロックの1つ外側、binf[bd - BInfSiz * 2]は今のコードブロックの2つ外側の情報になります。
- よし詳しい情報は、binf[bd + 1～]に入っています。
- こういう変数がないと、ソースコード中に「 } 」があっても、ifの終わりなのか、forの終わりなのか、すぐには判断できなくなってしまいます。
(3) ブロックif文について
- ブロックif文のためにcompile()に追加された部分を中心に説明します。
- まず HL-8 では、ブロックif文を次のように変換することで、実現しています。
} else if (phrCmp(11, "if ( !!**0 ) {", pc)) { // ブロックif.
bd += BInfSiz;
binf[bd] = BlkIf;
binf[bd + IfLabel0] = tmpLabelAlloc(); // 条件不成立のときの飛び先.
binf[bd + IfLabel1] = 0;
ifgoto(0, 1, binf[bd + IfLabel0]); // 条件を満たさなければ、binf[bd + IfLabel0]へgotoする.
- ブロックif文が現れたら、新しいコードブロックが始まるので、binf[]を準備します。
- そして_tmpLabel0を準備します。
- 最後に「if (!条件式) goto _tmpLabel0;」に相当する内部コードをifgoto()で生成します。
} else if (phrCmp(12, "} else {", pc) && binf[bd] == BlkIf) {
binf[bd + IfLabel1] = tmpLabelAlloc(); // else節の終端.
putIc(OpGoto, &var[binf[bd + IfLabel1]], &var[binf[bd + IfLabel1]], 0, 0);
var[binf[bd + IfLabel0]] = icq - ic; // ラベルに対応するicqを記録しておく.
- 「 } else { 」が来たら、これは上記の[2]の場合に相当します。
- _tmpLabel1も必要になるのでそれを準備したのち、goto _tmpLabel1;を出力します。
- ここで、OpGotoの仕様が変わって、飛び先を二度指定するようになっています。なぜそうしなければいけないかは後で説明します。
- そして、_tmpLabel0のラベルはここだよと宣言します。
- これで「 } else { 」の処理はおしまいです。
} else if (phrCmp( 13, "}", pc) && binf[bd] == BlkIf) {
if (binf[bd + IfLabel1] == 0) {
var[binf[bd + IfLabel0]] = icq - ic; // ラベルに対応するicqを記録しておく.
} else {
var[binf[bd + IfLabel1]] = icq - ic; // ラベルに対応するicqを記録しておく.
}
bd -= BInfSiz;
- ブロックif文のコードブロックを閉じたときの処理です。
- これは[1]の場合と[2]の場合とで異なります。
- [1]の場合は、「_tmpLabel0:」の処理をやります。
- [2]の場合は、「_tmpLabel1:」の処理をやります。
- 最後にbdをBInfSizだけ減じて、コードブロックを終了します。
(4) for文について
- 上記のブロックif文と似たような方法で、for文も実現しています。
- for文の変換は次のようにしています。
} else if (phrCmp(14, "for (!!***0; !!***1; !!***2) {", pc)) { // for文
bd += BInfSiz;
binf[bd] = BlkFor; // ブロックのタイプ.
binf[bd + ForLopBgn] = tmpLabelAlloc(); // ループの頭に戻る用.
binf[bd + ForCont ] = tmpLabelAlloc(); // continue用.
binf[bd + ForBrk ] = tmpLabelAlloc(); // break用.
binf[bd + ForLbd0 ] = lbd; // 古い値を保存.
binf[bd + ForWpc01 ] = wpc [1];
binf[bd + ForWpc11 ] = wpc1[1];
binf[bd + ForWpc02 ] = wpc [2];
binf[bd + ForWpc12 ] = wpc1[2];
lbd = bd;
e0 = expr(0);
if (wpc[1] < wpc1[1]) { // !!***1に何らかの式が書いてあった.
ifgoto(1, IfFalse, binf[bd + ForBrk]); // 最初から条件不成立ならbreakへ.
}
var[binf[bd + ForLopBgn]] = icq - ic; // ラベルに対応するicqを記録しておく.
- for文では、あとで（＝コードブロックを閉じるときに）条件式や式2の部分を利用するので、それらも全部binf[]にしまっておきます。
- 「e0 = expr(0);」で 式0 の部分を内部コードとして出力させます。
- そして条件式に何か書いてあれば、条件不成立時にはループに侵入しないようにします。
- 最後に _tmpLabel0: に相当する処理をしています。
} else if (phrCmp(15, "}", pc) && binf[bd] == BlkFor) {
var[binf[bd + ForCont]] = icq - ic; // ラベルに対応するicqを記録しておく.
i = binf[bd + ForWpc01];
j = binf[bd + ForWpc02];
if (i + 3 == binf[bd + ForWpc11] && j + 2 == binf[bd + ForWpc12] && tc[i] == tc[j] && tc[i + 1] == TcLt && tc[j + 1] == TcPlPlus) {
// !!***1が「i < ?」かつ、!!***2が「i++」だったら（変数名はiじゃなくてもいいけど、共通である必要がある）.
putIc(OpLop, &var[binf[bd + ForLopBgn]], &var[tc[i]], &var[tc[i + 2]], 0);
} else {
wpc [1] = binf[bd + ForWpc01];
wpc1[1] = binf[bd + ForWpc11];
wpc [2] = binf[bd + ForWpc02];
wpc1[2] = binf[bd + ForWpc12];
e2 = expr(2);
if (wpc[1] < wpc1[1]) { // !!***1に何らかの式が書いてあった.
ifgoto(1, IfTrue, binf[bd + ForLopBgn]);
} else {
putIc(OpGoto, &var[binf[bd + ForLopBgn]], &var[binf[bd + ForLopBgn]], 0, 0);
}
}
var[binf[bd + ForBrk]] = icq - ic; // ラベルに対応するicqを記録しておく.
lbd = binf[bd + ForLbd0]; // 以前の値を復元.
bd -= BInfSiz;
- これはfor文のコードブロックを閉じるときの処理です。
- ちょっと長くなっていますが、これはOpLopが使える場合には使ってやろうとして、そのせいでややこしくなっています。
- OpLopを使わない、一般の場合の処理を見れば、「 _tmpLabel1: 」したあとで、「e2 = expr(2);」で 式2 を内部コードに変換し、さらに条件式を評価させて _tmpLabel0 に条件分岐させています。
- そして最後に「 _tmpLabel2: 」しています。
} else if (phrCmp(16, "continue;", pc) && lbd > 0) {
putIc(OpGoto, &var[binf[lbd + ForCont]], &var[binf[lbd + ForCont]], 0, 0);
} else if (phrCmp(17, "break;", pc) && lbd > 0) {
putIc(OpGoto, &var[binf[lbd + ForBrk ]], &var[binf[lbd + ForBrk ]], 0, 0);
- これはcontinue文とbreak分です。どちらもOpGotoで無条件分岐しています。
} else if (phrCmp(18, "if ( !!**0 ) continue;", pc) && lbd > 0) {
ifgoto(0, IfTrue, binf[lbd + ForCont]);
} else if (phrCmp(19, "if ( !!**0 ) break;", pc) && lbd > 0) {
ifgoto(0, IfTrue, binf[lbd + ForBrk ]);
- これは条件付きのcontinueとbreak;です。ifgotoで処理しています。
(5) OpGoto最適化について
(6) ifgoto()の仕組みについて
- これは短くて簡単な関数ではありますが、説明があったほうがいいかもしれないと思ったので書きます。
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);
}
}
- まずnot=0、つまりIfTrueを指定した場合だけを考えます。
- すると、条件式の長さが3で、かつ真ん中が比較演算子の場合は、TcEEq～TcGtがそのままOpJeq～OpJgtになります（^0という演算は何もしないのと同じなので）。
- そしてそれ以外の場合は、式をexpr(i);で評価した後で、その結果がTc0と比較されて、OpJneで条件分岐することになります。
- 「式の値がゼロでなければ分岐せよ」なので、これでいいわけです。
- では今度はnot=1、つまりIfFalseを指定した場合だけを考えます。
- 条件式の長さが3で、かつ真ん中が比較演算子の場合、
| 真ん中の比較演算子(=tc[j+1]) | tc[j+1]-TcEEq(→A値) | A値^1(→B値) | B値+OpJeq |
| TcEEq(==) | 0 | 1 | OpJne(!=) |
| TcNEq(!=) | 1 | 0 | OpJeq(==) |
| TcLt (< ) | 2 | 3 | OpJge(>=) |
| TcGe (>=) | 3 | 2 | OpJlt(< ) |
| TcLe (<=) | 4 | 5 | OpJgt(> ) |
| TcGt (> ) | 5 | 4 | OpJle(<=) |
- とまあこんな風に計算されるおかげで、ちゃんと期待通り条件が不成立の時に分岐するようになります。
- それ以外の条件式の時は、OpJne-notがOpJeqになるので、式の値が0のときだけ分岐するようになり、これも期待通りになります。
次回に続く
こめんと欄
![[PukiWiki]](image/pukiwiki.png "[PukiWiki]")
