GAME80コンパイラ解説 (2003/08/05)

GAME80コンパイラの作者の中島聡さんにGAME80 コンパイラのソースを掲載する許可を頂きました。 プログラム言語の仕組みに興味がある方にとって非常に参考になると思います。

GAME80コンパイラは、約5.5キロバイト強と非常にコンパクトなソースで記述されています。 コンパイラがこのようなサイズで作成できる理由は、GAME IIIという言語が単純な文法でありながら密度の高い記述ができることにあります。コンパイラがターゲットとする言語自身で書かれていることもGAME80コンパイラの特徴です。自分で自分自身をコンパイルできることは、言語の改善や拡張が容易であり、GAME80コンパイラ以後に多くのマシン用のGAMEコンパイラが開発された理由にもなっています。GAME IIIの文法は GAME86 または VTL系言語の歴史 を参考にして下さい。

このコンパイラはGAME言語のプログラムソースからインテルの8080という8ビットのCPUをターゲットとしたコードを生成します。インテルの8080の機械語がコンパイラのソースに直接埋め込まれていますが、 8080の命令セットは、例えば半導体コレクション展示会場(MCS-80)を参考にして下さい。

80386以降のCPUでLinux上で動作する32ビット版のコンパイラはrvtl コンパイラを参照してください。(2006/5/3 追加)

以下のリストは昔に記事を読んで打ち込んだもので、実行して確認していません。ミスがあるかもしれませんが、その場合はご容赦下さい。GAME言語のソースは、慣れないと記号ばかりで読みにくいと思いますが、GOTOが「#=」、GOSUBが「!=」、RETURNが「]」、IFが「;=」であることを意識しておけば読めるようになると思います。

GAME80コンパイラソース

中島 聡，GAME80コンパイラ, ASCII, アスキー，1979(7), p28-29より引用

