rvtl のソースコード解説
rvtlコンパイラのソースコードの解説を書いてみました。rvtlc は簡単なコンパイラでソースコードは2000行ほどです。普通のプログラミング言語のコンパイラでは、字句解析、構文解析、意味解析、エラー処理、コード生成、最適化、リンクなどのステップを経て実行ファイルに変換します。rvtl は文法が簡単なため、rvtl コンパイラではソースを1文字ずつ読みながら、直接実行形式に変換するため非常に高速にコンパイルできます。最近のPCならば1分間に100万行のコンパイルが可能と思います。ほとんど最適化していないため実行速度は速くはありませんが、数キロバイトから数十キロバイト程度のコンパクトな実行ファイルとなります。
rvtlc.vtl は rvtl上で動作する rvtl で書かれたコンパイラです。Linuxの実行ファイルを直接出力します。したがってリンカ(ld)もアセンブラも不要です。出力された実行ファイル はそのファイル単独で動作し、libc等の共有ライブラリは不要です。
最新版のソースのダウンロードはこちらのページから。
rvtl自身でrvtlのコンパイラを記述した意味は以下のように考えることができます。
1) オリジナル言語を考える 今回は rvtl という TINY BASIC言語系の言語です。 2) その言語のインタープリタを作成 アセンブラで rvtl のインタープリタを作成しました。 3) その言語のコンパイラのソースをインタープリタでコンパイル rvtl言語でコンパイラのソースを書いてインタープリタでコンパイルすると rvtl言語コンパイラの実行形式のファイルができます。 4) コンパイルされたコンパイラでコンパイラのソースをコンパイル 実行形式のrvtlコンパイラでコンパイラのソースがコンパイルできることを 確認します。この時点からrvtlコンパイラのソースのコンパイルに rvtlインタープリタは不要になります。 5) コンパイラのソースを改良してコンパイル rvtlコンパイラだけでrvtlコンパイラの改良や言語自身の改良が可能です。
プログラム言語を作成するには、インタプリタやコンパイルを記述するためのプログラム言語が必要となります。「タマゴが先か、ニワトリが先か」という問題と同じです。「ニワトリではない鳥がニワトリのタマゴを産んだ」が答えとなります。
rvtlcの出力ELFバイナリのメモリマップ
rvtlcが出力するプログラム(実行形式のELFファイル)の実行時メモリマップです。gcc とは異なり、MS-DOS のcom形式のように固定アドレスで動作します。
: :
+---------------------------------------+ 0x08048000
.text | ELF Header領域 |
+---------------------------------------+ 0x08048080
| ランタイムライブラリ領域 |
+---------------------------------------+
| コード領域 最大350KB |
| |
+---------------------------------------+
: :
+=======================================+ 0x080A0000
.bss | ランタイムライブラリ作業領域 16KB |
+---------------------------------------+ 0x080A4000
| 変数領域 128ワード 1KB |
+---------------------------------------+
| 変数スタック 1024ワード 4KB |
+---------------------------------------+ &
| ヒープ領域 256KB 実行時に拡張可能 |
: :
| |
+---------------------------------------+ *
: :
| スタック領域 |
+---------------------------------------+
変数の割付
rvtlは変数として A-Z、a-z の52種類のみ使用できます。rvtlc.vtl では A-Z、z をグローバル変数として使い、a-y を局所変数として使っています。
グローバル変数
rvtlコンパイラの全体を通して使うグローバル変数の使用方法です。
| A | 未使用 |
| B | BSS .bss 先頭アドレス |
| C | 入力ソース文字配列、行長はSに保持 |
| D | デバッグレベル |
| E | Lib内の.text領域書き込み用ワーク |
| F | ライブラリ読み込みエリア |
| G | ライブラリサイズ |
| H | ELFフォーマットワーク(配列) |
| I | セクションヘッダテーブルの設定で使用(局所変数で可) |
| J | ランタイムライブラリのジャンプテーブルオフセット |
| K | ラベル:アドレステーブル最終登録位置+1=登録数 を保持 |
| L | ラベル:アドレステーブル |
| M | コード領域先頭 |
| N | Nは行先頭ポインタを最初の行に設定 |
| O | Obj[] コード格納配列 |
| P | Objのインデックス(byte) |
| Q | PASS カウンタ |
| R | PASS毎のコードサイズを保持 |
| S | Cからの行長 |
| T | Control Table (配列) |
| U | Control Table Pointer |
| V | 行番号:アドレステーブル |
| W | 行番号:アドレステーブル最終登録位置+1=登録数 を保持 |
| X | 出力ファイル名 |
| Y | ソース格納用領域 |
| Z | コンパイラ先頭行番号を保存 |
| z | 確保済みのメモリ上限＋1 |
グローバル変数(配列H)
グローバル変数の数が足らないため配列Hをグローバル変数として使います。読みやすさのため、インデックスは数値ではなく文字定数を使っています。ちょっとメモリの無駄になりますが、識別しやすくなります。
| H['A']=$08048080 | e_entry |
| H['B']=$08048000 | address .text |
| H['C']=P | コード生成先頭オフセット |
| H['D']=q-Obj-P | .data文字列 |
| H['E']=q-Obj-P | .bss文字列 |
| H['F'] | ソースファイルディスクリプタ |
| H['G'] | ソース読み込み用ワーク |
| H['H']=q-Obj-P | .shstrtab文字列 |
| H['I'] | 開始時間記録(秒) |
| H['J'] | 開始時間記録(マイクロ秒) |
| H['K']=$080A0000 | .data 領域先頭アドレス |
| H['L']=0 | .data 領域のサイズ(byte) |
| H['M']=0 | .data オフセット |
| H['N']=H['K']+H['L'] | .bss 領域先頭アドレス |
| H['O']=256*1024 | .bss 領域のサイズ(byte) |
| H['P']=H['A']-H['B'] | sect_offset=e_entry-p_paddr |
| H['Q']=P | .data 終わり |
| H['R'] | |
| H['S']=P | .shstrtab |
| H['T']=q-Obj-P | .text文字列 |
| H['U']=$4000 | .bss領域中の変数領域オフセット |
| H['V']=H['N']+H['U'] | .bss領域中の変数領域先頭アドレス |
| H['W']=H['V']+$400 | .bss領域中の変数スタック先頭アドレス |
| H['X']=H['W']+$1000 | ヒープ領域先頭アドレス |
| H['Y']=P-H['S'] | .shstrtabセクションサイズ |
| H['Z']=P-H['P'] | .textセクションサイズ |
配列用のメモリ確保とグローバル変数の初期設定
rvtlcの初期化部分です。変数 z を空きメモリ領域の先頭に設定して、配列の領域を確保する場合は、「X=z z=z+256」のように z を更新します。これで「X(256)」に相当する動作をします。
10000 :------------------------------------------------------------ 10010 : rvtlc.vtl - rvtl Compiler 10020 : 2006/03/20- Jun Mizutani 10030 : 2006/05/02,05/16 10040 : コンパイルするrvtlソースをハイフンの後に指定 10050 : rvtl rvtlc.vtl - to_be_compiled.vtl 10060 : #=1 10070 : PASS1でコード生成とラベルテーブル作成 10080 : PASS2でラベルテーブルを参照してコード生成、バイナリ出力 10090 :------------------------------------------------------------ 10100 Z=9999999 : #-100 : コンパイラ先頭行番号を保存 10110 D=0 : デバッグレベル 10120 z=& : ヒープ先頭 10130 X=z z=z+256 X*="bin.elf" : 出力ファイル名(後で変更) 10140 M== : コード領域先頭 10150 *=*+(512*1024) 10160 J=35 : ジャンプテーブル先頭インデックス 10170 : 10180 Obj=z z=z+(256*1024) : 256KB までのバイナリファイル 10190 H=z z=z+512 : for ELF Header 10200 T=z z=z+300 : control table (for,do) 10210 U=0 : control table pointer 10220 V=z z=z+64000 : 8000行分の行番号:アドレステーブル 10230 W=0 : 行番号テーブル最終位置+1=登録数 10240 L=z z=z+16000 : 1000のラベル:行番号テーブル 10250 K=0 : ラベル:行番号テーブル最終位置+1=登録数 10260 Q=1 : PASSカウンタ 10270 F=z z=z+8096 : ライブラリ読み込み領域 10280 R=z z=z+8 : パス間のコードサイズ確認 10290 !=^TimerStart 10300 !=^InitSource : ソースコード読み込み 10310 :------------------- 10320 H['B']=$08048000 : コード領域先頭アドレス 10330 H['A']=$08048080 : e_entry 10340 H['K']=$080A0000 : .data 領域先頭アドレス 10350 H['L']=0 : .data 領域のサイズ(byte) 10360 H['M']=0 : .data オフセット 10370 H['N']=H['K']+H['L'] : .bss 領域先頭アドレス 10380 H['O']=256*1024 : ヒープ領域のサイズ(byte) 10390 H['U']=$4000 : .bss領域中の変数領域オフセット 10400 H['V']=H['N']+H['U'] : .bss領域中の変数領域先頭アドレス 10410 H['W']=H['V']+$400 : .bss領域中の変数スタック先頭アドレス 10420 H['X']=H['W']+$1000 : ヒープ領域先頭アドレス 10430 !=^LibRead : 10440 !=^SetUpLib 10450 E=Obj+P 10460 H['C']=P : コード生成先頭オフセット 10470 H['P']=H['A']-H['B'] : sect_offset=e_entry-p_paddr 10480 :
行番号10110の変数 D の値を大きくすると構文解析の経過やコンパイルの結果の詳細を表示することができます。値が大きくなると表示内容は追加されていきます。
| D | 表示内容 |
|---|---|
| 0 | 表示なし |
| 1 | 行番号テーブルとラベルテーブルを表示 |
| 2 | 構文解析の経過を表示 |
| 3 | ソース中の数値を表示 |
| 4 | ランタイムライブラリの呼び出し番号を表示 |
| 5 | アドレスと出力する機械語を表示 |
時間計測
コンパイル時間を計測する部分。コンパイル前に時刻を取得し、コンパイル後の時刻との差を求めます。時刻はUNIX時間とマイクロ秒で返るため、それぞれ差を求めています。
30370 :---------------------------------- 30380 : 時間計測開始 30390 :---------------------------------- 30400 ^TimerStart 30410 H['I']=_ H['J']=% 30420 ] 30430 : 30440 :---------------------------------- 30450 : 時間計測終了、経過時間表示 30460 :---------------------------------- 30470 ^TimerStop 30480 t=H['I'] u=H['J'] x=_ y=% 30490 d=x-t f=y-u 30500 ;=(f<0) d=d-1 f=f+1000000 30510 " time:" ?=d "." ?[6]=f "sec" / 30520 ] 30530 :
ソースコードの読み込み
コマンドライン引数で渡されたソースファイルをオープンして、一文字づつ読み込み、以下の形式で行として格納します。行番号は読込み時点で数値に変換されます。rvtl インタプリタがスクリプトをメモリ中に格納する形式と同じです。
4byte 4byte 1byte 0-3byte
+-------------------+--------+--------------------+-----+-----------+
+---| 次行へのオフセット| 行番号 | 行の内容 | 0 | アライン用|
| +-------------------+--------+--------------------+-----+-----------+
+-->| 次行へのオフセット| 行番号 | 行の内容 | 0 | アライン用|
+-------------------+--------+--------------------+-----+-----------+
: : : : : :
+-------------------+--------+--------------------+-----+-----------+
| -1 | | | | |
+-------------------+--------+--------------------+-----+-----------+
30540 :------------------------------------------------- 30550 : ソース読み込み 30560 :------------------------------------------------- 30570 ^InitSource 30580 : z=& 30590 Y=z z=z+(128*1024) : ソース保存領域 30600 H['G']=z z=z+16 : work 30610 !=^LoadSource 30620 !=^MkFileName 30630 : !=^ListSource 30640 M=Y : 30650 ] 30660 : 30670 :------------------------------------------------- 30680 : 出力ファイル名をXに設定 30690 :------------------------------------------------- 30700 ^MkFileName 30710 +bzinf 30720 b=z z=z+256 30730 [=0 b*=\0 30740 n=% 30750 i=n 30760 @ 30770 i=i-1 30780 @=((b(i)='.')|(i=0)) 30790 ;=i=0 f=b+n f*=".elf" X*=b ] 30800 f=b+i f*=".elf" X*=b 30810 -fnizb 30820 ] 30830 : 30840 :------------------------------------------------- 30850 : ソースファイルを読み込み 30860 :------------------------------------------------- 30870 ^LoadSource 30880 +ynml 30890 !=^SourceOpen : ソースファイルをオープン 30900 y=Y 30910 l=0 30920 @ 30930 : 1行読み込み 30940 !=^SourceRead 30950 ;=c=' ' !=^SkipSpace 30960 ;=(c<'0')|(c>'9') !=^SkipLine #=^ls0 30970 !=^GetLineNo : 行番号 30980 y[1]=n 30990 m=8 31000 @ 31010 y(m)=c : ソースをLFまで保存 31020 m=m+1 31030 !=^SourceRead 31040 ;=c=$0D !=^SourceRead 31050 @=((c=$0A)|(c=0)) 31060 y(m)=0 m=m+1 31070 m=(m+3)/4*4 : 4でアライン 31080 y[0]=m : 次行までのオフセットを設定 31090 y=y+m 31100 l=l+1 31110 ^ls0 31120 @=(c=0) 31130 y[0]=-1 31140 !=^SourceClose : ソースファイルをクローズ 31150 / "read " ?=l " lines" / 31160 -lmny 31170 ] 31180 : 31190 :------------------------------------------------- 31200 : 1行読み飛ばし 31210 ^SkipLine 31220 @ 31230 !=^SourceRead 31240 @=((c=$0A)|(c=0)) 31250 ] 31260 : 31270 :------------------------------------------------- 31280 : ソース表示 31290 :------------------------------------------------- 31300 ^ListSource 31310 y=Y 31320 n=0 31330 @ 31340 ?(6)=y[1] 31350 $*=y+8 / 31360 y=y+y[0] 31370 @=(y[0]=-1) 31380 ] 31390 : 31400 :------------------------------------------------- 31410 : 空白除去 31420 :------------------------------------------------- 31430 ^SkipSpace 31440 @ 31450 !=^SourceRead 31460 ;=(c>='0')&(c<='9') n=n*10+(c-'0') 31470 @=((c<>' ')) 31480 ] 31490 : 31500 :------------------------------------------------- 31510 : 行番号取得 cに1文字目 31520 :------------------------------------------------- 31530 ^GetLineNo 31540 n=c-'0' 31550 @ 31560 !=^SourceRead 31570 ;=(c>='0')&(c<='9') n=n*10+(c-'0') 31580 @=((c<'0')|(c>'9')) 31590 ] 31600 :
rvtlの基本機能ではファイルをすべてメモリに読み込むことはできますが、「ファイルをオープンして、ファイルから1文字ずつ読み込み、ファイルをクローズする」機能はありません。ソースファイルから1文字ずつ読み込むため、組み込みコマンド|zz を使ってカーネルのシステムコールで、ファイルオープン、ファイルリード、ファイルクローズを実現しています。
31610 :------------------------------------------------- 31620 : ソースファイルをオープン 31630 :------------------------------------------------- 31640 ^SourceOpen 31650 +r 31660 b=\0 31670 !=^fropen 31680 H['F']=r 31690 -r 31700 ] 31710 : 31720 :------------------------------------------------- 31730 : ソースファイルをクローズ 31740 :------------------------------------------------- 31750 ^SourceClose 31760 b=H['F'] 31770 !=^fclose 31780 ] 31790 : 31800 :------------------------------------------------- 31810 : ソースから1文字読み込み 31820 :------------------------------------------------- 31830 ^SourceRead 31840 a=3 : read 31850 b=H['F'] : fd 31860 c=H['G'] : buffer 31870 d=1 : size 31880 |zz 31890 c=c(0) 31900 ;=(|<=0) c=0 31910 ] 31920 : 31930 :------------------------------------------------- 31940 : ファイルをオープン 31950 : enter b : 第１引数 filename 31960 : return r : fd, if error then eax will be negative. 31970 :------------------------------------------------- 31980 ^fropen 31990 c=0 : 第２引数 flag=O_RDONLY 32000 #=^fopen 32010 ^fwopen 32020 c=577 : O_CREAT|O_WRONLY|O_TRUNC 32030 ^fopen 32040 a=5 : システムコール番号 SYS_open 32050 d=420 : 第３引数 mode=0644 32060 |zz 32070 r=| 32080 ] 32090 :------------------------------------------------- 32100 : ファイルをクローズ 32110 : enter b : 第１引数 ファイルディスクリプタ 32120 :------------------------------------------------- 32130 ^fclose 32140 a=6 : システムコール番号 SYS_close 32150 |zz 32160 r=| 32170 ] 32180 :
[目次] [次]