Rubyでコンパイラを作ってみる

Rubyを使って超簡易コンパイラを作ってみました。
ソースを読み込んで、仮想スタックマシンのアセンブラを出力します。
使用したRubyのバージョンは1.9.1、Windows環境で作成しています。

ソースとサンプルsscr_003a.lzh
アセンブリ言語インタープリターinterpreter_003a.lzh
構文規則（racc定義ファイル）sscr.y
アセンブリ言語マニュアルopcode.txt
関数呼び出し・復帰手順call_func.txt

使用方法

コンパイル方法
C:¥> ruby sscr.rb sample.src sample.asm
アセンブリインタープリター実行方法
C:¥> ruby interpreter.rb  sample.asm

interpreter.rb内最初のDEBUG_STEPをtrueにするとステップ（1命令毎）動作します。

履歴
ver. 0.0.3a (2010-05-14)
ver. 0.0.3 (2010-05-09)
ver. 0.0.2 (2010-05-06)
ver. 0.0.1 (2010-05-04)

ver. 0.0.3a

関数定義を可能にした（型はintのみ）
return文追加
その為、アセンブラにBP(ベースポインタ）を追加
関連するオペコード追加

ソースとサンプルsscr_003a.lzh

文法

int add(a,b){
   int x;
   x = a + b;
   return(x);
}

print add(a+1,b+2);

構文規則

stmt     : 
         | stmt_return　（追加）

decl_int   : 'INT' list_var ';'
           | 'INT' IDENT '(' list_var ')' '{' list_stmt '}' ';'　（追加）

stmt_return: 'RETURN' ';'　　　　　（追加）
           | 'RETURN' expr ';'　　 （追加）

primary  : IDENT
         | IDENT '(' list_exp ')'　（追加）

アセンブラ命令コード

adr       アドレス
(adr)     アドレスadrのデータ
R         SP(p) or BP(bp)

pc        プログラムカウンタ
p         スタックポインタ（値が入っているトップを指す）
s[p]      pが示すスタックの値
bp        ベースポインタ（スタック上の特定の位置を指す）
※spとbpの初期値は、スタックボトム-1である


LDA   offset[R] s[p+1]=R+offset,p=p+1   

LEASP offset[R]  p=R+offset             exp) LEASP 1[SP] -> p=p+1
LEABP pffset[R] bp=R+offset

PUSH            sp[p+1]=bp,p=p+1
POP             bp=sp[p],p=p-1

CALL  adr       sp[p+1]=pc+1(次命令アドレス),p=p+1
RET             pc=sp[p],p=p-1

call/ret手順とスタックの変化

int foo(a,b){
   int c,d;
}

foo(aa,bb);

------------------------------------
main内foo呼び出し直前
bp    sp
v     v
 [n,n,n]

foo開始時
                bp       sp
                v        v
 [n,n,n,z,bb,aa,BP,ret,c,d]
    z    :戻り値格納場所
    aa,bb:arg
    BP   :foo呼出前のBP位置
    ret  :return adr
    c,d  :local var

local_var/argアクセス
    arg1(aa)    LDA  -1[BP]
    arg2(bb)    LDA  -2[BP]
    local1(c)   LDA   2[BP]
    local2(d)   LDA   3[BP]
------------------------------------
call foo 手順
main                                    v(BP0)
                                         [n,n,n]
    LEASP  1[SP] (sp=sp+1,戻値格納場所)  [n,n,n,z]
    (push  arg)  (aa,bb)                 [n,n,n,z,bb,aa]
    PUSH                                 [n,n,n,z,bb,aa,BP0]
                                                         v(BP1)
    LEABP  [SP]  (bp=sp)                 [n,n,n,z,bb,aa,BP0]
    CALL   foo   (push ret_adr)          [n,n,n,z,bb,aa,BP0,ret]
foo
    LEASP  2[SP] (sp=sp+2,local_var数)   [n,n,n,z,bb,aa,BP0,ret,c,d]
    LDA    -3[BP]                        [n,n,n,z,bb,aa,BP0,ret,c,d,BP1-3]


return foo 手順
foo                                                     v(BP1)
                                         [n,n,n,z,bb,aa,BP0,ret,c,d,BP1-3,v]
    STS          ((BP-3)=ret_value)      [n,n,n,v,bb,aa,BP0,ret,c,d,v]
    DEL                                  [n,n,n,v,bb,aa,BP0,ret,c,d]
    LEASP  1[BP] (c,d)                   [n,n,n,v,bb,aa,BP0,ret]
    RET                                  [n,n,n,v,bb,aa,BP0]
main
                                        v(BP)
    POP                                  [n,n,n,v,bb,aa]
    LEASP  -2[SP](aa,bb)                 [n,n,n,v]

ver. 0.0.2

print文の出力対象を変数から式に変更

ソースとサンプルsscr_002.lzh

文法

print [式,…];

構文規則

stmt_print: 'PRINT' list_exp ';'

list_exp :
         | expr ',' list_exp

ver. 0.0.1

仕様は以下のとおり

