川合のプログラミング言語自作のためのテキスト第三版#8a

  • (by K, 2021.03.16)

(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]動作説明
      OpPrintsp1printf("%s\n", p1);文字列の表示
      OpAryNewp1p2p1=new intptr_t[p2]; (malloc)配列の準備
      OpAryInitp1p2p3memcpy(p1,p2,p3*sizeof(inttr_t));配列への初期値代入
      OpArySetp1p2p3p1[p2]=p3;変数の値を配列へ代入
      OpAryGetp1p2p3p3=p1[p2];配列の値を変数へ代入
    • [4]ついでのおまけ。HL-8まででは加算と減算だけ「a=b+c;」みたいな形式を1内部命令にコンパイルする最適化をサポートしていたが、これをすべての二項演算子に拡大する。
#include <stdio.h>
#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と同じなので省略
  • プログラムは635行になりました。49行から始まって、思えば遠くまで来たものです。
  • この先にHL-9やHL-9aもありますが、それらはお遊びみたいなもので、言語そのものの強化ではないので、言語としてはHL-8aでひとまずの完成と言えるかもしれません。

  • HL-8aにはprints命令があります。
    >prints "hello"
    hello
  • まあ、それだけなのですが・・・。まあ一応、以下みたいなこともできます。
    a = "abc";
    if (x > y) {
        a = "def";
    }
    prints a;
  • HL-8aでは配列も使えます。
    >int a[30] = { 1, 1 }
    
    >for (i = 2; i < 30; i++) { a[i] = a[i - 2] + a[i - 1]; }
    
    >for (i = 0; i < 10; i++) { print a[i]; }
    1
    1
    2
    3
    5
    8
    13
    21
    34
    55

(2) HL-8aの簡単な説明

  • 基本的なことは、(1)の最初にある程度書いたので、この節では省略します。
  • 細かいことを書きます。
    • 文字列リテラルでは、エスケープシーケンスを処理していません。だから改行(\n)などを書いてもうまくいきません。
    • 配列では、宣言されるたびにmalloc()でメモリを確保しています。そして使い終わってもmalloc()したものをfree()しません。
    • だからどんどんメモリリークします。これをどうするか考えたのですが、まあHLシリーズとしては「HL-9aのデモが動けばそれでいい」くらいの言語なので、ひとまずリークしたままにすることにしました。

(3) HL-8aにおける配列アクセスの実現方法

  • 何も考えずに添え字演算子を実装するとこんな感じになると思います。
    } else if (phrCmp(71, "[!!**0]", epc)) {
        e1 = i; 
        i = tmpAlloc();
        e0 = expr(0);
        putIc(OpAryGet, &var[e1], &var[e0], &var[i], 0);
        epc = ppc1;
  • 配列から値を読むだけなら、これで何の問題もなく十分に機能します。
  • しかし実際には、 a[i] = 3; みたいに配列への代入をすることがあり得ます。そうすると、上記の方法では、tmpAlloc()された変数の値が更新されるだけで、a[i]の値を変えることができません。
  • ということで、添え字演算子の直後に代入演算子が来た時に限って、特別な処理をすることにしました。
  • なお、これは上記のphrCmp()よりも先にやらないと、先に上記のほうが一致してしまって処理を奪われてしまうので、先に記述します。
    } 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);
  • こうすることで、a[i] = 3;で配列の値が更新されるようになります。

次回に続く

  • 次回: a21_txt01_9

こめんと欄


コメントお名前NameLink

トップ   編集 凍結 差分 バックアップ 添付 複製 名前変更 リロード   新規 一覧 単語検索 最終更新   ヘルプ   最終更新のRSS
Last-modified: 2021-03-18 (木) 16:54:01 (26d)