川合のプログラミング言語自作のためのテキスト第三版#1
(1) はじめに
- 「プログラミング言語を作ってみたい」と思ったことがある人は、プログラマの中にはけっこうたくさんいるのではないかと思います。・・・でも、実際に作ってみた人はそれほどには多くないかもしれません。それはなぜでしょうか。
- おそらくは、多くの人にとってプログラミング言語を作るのは難しいということになっているからだと思います。そう思うからこそ、チャレンジするまでもなくあきらめてしまうわけです。とてももったいないです。
- 私はプログラミング言語は(世間の人が思っているよりは)ずっと簡単に作れるものだと思っています。・・・今からここにそのためのテキストを置きます。これを読んで是非作れるようになってください。そうすれば「作りたいけど、作り方が分からない」を卒業することができます。そして今後は「じゃあどんな言語を作ろうか」をメインで考えられるようになるのです。それはとても素敵なことだと思います。
- この時点では「本当にプログラミング言語を作るのは簡単なのか?」という疑問を持つ人は少なくないと思いますが、かつてはタイニーベーシックのような言語があり、それはたった数キロバイトの機械語でした。それらの言語はもちろん言語を作りやすくするために文法規約にいろいろと制限がありましたが、つまり逆に言えば、適切な制限を導入すれば言語は簡単に作れるということなのです。
- このテキストでは、最初はインタプリタ(スクリプト言語)の作り方を説明します。そしてある程度いろいろできるようになったら、JITコンパイラや普通のコンパイラの作り方も紹介します。
- というとなんだか欲張りな構成ですが、結局プログラミング言語はインタプリタでもコンパイラでも共通の部分が多くて、だからついでに全部紹介してしまうのは効率的なのです。
- 目的別ガイド:
- とにかく言語の本質だけが知りたければ、HL-1だけ読めばいいです。49行で処理系を理解できます。
- トークンを使って変数名を可変長にするやり方を知りたければ、HL-2まで読めば十分です。
- 基本的な分岐処理を理解したければ、HL-3まで読めばいいです。
- REPLの例が見たければ、HL-4まで読めばいいです。
- 実行速度を高める工夫に興味があれば、HL-5やHL-6まで読めばいいです。HL-6では内部に簡単なVMを作ります。徐々にコンパイラっぽくなってきます。
- 演算子の優先順位を反映した式の評価をやりたければ、HL-7まで読めばいいです。
- for文やブロックif文などの実装方法に興味があれば、HL-8まで読めばいいです。
- インタプリタ編を最後まで読みたければ、HL-9まで読んでみてください(→この段階でどの程度のことができるのかについて、a21_tl9aに詳しく書きました)。
- もくじ(HL-1から順番に読んでいくとわかるように書いています)
ページ名 | 名前 | 行数 | .exeの大きさ | 説明 | 速度のめやす |
a21_txt01 | HL-1 | 49行 | 6.0KB | 初めの一歩、たった49行のシンプルすぎる言語処理系 | 計測不能 |
a21_txt01_2 | HL-2 | 128行 | 6.5KB | 変数名は1文字じゃなくてもOK、見やすいスペースやインデントもOKに | 計測不能 |
a21_txt01_3 | HL-3 | 148行 | 7.0KB | 条件分岐などをサポートしてループ処理が可能に | 1520倍 |
a21_txt01_4 | HL-4 | 186行 | 7.5KB | REPLの導入(これは楽しい!) | 1520倍 |
a21_txt01_5 | HL-5 | 215行 | 7.5KB | 少し高速化 | 260倍 |
a21_txt01_6 | HL-6 | 287行 | 8.0KB | もっと高速化(がんばった!) | 11.3倍 |
a21_txt01_6a | HL-6a | 303行 | 8.5KB | さらに高速化!(これをやるかどうかは好みが分かれるかも) | 6.5倍 |
a21_txt01_7 | HL-7 | 456行 | 9.5KB | 式の導入(なんか急にかっこよくなった!) | 6.5倍 |
a21_txt01_8 | HL-8 | 622行 | 12.0KB | forやブロックifの追加 | 6.5倍 |
a21_txt01_9 | HL-9 | | | グラフィック命令の追加 | |
a21_txt01_10 | | | | ここまでのまとめ・今後の課題 | |
a21_txt01_11 | HJ-1 | | | 最初のJITコンパイラ | |
- (註)「.exeの大きさ」はWindows向けにgcc(MinGW)でコンパイルした時の大きさです。
- しかしここで扱う言語処理系は、Windows専用というわけではなく、他のOSでも問題なく動作するようになっています。
- 純粋に言語処理系の規模の目安を示すために書いてあります。
- 「速度のめやす」は、C言語で10億回ループさせた場合と、この言語で10億回ループさせた場合の処理時間の比を書いています。数が大きいほうが遅いです。
- なお、gccに対しては「-O3」という一番強い最適化を指示しています。
- 遅すぎて10億回もまわせないときは、1億回とかにへらして、その結果を10倍して記入しています。
- おおざっぱな目安です。
(2) HL-1
- 事前の説明はこれくらいにして、とにかく言語を作ってみます。これは「HL-1」です。HLは「はりぼて言語」の略です。HL-1はC言語で書かれています。
#include <stdio.h>
#include <stdlib.h>
void loadText(int argc, const char **argv, unsigned char *t, int siz)
{
FILE *fp;
int i;
if (argc < 2) { // 引数が少ないのでエラー表示して終了.
printf("usage>%s program-file\n", argv[0]);
exit(1);
}
fp = fopen(argv[1], "rt"); // テキストモードでファイルを開く.
if (fp == 0) { // ファイルを開けなかった.
printf("fopen error : %s\n", argv[1]);
exit(1);
}
i = fread(t, 1, siz - 1, fp); // iは読み込んだバイト数.
fclose(fp);
t[i] = 0; // 終端マークを書いておく.
}
int main(int argc, const char **argv)
{
unsigned char txt[10000]; // ソースコード.
int i, pc, var[256]; // varは変数.
loadText(argc, argv, txt, 10000);
for (i = 0; i < 10; i++)
var['0' + i] = i; // テクニック#1.
for (pc = 0; txt[pc] != 0; pc++) {
if (txt[pc] == '\n' || txt[pc] == '\r' || txt[pc] == ' ' || txt[pc] == '\t' || txt[pc] == ';') // 空行など.
continue;
if (txt[pc + 1] == '=' && txt[pc + 3] == ';') { // 単純代入.
var[txt[pc]] = var[txt[pc + 2]];
} else if (txt[pc + 1] == '=' && txt[pc + 3] == '+' && txt[pc + 5] == ';') { // 加算.
var[txt[pc]] = var[txt[pc + 2]] + var[txt[pc + 4]];
} else if (txt[pc + 1] == '=' && txt[pc + 3] == '-' && txt[pc + 5] == ';') { // 減算.
var[txt[pc]] = var[txt[pc + 2]] - var[txt[pc + 4]];
} else if (txt[pc] == 'p' && txt[pc + 1] == 'r' && txt[pc + 5] == ' ' && txt[pc + 7] == ';') { // 最初の2文字しか調べてない(手抜き).
printf("%d\n", var[txt[pc + 6]]);
} else
goto err;
while (txt[pc] != ';')
pc++;
}
exit(0);
err:
printf("syntax error : %.10s\n", &txt[pc]);
exit(1);
}
(4) HL-1の簡単な説明
- 関数:
- loadText() : コマンドライン引数で指定されたソースファイルを配列変数に読み込む。
- main() : 言語処理の本体。
- 変数:
- var[] : 変数の値を記憶しておくための変数。
- txt[] : ソースコードを記憶しておくための変数。
- pc : 現在プログラムのどこを実行しているのかを記憶するための変数。
- プログラム中で「テクニック#1」と書かれた部分があります。ここがやっていることは、「3」という定数さえも「3」という名前の変数であると解釈することにして、その代わり変数「3」には初期値として3を代入しておくのです(そうでないと変数「3」を参照したときに3にならなくなってしまうため)。
- こうすることで、プログラムでは以降変数と定数を区別する処理が不要になって、HL-1は短く書けるようになります。
- C言語での文字列の扱いに不慣れな人のために、簡単な説明ページを作りました。必要な人はご利用ください。→a21_txt01_1a
- [隠れたこだわり]
- このHL-1やそれ以降のプログラムは、C言語が得意じゃない人でも分かりやすくなるように一定の配慮をしています。
- ポインタはやむをえないときは使ってもいいですが、ポインタに対する加算や減算はしせん(ポインタは配列みたいなものだと理解している場合、ポインタに対する演算があるとそこで難しく感じてしまうので)。というマイルールを自分に課しています。
- 文字列を扱うときはなるべく標準関数で扱える形式にします。
次回に続く
こめんと欄