このページの目次

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 :
[目次] [次]