10**  GAME80 COMPILER **
20 "GAME PROGRAM FROM" G=?
30 "START ADRRESS" S=?
40 "WORK AREA FROM" L=?+4
50 L(-2)=G A=S
60 P=1 !=100 L(-1)=A
65 A=S D=$8D06
70 G=L(-2) P=2 !=100
80 "PROGRAM SIZE: " ?=A-S "(" ??=S "-" ??=A-1 ")" /
90 "END" #=-1
100** 1-2 PASS ROUTINE **
110 O=0
200** TOP OF LINE **
210 V=G:0)*256+G:1)
220 ;=G:0)>=$80  L(O)=$7FFF L(O+1)=$8603 A:0)=$C3 A=A+3 A(-1)=$8603 ]
225 ?(5)=V .=5 ??=A >=5 ??=G /
230 ;=P=1 L(O)=V L(O+1)=A O=O+2
240 G=G+3
250 ;=G:-1)<>" " #=900
300** TOP OF STATEMENT **
310 N=G:0)
350 ;=N="#" Q=$C3 #=1000
360 ;=N="!" Q=$CD #=1000
370 ;=N="]" #=1100
380 ;=N="/" G=G+1 Z=$8C83 #=2910
390 ;=N=""" #=2300
400 ;=N="?" #=2500
410 ;=(N>="A")*(N<="Z") #=5000
420 ;=N=";" #=5500
430 ;=N="@" #=5550
440 ;=N="." G=G+2 Z=$8B58 #=2900
450 ;=N=">" G=G+2 !=500 Z=K #=2910
460 ;=N="$" G=G+2 Z=$8B85 #=2900
470 ;=N="'" Z=$8D52 #=5010
480 ;=N=" " #=700
490 #=20000
500 K=0 ;=G:0)="$" G=G+1 #=530
510 E=G:0)-$30 ;=(E<0)+(E>9) ]
520 K=K*10+E G=G+1 #=510
530 E=G:0)-($30*(G:0)<"A"))-($37*(G:0)>"9"))
540 ;=(E<0)+(E>15) #=560
550 K=K*16+E G=G+1 #=530
560 ;=G:-1)<>"$" ]
570 #=4750
600 A:0)=$D5 A=A+1
610 ;=A:-2)=$D1 A=A-2
620 ]
650 A:0)=$EB A=A+1
660 ;=A:-2)=$EB A=A-2
670 ]
700** END OF STATEMENT **
710 ;=G:0)=0 G=G+1 #=200
730 ;=G:0)=" " G=G+1 #=710
740 #=300
900** REM **
920 ;=G:-1)>0 G=G+1 #=900
930 #=200
1000 ;=G:1)<>"=" #=1200
1010 G=G+2 !=1400
1020 #=700
1100 G=G+1 A:0)=$C9 A=A+1 #=700
1200 G=G+1 !=4000 A:0)=$7D A=A+1 G=G+1 Q=$CA
1210 A:0)=$3D A=A+1 !=1400
1220 ;=G:0)="," G=G+1 #=1210
1230 #=700
1400 ;=G:0)="-" G=G+1 !=500 K=$7FFF #=1500
1410 !=500
1500 A:0)=Q A=A+3 ;=P=1 ]
1510 J=-2 @ J=J+2 @=(L(J)>=K)
1520 ??=L(J+1) /
1530 A(-1)=L(J+1) ]
2300 A:0)=$C3 A=A+1 I=2
2400 Q=A+2 @ A:I)=G:I-1) I=I+1
2410 @=(G:I-1)=""") A(0)=A+I
2420 G=G+I A=A+I A:0)=$3E
2430 A:1)=I-2 A:2)=$32 A=A+5 A(-1)=$847A
2440 A:0)=$21 A=A+3 A(-1)=Q
2445 A:0)=$22 A=A+3 A(-1)=$847B
2450 A:0)=$CD A=A+3 A(-1)=$FA52
2460 #=700
2500 ;=G:1)<>"=" #=2600
2510 G=G+2 Z=$8C26 #=2900
2600 ;=G:1)<>"?" #=2700
2610 G=G+3 !=3000 A(0)=$42D5 A:2)=$CD A=A+5 A(-1)=$8C32
2620 A:0)=$D1 A=A+1 Z=$8C31 #=2910
2700 ;=G:1)<>"$" #=2750
2710 G=G+3 Z=$8C31 #=2900
2800 ;=G:1)<>"(" #=20000
2810 G=G+1 !=4000 A:0)=$4D A=A+1 G=G+1 Z=$8B9C
2820 A:0)=$C5 A=A+1 !=3000 A:0)=$C1 A=A+1 #=2910
2900 !=3000
2910 A:0)=$CD A=A+3 A(-1)=Z #=700
2950 !=3000 !=650 ]
2960 A:0)=$E5 A=A+1 !=3000
2970 A:0)=$E1 A=A+1 ]
2999** EXPRESSION **
3000 !=4000 A:0)=$EB A=A+1
3200 H=G:0) G=G+1
3210 ;=H="-" !=4000 H=$8A03 #=3500
3220 ;=H="*" !=4000 H=$8A0F #=3500
3230 ;=H="/" !=4000 H=$8A2C #=3500
3240 ;=H="=" !=4000 H=$C2 #=3610
3250 ;=H="<" #=3400
3260 ;=H=">" #=3450
3270 ;=H="<" #=3300
3280 G=G-1 ]
3300 !=4000 A(0)=$EB19 A=A+2 #=3200
3400 ;=G:0)=">" G=G+1 !=4000 H=$CA #=3610
3410 ;=G:0)=">" G=G+1 !=4000 H=$FA #=3600
3420 !=4000 H=$F2 #=3610
3450 ;=G:0)="=" G=G+1 !=4000 H=$FA #=3610
3460 !=4000 H=$F2 #=3600
3500 A:0)=$CD A=A+3 A(-1)=H #=3200
3600 A:0)=$EB A=A+1
3610 A:0)=$CD A=A+3 A(-1)=$8A03
3620 ;=H/16=$C A:0)=$B3 A=A+1
3630 A:0)=$11 A=A+3 A(-1)=0
3640 A:0)=H A=A+3 A(-1)=A+1
3650 A:0)=$1C A=A+1 #=3200
4000 H=G:0) G=G+1
4010 ;=(H>="0")*(H<="9")+(H="$") #=4210
4020 ;=H=""" #=4200
4030 ;=H="&" K=L(-1) #=4220
4040 ;=(H<"A")+(H>"Z") #=4500
4050 ;=(G:0)>="A")*(G:0)<="Z") G=G+1 #=4050
4060 H=(H-"A")*2+D
4070 ;=G:0)=":" #=4300
4080 ;=G:0)="(" #=4350
4090 A:0)=$2A A=A+3 A(-1)=H ]
4200 K=G:0) G=G+2 #=4220
4210 G=G-1 !=500 ;=G:-1)="$" ]
4220 A:0)=$21 A=A+3 A(-1)=K ]
4300 !=4400 A(0)=$6ED1 A(1)=$26 A=A+4 #=4550
4350 !=4400 A(0)=$D119 A(1)=$237E
4360 A(2)=$6F66 A=A+6 #=4550
4400 X=H !=600 G=G+1 !=3000
4410 A:0)=$2A A=A+3 A(-1)=X A:0)=$19 A=A+1 ]
4500 ;=H<>"(" #=4600
4510 !=600 !=2950 A:0)=$D1 A=A+1
4550 ;=G:0)<>")" #=20000
4560 G=G+1 ]
4600 ;=H<>"'" #=4700
4610 A(0)=$C5D5 A=A+2 !=4000
4620 !=650 A:0)=$CD A=A+3 A(-1)=$889E
4630 !=650 A(0)=$D1C1 A=A+2 ]
4700 ;=H<>"%" #=4800
4710 !=4000
4720 A:0)=$2A A=A+3 A(-1)=$8D4E ]
4750 A:0)=$CD A=A+3 A(-1)=$8C96
4760 A:0)=$6F A=A+3 A(-1)=$26
4780 ]
4800 ;=H="-" !=4900 H=$8A5B #=4920
4810 ;=H="+" !=4900 H=$8872 #=4920
4820 ;=H="#" !=4900 H=$8881 #=4920
4830 ;=H="?" !=600 H=$8904 #=4920
4890 #=20000
4900 !=600
4910 !=4000 !=650 ]
4920 A:0)=$CD A=A+3 A(-1)=H
4930 A(0)=$D1EB A=A+2
4940 ]
5000 Z=2*(G:0)-"A")+D
5005 ;=(G:1)>="A")*(G:1)<="Z") G=G+1 #=5005
5010 ;=G:1)="=" #=5300
5020 ;=G:1)=":" #=5150
5030 ;=G:1)="(" #=5100
5090 #=20000
5100 !=5200 A:0)=$19 A=A+1 #=5310
5150 !=5200 !=2960 A:0)=$73 A=A+1 #=5600
5200 G=G+2 !=3000 ;=G:0)<>")" #=20000
5210 A:0)=$2A A=A+3 A(-1)=Z
5220 A:0)=$19 A=A+1 G=G+2 ]
5300 G=G+2 !=2950 A:0)=$22 A=A+3 A(-1)=Z #=5600
5310 !=2960
5320 A:0)=$73 A:1)=$23 A:2)=$72 A=A+3
5330 #=5600
5500 ;=G:1)<>"=" #=20000
5510 G=G+2 !=3000
5520 A=A-1 ;=(A:0)=$1C)*(A(-1)=A+1) #=5800
5530 A=A+3 A(-1)=$B27B
5540 Q=$CA K=V+1 !=1500 #=700
5550 G=G+1 ;=G:0)="=" #=5700
5560 A:0)=$11 A=A+3 A(-1)=0
5570 #=5620
5600 ;=G:0)<>"," #=700
5610 G=G+1 !=3000
5620 A:0)=$CD A=A+3 A(-1)=A A:0)-$D5 A=A+1
5630 #=700
5650 G=G+1 ;=G:0)="=" #=5700
5700 Z=G:1) G=G+1 !=3000
5710 !=650
5720 ;=(Z>="A")*(Z<="Z") A:0)=$22 A=A+3 A(-1)=2*(Z-"A")+D
5730 A(0)=$D5D1 A:2)=$CD
5740 A=A+5 A(-1)=$8A03 A:0)=$D1 A=A+1
5760 A:0)=$E1 A:1)=$FA A(1)=A+6
5770 A:4)=$E5 A:5)=$E9
5780 A=A+6 #=700
5800 A=A-6 Q=A:3) K=V+1 !=1500 #=700
20000 "ERROR" #=-1

解説

コンパイラはある言語から別の言語へ翻訳するプログラムです。GAME80コンパイラは、GAME言語のプログラムの命令文を１つずつインテル8080のマシン語のパターンに置き換えていきます。

GAME80コンパイラのソースを解読するポイントは、コンパイルするソースを G:0) で1文字づつ参照していること、生成するマシン語は A:0) で1バイトを、A(0) で2バイトを書き込んでいるところです。ソースの読み込みとコード生成に使われる変数Aも変数Gも配列というよりポインタとして使用されていて、A:0)=x A=A+3 A(-1)=y のようにAの示すアドレスを変更して書いていきます。BASIC というよりむしろ C に近い書き方です。

行番号10から90までがメインルーチンです。最初にコンパイルされるGAME言語のソースが格納されている先頭アドレス(変数G)、生成するマシン語を格納する先頭アドレス(変数S)、ワークエリアの先頭アドレス(変数L)をコンソールから取得します。その後、GAME言語のソースを2回読み出してコンパイルを実行します。

GAME80コンパイラはソースを読みながらマシン語の命令を生成しますが、GOTO文(#=1000等)などの飛び先アドレスが前方(まだ読んでいない行番号)の場合には飛び先アドレスを決められないため、ソースを2回読み込みます。1回目で命令を生成しながら行番号と生成された対応するプログラムのアドレスとの対応表を作成します。2回目では1回目と同様に命令を生成しますが、飛び先アドレスは行番号との対応表から確定した値を書き込むことができます。このようにソースを2回読むことで完全なマシン語のプログラムを生成します。行番号とアドレスの表は配列変数 L の領域を使って、行番号とアドレスを交互に格納しています。

行100-490はメインルーチンから2回呼び出されて、各パスでソース中の命令をマシン語に翻訳しています。コンパイルされるGAME言語のソースは、２バイトの行番号に続いてテキストで書かれた行、行末を表す 0 を1行としてメモリに格納されています。全体の処理の流れは次のようになります。

  1. 現在の行番号を変数Vに格納
  2. 行番号が負ならばアドレステーブルの行番号を$7FFF、アドレスを$8603として登録、$8603番地へのJMP命令を生成(終了：GAME80インタプリタへ制御を戻す)
  3. 1パス目ならばアドレステーブル(L)に登録して、インデックス(変数O)を更新
  4. 読み込みソース位置(G)を行先頭に設定、コメント(行番号の直後が空白でない)ならその行を読み飛ばす(行900-930)
  5. 命令の種類に従って分岐してコード生成(行300-490)
  6. 行末でなければ 5. を繰り返す(行740)
  7. 行末なら次の行の最初に読み込み位置(G:0))を設定(行710-730)して、1. に戻る

個々の命令に関する処理へは行300-480のIF文によって分岐しています。分岐先で対応するマシン語のパターンを生成しています。

行番号 処理内容
500 数字文字列を数値に変換
700 次の命令に移る。行末ならば行200へ
900 コメント行を読み飛ばす
1000 制御系
1100 リターン文
2300 文字列出力
2500 数値出力
3000 式
4000 項
5000 変数、1バイト配列、2バイト配列への代入 FOR文
5300 代入文
5500 IF文
5550 DO文
5600 FOR文
5700 UNTIL文
20000 エラー処理

入出力と四則演算は GAME80インタープリタの入出力ルーチンをサブルーチンコールして利用しています。変数の格納領域のインタープリタの領域を使用します。機能とサブルーチンのアドレスの対応は次のとおりです。

機能 アドレス
ホットスタート $8603
改行出力 $8C83
TAB出力 $8B58
1文字出力 $8B85
1文字入力 $8C96
乱数生成 $889B
16進数出力 $8C31, $8C32
減算 $8A03
乗算 $8A0F
除算 $8A2C
右詰数値出力 $889B
数値出力 $FA52:TK-80BSのROM内ルーチン
変数格納領域先頭 $8D06

行番号380-470、3210-3230付近でサブルーチンコール命令($CD)に続けて、目的とするサブルーチンアドレスを格納した変数Zの値を書き込んでサブルーチンコールを実行するコードを生成しています。

教科書的に解説すると、「コンパイラは、字句解析、構文解析、意味解析、コード生成、最適化といった部分から構成される」という理解するには遠い道のりに思えますが、GAME80コンパイラは200行弱です。 独自の言語を作成する気になってきませんか？

GAME言語が発表されてから半年ほどでコンパイラを作成した中島さんは当時高校生だったそうです。驚きです。

参考文献


Jun's Homepage

rvtl

アセンブリ言語シリーズ