電子ブロック工房 IC・トランジスタで出来たコンピューターを設計・製作するためのブログ

ケンケンさんのPIC32MX用SDカードブートローダー（＋カラーNTSC出力）用に、整数型BASICコンパイラーを作成することにした。仕様は、以前にMZ-80用に作成したKM-BASICと同じに。必要最小限の仕様。SDカードにBASICのソースコードをテキストファイルで置いておけば、それをコンパイルして即実行するような物を考えている。

９割以上出来上がっているのだが、最後に、RAM上のプログラムの実行権限を得るところで手間取っていて、公開は次の週末以降になる見込み。ここでは、基本的な構造に関する覚え書きなど、記しておく。

演算アルゴリズム
MZ-80用のKM-BASICでは、演算子に優先順位を付けなかった。これを実装すると、コンパイラー自身のコードサイズが大きくなってしまうので、メモリー容量の少ないモデルでは割愛した。今回は、広大（と言っていい）なフラッシュメモリー領域があるので、少々複雑な事をする実装が可能なので、演算の優先順位付きでの実行は、やはり欲しいところ。私が大学生の頃、NECのPC-9801用に整数(16 bits)型BASICコンパイラーを作成したことがあって、その時も実装したのだが、どうやったかどうも思い出せない。もう一度考え直して出来たのが、次のアルゴリズム。ここにメモしておけば、将来同じ事をするときに、無駄に時間を費やすことがないだろう。


演算順位決定ルーチンは、一つの関数（再帰呼び出しされる）で実装されている。実際のコードは、以下の通り。

char* get_value_sub(int pr){
	char* err;
	enum operator op;
	int prevpos;
	// Get a value in $v0.
	err=get_simple_value();
	if (err) return err;
	while(1){
		// Get the operator in op. If not valid operator, simply return without error.
		prevpos=g_srcpos;
		err=get_operator();
		if (err) return 0;
		op=g_last_op;
		// Compair current and previous operators.
		// If the previous operator has higher priolity, return.
		if (pr>=priority(op)) {
			g_srcpos=prevpos;
			return 0;
		}
		// Store $v0 in stack
		g_sdepth+=4;
		if (g_maxsdepth<g_sdepth) g_maxsdepth=g_sdepth;
		check_obj_space(1);
		g_object[g_objpos++]=0xAFA20000|g_sdepth; // sw v0,xx(sp)
		// Get next value.
		err=get_value_sub(priority(op));
		if (err) return err;
		// Get value from stack to $v1.
		check_obj_space(1);
		g_object[g_objpos++]=0x8FA30000|g_sdepth; // lw v1,xx(sp)
		g_sdepth-=4;
		// Calculation. Result will be in $v0.
		err=calculation(op);
		if (err) return err;
	}
}

この基本部分が出来てしまえば、あとは演算子の実装を、しらみつぶしに行なっていくだけ。

文字列の処理
文字列についても、MZ-80用の物よりも少し複雑な処理が行えるようにした。MZ-80用の物では、文字列の長さを８０文字までに限定し、かつ、文字列の連結はLETステートメントのみで行える仕様であった。これを、いつでもどこでも文字列の連結が行え、長さの上限が無いようにした。結果として、一時領域の動的な確保とガベージコレクションが必要になった。

一時領域の確保をフレキシブルに行なうため、malloc()を使わず、一から実装することに。色々と試行錯誤した結果、最終的には、いつガベージコレクションを行なうかのタイミングだけで制御するコードになった。

一時的に作成された文字列は、それが変数に代入されるかPRINT文などで使用されるか、いずれかが実行されるまでは有効に保持しておかなければならない。逆に、これらが行なわれた後は、すべて破棄することが出来る。ただし、余り頻繁にガベージコレクションを行なっていては、実行速度の低下を招いてしまう。

そこで、ソースコードでの一行に一度、一時領域の確保をする直前に、それ以前の一時領域をすべて破棄する仕様にした。一時領域確保の際、その行での初めての実行かどうかの判断は、$s6レジスターの値をチェックすることで行なう。$s6レジスターの値が正の場合、初めての実行と見なし、すべての一時領域を破棄した後に、$s6レジスターの値を負にする($s6=0-$s6)。$s6レジスターは、行番号やジャンプ用ラベルの管理にも使用されているので、それについては下記を参照。

FOR～NEXT文の実装
FOR～NEXTには、スタックを用いている。FOR文のところで、現在の実行アドレスをスタックに待避し、NEXTのところでスタックに待避されたアドレスにジャンプするような実装。この実装のため、「～」の部分は、最低一度は実行される仕様である。また、下記で述べるGOSUBにもスタックが用いられているので、FOR～NEXTループ中ではRETURN命令は使用できない。

GOTO/GOSUB/RETURNの実装
GOTOは、純粋にMIPSのジャンプ命令に置換される。ただし、ジャンプ先としては行番号以外にラベルを指定することが出来る。GOSUBの場合は、現在の実行アドレスをスタックに待避した後にジャンプ、RETURNは、待避された実行アドレスへのジャンプである。ON-GOTOは実装していないが、その代りに、"GOTO 100+A"の様に、ジャンプ先をダイナミックに指定することが出来る。

GOTO/GOSUBのジャンプ先が静的な場合、コンパイル後のリンクの際に、ジャンプ先のアドレス部分が書き込まれる。それぞれの行番号とラベルが、どのアドレスに相当するかを調べる方法として、オブジェクト中にMIPSの$s6レジスターに値を代入する命令を挿入するようにした。このコードを走査することで、ジャンプ先を調べることが出来る。"GOTO 100+A"の様に、ジャンプ先をダイナミックに指定している場合も、同じメカニズムを利用している。また、オブジェクトの実行中に、「ゼロで割る」　「一時領域が足りない」などの例外が起きた場合に、$s6レジスターの値を調べれば、どの行で例外が起きたかを調べることが出来る。

追記：2014/8/03
以下、とりあえず動くようにしたバージョンです。hexファイルを、ケンケンさんのSDカードブートローダーから取り込んで下さい。BASICのソースコードを、hexファイルと同じファイル名で拡張子をtxtにして、保存して下さい。文法は、とりあえずこちらを参照。追加の命令もありますので、改めて公表します。
バージョン0.8.6がここからダウンロードできます。まだ、転載不可のライセンスとします。