扱えるデータは整数値のみ
変数はグローバル変数のみ
制御構造として、if文とwhile文(break等はなし）をもつ
変数の入出力として、print文とinput文をもつ
最適化は何もしていない

ソースとサンプルはこちら

main.rb：ファイルの入出力と各クラスの呼び出し
lexscan.rb：字句解析クラスとトークンクラスの定義
perser.rb：構文解析クラスとノードクラスの定義
genasm.rb：コード生成クラスの定義

変数

英小文字で始まる、小文字の英数字列（大文字は使用不可）
[a-z][a-z0-9]*

文法

int 変数[,変数,…];
if(条件) 文
if(条件) 文 else 文
while(条件) 文
　条件：0(偽）,0以外(真）
print 変数[,変数,…];
input 変数;
式;
{文　文…｝

演算子（上が優先順位低）

代入　=
比較　==,!=,<=,<,>=,>　：0(偽）,1(真）
加減　+,-
乗除　*,/

構文規則

program  : list_stmt 'EOF'

list_stmt: 
         | stmt list_stmt

stmt     : decl_int
         | stmt_if
         | stmt_while
         | stmt_print
         | stmt_input
         | block
         | expr ';'
         | ';'

decl_int  : 'INT' list_var ';'
stmt_if   : 'IF' '(' expr ')' stmt
          | 'IF' '(' expr ')' stmt 'ELSE' stmt
stmt_while: 'WHILE' '(' expr ')' stmt
stmt_print: 'PRINT' list_var ';'
stmt_input: 'INPUT' IDENT ';'

block    : '{' list_stmt '}'

list_var : IDENT
         | IDENT ',' list_var

expr     : exp_asn
         | exp_comp

exp_asn  : IDENT '=' expr

exp_comp : exp_add
         | exp_add '==' exp_add
         | exp_add '<=' exp_add
         | exp_add '>=' exp_add
         | exp_add '<'  exp_add
         | exp_add '>'  exp_add
         | exp_add '!=' exp_add

exp_add  : exp_mul
         | exp_mul  '+'  exp_add
         | exp_mul  '-'  exp_add

exp_mul  : primary
         | primary  '*'  exp_mul
         | primary  '/'  exp_mul

primary  : IDENT
         | '-' NUMBER
         | NUMBER
         | '(' expr ')'

アセンブラ命令コード

adr       アドレス
(adr)     アドレスadrのデータ

pc        プログラムカウンタ
p         スタックポインタ（値が入っているトップを指す）
s[p]      pが示すスタックの値




命令
NOP          無実行

ADD          s[p-1]=s[p-1]+s[p], p=p-1    exp) [n,2,3]->[n,5]
SUB          s[p-1]=s[p-1]-s[p], p=p-1
MUL          s[p-1]=s[p-1]*s[p], p=p-1
DIV          s[p-1]=s[p-1]/s[p], p=p-1

CMPEQ        if s[p-1]==s[p] then s[p-1]=1 else s[p-1]=0, p=p-1  exp) [n,1,1]->[n,1]
CMPNE        if s[p-1]!=s[p] then s[p-1]=1 else s[p-1]=0, p=p-1  exp) [n,1,1]->[n,0]
CMPLE        if s[p-1]<=s[p] then s[p-1]=1 else s[p-1]=0, p=p-1
CMPLT        if s[p-1]< s[p] then s[p-1]=1 else s[p-1]=0, p=p-1
CMPGE        if s[p-1]>=s[p] then s[p-1]=1 else s[p-1]=0, p=p-1
CMPGT        if s[p-1]> s[p] then s[p-1]=1 else s[p-1]=0, p=p-1

JP    adr    pc=adr
JPT   adr    if s[p]!=0 then pc=adr, p=p-1
JPF   adr    if s[p]==0 then pc=adr, p=p-1

DEL          p=p-1

LDS          s[p]=(s[p]),p=p         exp) [n,5]->[n,5番地のデータ]
LDA   adr    s[p+1]=adr,p=p+1        exp) [n]->[n,adr]
LDI   dat    s[p+1]=dat,p=p+1        exp) [n]->[n,dat]

STS          (s[p-1])=s[p],s[p-1]=s[p],p=p-1
             exp) [n,adr,dat]->[n,dat]  (adr番地)=dat
                  ※datがスタック上に残ることに注意

PRT          p=p-1                   exp) [n,dat]->[n]          PRINT dat
INP          s[p+1]=dat,p=p+1        exp) [n]->[n,dat]          INPUT dat

STOP         停止

サンプル

-----source-----
int a,b,c;
a = 2;
b = 3;
if(a==0)
  print a;
else{
  c = a*(b+4);
  print c;
}
----------------

-----asm出力----
_VAR
_a$         INT 0
_b$         INT 0
_c$         INT 0
_END_VAR
_PROG
     LDA    _a$
     LDI    2
     STS
     DEL
     LDA    _b$
     LDI    3
     STS
     DEL
L001_IF:
     LDA    _a$
     LDS
     LDI    0
     CMPEQ
     JPF    L001_ELSE
     LDA    _a$
     LDS
     PRT
     JP     L001_END
L001_ELSE:
     LDA    _c$
     LDA    _a$
     LDS
     LDA    _b$
     LDS
     LDI    4
     ADD
     MUL
     STS
     DEL
     LDA    _c$
     LDS
     PRT
L001_END:
     STOP
_END_PROG
----------------

最終更新日 2010-05-16