コンパイラの仕組みを学ぶために、いまCコンパイラを書いています。

Cコンパイラは、ソースコード（文字列）をアセンブリ言語に変換するものです。

このコンパイラは、まず文字列をトークンに分解し、次にトークンを使って文字列をノードにパースし、最後にアセンブリを生成します。

  • トークナイザ
  • パーサ
  • コードジェネレータ

トークナイザ

トークナイザは文字列を走査して、トークンの連結リストを作ります。

パーサ

パーサは文字列をノードにパースします。

パーサを実装するには、コンパイラの設計が必要です。コンパイラの設計には通常、BNF（バッカス・ナウア記法）という記法を使います。

BNF記法は次のようなものです。

expr = num ("+" num | "-" num)*

これは加算と減算のシンプルな例です。 この式は数値を1つ受け取り、続く数値があればそれを加算または減算します（* は0回以上の繰り返しを意味します）。

コードジェネレータ

コードジェネレータはアセンブリを生成します。

先ほどのBNFの例は、次のようなアセンブリに変換されます。

.intel_syntax noprefix
.globl main
main:
    push 2
    push 3
    pop rdi
    pop rax
    add rax, rdi
    push rax
    pop rax
    ret

これは 2 + 3 を意味し、スタックマシンとして実装されています。

まず 2 と 3 の2つの数値をプッシュし、3 を rdi（アセンブリのレジスタ）に、2 を rax（アセンブリのレジスタ）に代入します。 最後に 2 + 3 を計算し、その結果を rax に代入します。 この例では続く2つの命令は無視して構いません。単に rax = rax をしているだけだからです。 ret が結果、つまり 5 を返します。

進捗

現時点では、数式の計算まで実装できました。

ソースコードは github にアップロードしています。