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

  • (by K, 2021.02.28)

(1) HL-2

  • TL-1では変数名も数値定数も1文字しか受け付けないという仕様でした。それはあんまりだと思うので、まずはその制限を解消しようと思います。
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef unsigned char *String;	// こう書くと String は unsigned char * の代用になる.

void loadText(int argc, const char **argv, String t, int siz) → HL-1と同じなので省略

///////////////////////////////////////////////////////////////////////////////

#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) // トークン番号を得るための関数.
{
    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になる).
    }
    return i;
}

///////////////////////////////////////////////////////////////////////////////

int isAlphabetOrNumber(unsigned char c)		// 変数名に使用できる文字かどうか.
{
    if ('0' <= c && c <= '9') return 1;
    if ('a' <= c && c <= 'z') return 1;
    if ('A' <= c && c <= 'Z') return 1;
    if (c == '_') return 1;
    return 0;
}

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 {
            printf("syntax error : %.10s\n", &s[i]);
            exit(1);
        }
        tc[j] = getTc(&s[i], len);
        i += len;
        j++;
    }
}

int tc[10000];	// トークンコード.

///////////////////////////////////////////////////////////////////////////////

int main(int argc, const char **argv)
{
    int pc, pc1;
    unsigned char txt[10000]; // ソースコード用のバッファ.
    loadText(argc, argv, txt, 10000);
    pc1 = lexer(txt, tc);
    tc[pc1] = tc[pc1 + 1] = tc[pc1 + 2] = tc[pc1 + 3] = getTc(".", 1);	// エラー表示用のために末尾にピリオドを登録しておく.
    int semi = getTc(";", 1);
    for (pc = 0; pc < pc1; pc++) { // プログラム実行開始.
        if (tc[pc + 1] == getTc("=", 1) && tc[pc + 3] == semi) { // 単純代入.
            var[tc[pc]] = var[tc[pc + 2]];
        } else if (tc[pc + 1] == getTc("=", 1) && tc[pc + 3] == getTc("+", 1) && tc[pc + 5] == semi) {  // 加算.
            var[tc[pc]] = var[tc[pc + 2]] + var[tc[pc + 4]];
        } else if (tc[pc + 1] == getTc("=", 1) && tc[pc + 3] == getTc("-", 1) && tc[pc + 5] == semi) {  // 減算.
            var[tc[pc]] = var[tc[pc + 2]] - var[tc[pc + 4]];
        } else if (tc[pc] == getTc("print", 5) && tc[pc + 2] == semi) { // print.
            printf("%d\n", var[tc[pc + 1]]);
        } else
            goto err;
        while (tc[pc] != semi)
            pc++;
    }
    exit(0);
err:
    printf("syntax error : %s %s %s %s\n", ts[tc[pc]], ts[tc[pc + 1]], ts[tc[pc + 2]], ts[tc[pc + 3]]);
    exit(1);
}
  • プログラムは128行になりました。このプログラムによって、たとえば以下のようなプログラムが実行可能です。
    abc = 123;
    def = 456;
    ans = abc + def;
    ans = ans - 321;
    print ans;
  • この例では記号と英数字の間にスペースを入れていますが、それは省略可能です。またスペースは1つではなく複数入れても平気です。

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

  • 関数:
    • void loadText(int argc, const char **argv, String t, int siz)
      • コマンドライン引数で指定されたソースファイルをtに読み込む。sizはtの最大サイズを表す(これを超える長さのファイルは途中で打ち切られる)。
    • int getTc(String s, int len)
      • トークン(単語)をsに渡すと、それに対応するトークンコード(整数)を返す。
    • int isAlphabetOrNumber(unsigned char c)
      • 引数で渡された文字コードが、英数字であれば1を返す。それ以外なら0を返す。
      • アンダースコアもHL-2の中ではアルファベットということにしておく。そうすることで、変数の一文字目に使えるようになる。
      • この関数は以下のlexer()の下請け。
    • int lexer(String s, int tc[])
      • sにプログラムのソースコードを渡す。すると、tc[]にトークンコード(単語番号)に変換させられた数列が入って返される。
      • より詳しい動作は、下記にあるようにa21_txt01_2aを参照のこと。
    • 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[]
      • プログラムをトークンコード列に変換したものがここに入る。

  • 変数名や定数が一文字で、余計なスペースが一切なかったHL-1では、とても簡単にプログラムの解釈ができていました。
  • しかしHL-2以降では、変数名や定数の長さは自由になり、またトークンとトークンの間にはスペースやタブが入るかもしれず、プログラムの解釈が複雑になります。
  • そこでまず、プログラムをトークンの集まりだと解釈して、トークン番号(トークンコード)の列に変換することにしました。こうすることで、HL-1での文字コードがトークンコードに置き換わるだけで、それ以外の仕組みをすべてそのままにすることができます。
  • 以下の比較を見れば、文字コードでの処理方法と、トークンコードでの処理方法がよく似ているというか、ほぼ同じだということがわかってもらえると思います。
    HL-1での加算の処理:var[txt[pc]] = var[txt[pc + 2]] + var[txt[pc + 4]];
    HL-2での加算の処理:var[tc [pc]] = var[tc [pc + 2]] + var[tc [pc + 4]];
  • すごくよく似ていることが伝わるでしょうか・・・。
  • とはいえ、文字コードとは異なり、どのトークン文字列が1番なのかは決まっていません(文字コードなら規格で決まっているのに)。ということで、HL-2では、ソースコードでの出現順に、0番, 1番, 2番,... と割り当てています。
  • ここまでの仕組みが分かれば、以下の説明はかなりわかりやすくなるはずです。

