* 川合のプログラミング言語自作のためのテキスト第三版#7 -(by [[K]], 2021.03.09) ** (1) HL-7 -まずC言語の演算子一覧を書きます。 |優先順位|演算子|形式|名前|結合方向|HL-7| |1|( )|func(x,y,z)|関数呼び出し演算子|左|×| |1|[ ]|a[i]|添え字演算子|左|×| |1|.|abc.x|ドット演算子|左|×| |1|->|p->x|アロー演算子|左|×| |1|++|i++|後置インクリメント演算子|左|〇| |1|--|j--|後置デクリメント演算子|左|×| |2|++|++i|前置インクリメント演算子|右|〇| |2|--|--j|後置デクリメント演算子|右|×| |2|sizeof|sizeof a|sizeof演算子|右|×| |2|&|&x|単項&演算子|右|×| |2|*|*p|単項*演算子|右|×| |2|+|+a|単項+演算子|右|×| |2|-|-b|単項-演算子|右|〇| |2|~|~i|補数演算子|右|×| |2|!|!j|論理否定演算子|右|×| |3|( )|(typ)obj|型キャスト演算子|右|×| |4|*|x * y|二項*演算子|左|〇| |4|/|x / y|除算演算子|左|〇| |4|%|x % y|剰余演算子|左|〇| |5|+|x + y|二項+演算子|左|〇| |5|-|x - y|二項-演算子|左|〇| |6|<< >>|i << j など|シフト演算子|左|△| |7|< <= > >=|x < y など|比較演算子|左|〇| |8|== !=|x == y など|比較演算子|左|〇| |9|&|i & j|ビットAND演算子|左|〇| |10|^|i ^ j|ビットXOR演算子|左|×| |11|||i | j|ビットOR演算子|左|×| |12|&&|i && j|論理AND演算子|左|×| |13||||i || j|論理OR演算子|左|×| |14|? :|x ? y : z|条件演算子|右|×| |15|=|x = y|単純代入演算子|右|〇| |15|+= -= など|x += y など|複合代入演算子|右|×| |16|,|x, y|コンマ演算子|左|×| -全部の演算子をサポートするとHL-7のプログラムが長くなってしまうので、この中の一部だけを実装することにします、残りは拡張したい人が拡張するということにします。 -この取り合わせだと「この演算子があって、あの演算子がないのはなぜだ!」みたいに思うかもしれませんが、それはこの先のHL-9aのサンプルアプリで必要になる演算子を入れるようにしたためです。だから深い理由はありません。 #include <stdio.h> #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[100 * 32], ppc1, wpc[9], wpc1[9]; // ppc1:一致したフレーズの次のトークンをさす, wpc[]:ワイルドカードのトークンの場所をさす. int phrCmp(int pid, String phr, int pc) // HL-5のとは違う(改造). { int i0 = pid * 32, i, i1, j, k, t; if (phrCmp_tc[i0 + 31] == 0) { i1 = lexer(phr, &phrCmp_tc[i0]); phrCmp_tc[i0 + 31] = i1; } i1 = phrCmp_tc[i0 + 31]; for (i = 0; i < i1; i++) { t = phrCmp_tc[i0 + i]; if (t == TcWiCard || t == TcExpr || t == TcExpr0) { i++; j = phrCmp_tc[i0 + i] - Tc0; // 後続の番号を取得. wpc[j] = pc; if (t == TcWiCard) { pc++; continue; } k = 0; // カッコの深さ. for (;;) { if (tc[pc] == TcSemi) break; if (tc[pc] == TcComma && k == 0) break; if (tc[pc] == TcBrOpn || tc[pc] == TcSqBrOpn) k++; // 手抜きで ( と [ を区別せずに数えている. if (tc[pc] == TcBrCls || tc[pc] == TcSqBrCls) k--; if (k < 0) break; pc++; } wpc1[j] = pc; // 式の終了位置を記憶. if (t == TcExpr && wpc[j] == pc) return 0; // "!!**"では、長さ0は不一致とする. if (k > 0) return 0; // カッコの深さがおかしい時も不一致とする. continue; } if (t != tc[pc]) return 0; // マッチせず. pc++; } ppc1 = pc; return 1; // マッチした. } /////////////////////////////////////////////////////////////////////////////// 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() // 未使用の一時変数を確保. { int i; for (i = 0; i < 10; i++) { if (tmp_flag[i] == 0) break; } if (i >= 10) { printf("tmpAlloc: error\n"); return -1; } tmp_flag[i] = 1; return i + TcTmp0; } void tmpFree(int i) // 一時変数を未使用に戻す. ただし、指定されたトークンコードが一時変数でないときは何もしない. { if (TcTmp0 <= i && i <= TcTmp9) { tmp_flag[i - TcTmp0] = 0; } } /////////////////////////////////////////////////////////////////////////////// int epc, epc1; // exprのためのpcとpc1. int exprSub(int priority); // exprSub1()が参照するので、プロトタイプ宣言. int expr(int j); int exprSub1(int i, int priority, int op) // 二項演算子の処理の標準形. { int j, k; epc++; j = exprSub(priority); k = tmpAlloc(); putIc(op, &var[k], &var[i], &var[j], 0); tmpFree(i); tmpFree(j); if (i < 0 || j < 0) return -1; return k; } int exprSub(int priority) { int i = -1, e0 = 0; ppc1 = 0; if (phrCmp(99, "( !!**0 )", epc)) { // かっこ. i = expr(0); } else if (tc[epc] == TcPlPlus) { // 前置インクリメント. epc++; i = exprSub(2); putIc(OpAdd1, &var[i], 0, 0, 0); } else if (tc[epc] == TcMinus) { // 単項マイナス. epc++; e0 = exprSub(2); i = tmpAlloc(); putIc(OpNeg, &var[i], &var[e0], 0, 0); } else { // 変数もしくは定数. i = tc[epc]; epc++; } if (ppc1 > 0) epc = ppc1; for (;;) { tmpFree(e0); if (i < 0 || e0 < 0) return -1; // ここまででエラーがあれば、処理を打ち切り. if (epc >= epc1) break; e0 = 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 (TcAster <= tc[epc] && tc[epc] <= TcPerce && priority >= 4) { // * / % i = exprSub1(i, 3, tc[epc] - TcAster + OpMul); // 左結合なので4より1小さくする. } else if (TcPlus <= tc[epc] && tc[epc] <= TcMinus && priority >= 5) { i = exprSub1(i, 4, tc[epc] - TcPlus + OpAdd); // 左結合なので5より1小さくする. } else if (tc[epc] == TcShr && priority >= 6) { i = exprSub1(i, 5, OpShr); // 左結合なので6より1小さくする. } else if (TcLt <= tc[epc] && tc[epc] <= TcGt && priority >= 7) { i = exprSub1(i, 6, tc[epc] - TcLt + OpClt); // 左結合なので7より1小さくする. } else if (TcEEq <= tc[epc] && tc[epc] <= TcNEq && priority >= 8) { i = exprSub1(i, 7, tc[epc] - TcEEq + OpCeq); // 左結合なので8より1小さくする. } else if (tc[epc] == TcAnd && priority >= 9) { i = exprSub1(i, 8, OpAnd); // 左結合なので9より1小さくする. } else if (tc[epc] == TcEqu && priority >= 15) { epc++; e0 = exprSub(15); // 右結合なので15のまま. putIc(OpCpy, &var[i], &var[e0], 0, 0); } else break; } return i; } int expr(int j) { int i, k, old_epc = epc, old_epc1 = epc1, s[19]; // epc, epc1を保存する. if (wpc[j] == wpc1[j]) return 0; for (k = 0; k < 9; k++) { // wpc[], wpc1[]を保存する. s[k] = wpc [k]; s[k + 9] = wpc1[k]; } s[18] = ppc1; // ppc1を保存する. epc = wpc [j]; // epc, epc1を準備してexprSub()を呼び出す. epc1 = wpc1[j]; i = exprSub(99); if (epc < epc1) return -1; // 式を最後まで解釈できなかったらエラー. epc = old_epc; // 保存しておいた変数をすべて復元する. epc1 = old_epc1; for (k = 0; k < 9; k++) { wpc [k] = s[k]; wpc1[k] = s[k + 9]; } ppc1 = s[18]; return i; } /////////////////////////////////////////////////////////////////////////////// int compile(String s) { int pc, pc1, i; IntP *icq1; 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; } for (pc = 0; pc < pc1; ) { // コンパイル開始. int e0 = 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]]], 0, 0, 0); } else if (phrCmp( 6, "if (!!*0 !!*1 !!*2) goto !!*3;", pc) && TcEEq <= tc[wpc[1]] && tc[wpc[1]] <= TcLt) { putIc(OpJeq + (tc[wpc[1]] - TcEEq), &var[tc[wpc[3]]], &var[tc[wpc[0]]], &var[tc[wpc[2]]], 0); } 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); if (e0 < 0) goto err; pc = ppc1; } 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) { icq[1] = (IntP) (*icq[1] + ic); } } 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() { clock_t t0 = clock(); IntP *icp = ic; int i; for (;;) { switch ((int) icp[0]) { case OpNeg: *icp[1] = - *icp[2]; icp += 5; continue; case OpAdd1: (*icp[1])++; icp += 5; continue; case OpMul: *icp[1] = *icp[2] * *icp[3]; icp += 5; continue; case OpDiv: *icp[1] = *icp[2] / *icp[3]; icp += 5; continue; case OpMod: *icp[1] = *icp[2] % *icp[3]; icp += 5; continue; case OpAdd: *icp[1] = *icp[2] + *icp[3]; icp += 5; continue; case OpSub: *icp[1] = *icp[2] - *icp[3]; icp += 5; continue; case OpShr: *icp[1] = *icp[2] >> *icp[3]; icp += 5; continue; case OpClt: *icp[1] = *icp[2] < *icp[3]; icp += 5; continue; case OpCge: *icp[1] = *icp[2] >= *icp[3]; icp += 5; continue; case OpCle: *icp[1] = *icp[2] <= *icp[3]; icp += 5; continue; case OpCgt: *icp[1] = *icp[2] > *icp[3]; icp += 5; continue; case OpCeq: *icp[1] = *icp[2] == *icp[3]; icp += 5; continue; case OpCne: *icp[1] = *icp[2] != *icp[3]; icp += 5; continue; case OpAnd: *icp[1] = *icp[2] & *icp[3]; icp += 5; continue; case OpCpy: *icp[1] = *icp[2]; icp += 5; continue; case OpPrint: printf("%d\n", *icp[1]); icp += 5; continue; case OpGoto: icp = (IntP *) icp[1]; continue; case OpJeq: if (*icp[2] == *icp[3]) { icp = (IntP *) icp[1]; continue; } icp += 5; continue; case OpJne: if (*icp[2] != *icp[3]) { icp = (IntP *) icp[1]; continue; } icp += 5; continue; case OpJlt: if (*icp[2] < *icp[3]) { icp = (IntP *) icp[1]; continue; } icp += 5; continue; case OpTime: printf("time: %.3f[sec]\n", (clock() - t0) / (double) CLOCKS_PER_SEC); icp += 5; continue; case OpEnd: return; case OpLop: i = *icp[2]; i++; *icp[2] = i; if (i < *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行になっています。かなり増えました。しかしかっこよさもかなり増しています。 -まず、print命令で、単に変数や定数を指定するだけではなく、式が書けるようになりました。 >print 1+2*3 7 >print (1+2)*3 9 -こんなふうに、ちゃんと演算子の優先順位も反映されます。 -次に、連続代入ができるようになりました。「x = y = z = 0;」とかそういうやつです。 -インクリメントもできます。 >a = 0; print ++a; print a 1 1 >a = 0; print a++; print a 0 1 -この違いがわかるでしょうか。C言語では、前置インクリメントと後置インクリメントは意味が違うのです。それもきちんと真似できています。 -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) ---REPLの処理をしている。 -変数: --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 ---exprのためのpc, pc1に相当。 ---- -(準備中) ** 次回に続く -次回: ''a21_txt01_8'' *こめんと欄 #comment