rowl0: コード生成の実装 - ブートストラッピングでコンパイラを作る日記

通常のコンパイラは大体こんな感じになっているが、

パース(構文木生成) → 型チェック等 → 中間言語化 → 最適化
 → 低レベル中間言語化 → スケジューリング&レジスタ割り当て → コード生成

rowl0はアセンブリ実装の為、簡略化して

パース(コード生成)

となっている。つまり、構文木を一切作らずにパースしつつコード生成をしている。
これはスタックに頼れば簡単にできる。
例えば

e1 + e2

の場合は

(e1のアセンブリコード %eaxに戻り値)
pushl %eax
(e2のアセンブリコード %eaxに戻り値)
movl %eax, %ebx
popl %eax
addl %ebx, %eax

のようなpush/popを使用するコードを生成すればよい。

変数

rowl0では識別子表を作っていないので、ある変数が関数パラメータなのかローカル変数なのか分からない。そこで

関数パラメータ: p0,p1,p2...
ローカル変数: x0,x1,x2..
グローバル変数: その他識別子

ということにしている。これなら"p0 ==> 8(%ebp)", "x0 ==> -4(%ebp)"等のようにコード生成ができる。
このような仕様でも、コンパイラを実装する上でほとんど困らない。

一方、アセンブリレベルで識別子表を作るには

mmap2を使ってヒープメモリを確保するコードを書く
ハッシュテーブルを実装する

という手間が掛かるので、この方法でさっさとコンパイラ完成させて、次世代のコンパイラから識別子表を実装した方が楽である。

代入文

厄介なのが代入文。

e1 = e2;

のようなコードは

(e2のアセンブリコード)
movl %eax, (e1の示すストレージ)

というコードにコンパイルする必要があるけど、e1をパースしている最中にはそれが代入文の左辺なのか他の式の一部なのか分からない為、式全体をパースするまで(構文木を作るまで)コードが生成できない。
rowl0では文法を制限する事でこれに対処している。

ToplevelExpr
    : Identifier ':' OrExpr
    | Identifier '=>' (Integer|Identifier)
    | Identifier '=' OrExpr
    | Identifier '(' Arguments')'
    | Identifier '[' OrExpr ']' '=' OrExpr
    | '*' PrefixExpr '=' OrExpr
    ;

つまり、一番最初が'*'なら確実に間接代入。一番最初がIdentifierならもう１記号読めば式の意味が分かる。それ以外は不適。という実装になっている。

他にもいろいろ細かい問題はあるけど、字句解析と上のようなやり方で非常に簡単にアセンブリでコンパイラを実装できます。(rowl0の場合コンパイラ全体で3500行くらい)