(3) getTc()の説明

  • 今回はgetTc()とlexer()が主要な変更点なので、その二つを詳しく説明します。
  • まずはgetTc()から行きます。以下は上記プログラムの一部を再掲したものです。
#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) // トークン番号を得るための関数.
{
    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になる).
    }
    return i;
}
  • まずgetTc()は、トークン文字列が始まる位置と、その文字数を受け取って、そこからトークンコード(単語番号)を返すという仕様になっています。また、ついでに、新規のトークンだった場合は、対応する変数領域に初期値を設定する役目もあります。
  • なぜ単純にトークン文字列を渡す仕様ではなく、文字数を指定する仕様にしたのかというと、ソースコードからトークンに切り分ける時に、ソースコードから切り出した文字列を毎回生成するのが面倒だなと思ったためです。文字数を指定する方法なら、ソースコード内の文字列をそのまま使うことができます。
  • getTc()では最初のループで、指定されたトークンが既に登録済ではないかどうかを調べます。もし登録済みのトークンであれば、規定の番号を返さなければいけません。見つかった場合は、 i < tcs ということになるので、その次のifは何もせずに通過して、そのままiを返すことになります。
  • 見つからなかった場合、トークンを新規登録することになります。受け取った文字列をきちんと切り出して、tcBuf[]へコピーしておきます。そしてts[]で参照できるようにもしておきます。こうすることで、トークンコードからトークン文字列を得ることが簡単にできるようになります。また次回項の検索のためにtl[]にlenも記憶させておきます。
  • この辺の処理が不慣れでよくわからない場合、a21_txt01_2bを見るとすっきりするかもしれません。
  • 最後に、変数に初期値を設定します。多くの場合、ここのstrtol()はゼロを返すだけですが、もしトークン文字列が「123」のようなものだった場合、それは123という数値となってvar[i]が初期化されることになります。

(4) lexer()の説明

  • 次はlexer()です。・・・一般にソースプログラムをトークンの列に切り分けるプログラムは、レキサーと呼ばれるそうで、この関数名はそれに由来しています。
  • 説明を分かりやすくするために、プログラムを再掲します。
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 {
            printf("syntax error : %.10s\n", &s[i]);
            exit(1);
        }
        tc[j] = getTc(&s[i], len);
        i += len;
        j++;
    }
}
  • lexer()では、ソースコードを読みながら、以下の6通りの処理を繰り返します。
    • [1]スペース、タブ、改行のコードを見つけた場合:
      • 特に何も出力することなく、読み飛ばします。
    • [2]ソースコードの終端に達した場合:
      • ここで変換処理を打ち切って、変換したトークン列の長さを返して終了します。
    • [3]かっこやセミコロン、コンマを見つけた場合:
      • これらの記号は1文字で1トークンであるとして、len=1にして、getTc()でトークンコードに変換して、それをtc[j]に格納します。
    • [4]英数字を見つけた場合:
      • これはおそらく変数名か定数です。ということで、英数字の並びが終わるまでlenを増やしたあとで、getTc()します。
    • [5]=や+などの記号を見つけた場合:
      • この種類の記号が続く限りlenを増やします。それでgetTc()します。
      • この方法だと、a=3;やa++;やa+=b;などはうまく切り分けられます。
      • しかし「a=-3;」と書いた場合、C言語なら「a」「=」「-」「3」「;」と分けるでしょうが、このlexer()だと「a」「=-」「3」「;」と分けることになります。これはlexer()を簡単にしてしまった副作用です。このlexer()でこれを避けるには、「a= -3;」のように、イコールとマイナスの間にスペースを入れるしかありません。
      • でもまあ、たいていは「a = -3;」と書く人が多いと思うので、このlexer()でもそんなに不便だというわけではありません。
  • lexer()がどんな結果を返しているのか、より詳しい説明ページを追加しました。→a21_txt01_2a

(5) main()の説明

  • main()はHL-1がわかっていれば難しいところはほとんどないと思いますが、一点だけ説明が必要そうなところがあるので書いておきます。
    tc[pc1] = tc[pc1 + 1] = tc[pc1 + 2] = tc[pc1 + 3] = getTc(".", 1);	// エラー表示用のために末尾にピリオドを登録しておく.
  • ここが何をやっているのかよくわからないかもしれません。
  • これはソースコードの末尾に、ピリオドのトークンを追加しています。しかしプログラムの末尾であるpc1は増加させていないので、この増やしたピリオドがプログラムの一部として実行されることはありません。
  • ではなぜこんなものが必要なのかというと、プログラムの末尾でエラーが起きた場合のためです。エラーが起きると、
err:
    printf("syntax error : %s %s %s %s\n", ts[tc[pc]], ts[tc[pc + 1]], ts[tc[pc + 2]], ts[tc[pc + 3]]);
    exit(1);
  • が実行されるわけですが、この時に、tc[pc + 1]やtc[pc + 2]などが不定値だったりすると誤動作の恐れがあるのです。それで、あまり目立たないピリオドを代わりに置いておこうと考えたわけです。それだけです。
  • ということで全く本質的ではないですが、わからないと気になるかもしれないと思ったので、説明しておきました。

次回に続く

こめんと欄


コメントお名前NameLink

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