（超簡易な）コンパイラを（参考コードありで）書いてみた

じゅくちょーです。私はJava製JITコンパイラGraalにとても強く興味を持っています。

Graal の検索結果 - Fight the Future

Graalのコードを読んでいる内に、自分はGraalの前にそもそもコンパイラをよく理解していないと感じるようになりました。コンパイラに関してはたくさんよい書籍があるようですが、きしださんのブログで以下の書籍を見つけ、読みました。

d.hatena.ne.jp

コンパイラとバーチャルマシン (IT Text)

大学生の教科書向けの本です。200pちょいと薄いです。わかりやすくおもしろい本でした。

この本にはCのサブセットな言語ChavaのコンパイラをJavaで書いたコードが掲載されています。つまり、サブセット言語をJavaのクラスファイルに変換するコンパイラです。

ただ、このコンパイラはソースを逐次的に読み取って字句解析/構文解析しています。そして、2004年発刊ではありますが利用しているAPIがかなり古いものです（VectorやHashTable）。なんと、コンパイラは1ファイルにすべて書かれています。インナークラスは多くありますが、全クラスがアウタークラスのフィールドを参照していたりします。

そこで、このCのサブセット言語の定義に対してBNFを書き、Lexer/Parserに以前も使ったANTLRを使い、その後は書籍のコードを参考にしながら自分でクラスファイルに変換してみようと思い立ちました。

この書籍のコードには著作権がありますので、それはあくまで参考として自分でコード書きました。処理方法もクラス階層もまったく違っているので著作権違反は意図していませんが、もし違反を見つけたらぜひ教えてください。すぐに修正します。

github.com

BNFでの定義はやや冗長に記述している感がありますが、書籍にある定義のままANTLRのBNFで書いています。BNFでの言語定義はこちらです。

Subset-of-C-Compiler/SubsetC.g4 at master · jyukutyo/Subset-of-C-Compiler · GitHub

できることはグローバル/ローカル変数の定義、関数の定義と呼び出しで、型はintのみです。コンパイルするとグローバル変数はJavaのstatic変数に、関数はJavaのstaticメソッドとなります。制御構造としてifとwhileが使えます。ただしelse ifやelseは使えません。

こんな感じのコードが書けます。

int i;
void main() {
  i = 2;
  int x;
  x = 3;
  if (i < x) {
    mul(i, x);
  }
}
int mul(int a, int b) {
  return a * b;
}

ANTLRでASTまでできますので、ANTLRで提供されるListenerを実装して自作のノードツリーに変換し、最後はバイトコードをファイルに書き込みます。

書籍のコードはノードが親を持つのですが、ANTLRのListenerではその構造はしづらそうなので、親は持たず子のみを持つノードで実装しました。

基本的な登場クラスはノード関連クラスを除くとほんの少しです。

• Compiler
• ClassFile
• ConstantPool
• Field
• Method

Compilerのmain()メソッドでコードを書いたファイルを読み、1ファイル1クラスとしてClassFileを作ります。ClassFileはConstantPoolとField、Methodを持ち、出力時にはそれぞれにバイトコードを出力させる作りです。制御構造だとバックパッチがあるので、バイトコード出力のあたりはかなり書籍のコードを参考にしています。

Javaコマンドでコンパイルを実行します。

com.sakatakoichi.subsetc.compiler.Compiler Test.jyu

javapすると以下のようになっています。

$ javap -v Test
Classfile /Test.class
  Last modified 2018/04/16; size 214 bytes
  MD5 checksum 6a83da14906e8a09f82fdba3c412777f
class Test
  minor version: 0
  major version: 52
  flags: (0x0020) ACC_SUPER
  this_class: #2                          // Test
  super_class: #4                         // java/lang/Object
  interfaces: 0, fields: 1, methods: 2, attributes: 0
Constant pool:
   #1 = Utf8               Test
   #2 = Class              #1             // Test
   #3 = Utf8               java/lang/Object
   #4 = Class              #3             // java/lang/Object
   #5 = Utf8               i
   #6 = Utf8               I
   #7 = NameAndType        #5:#6          // i:I
   #8 = Fieldref           #2.#7          // Test.i:I
   #9 = Utf8               ()V
  #10 = Utf8               main
  #11 = NameAndType        #10:#9         // main:()V
  #12 = Methodref          #2.#11         // Test.main:()V
  #13 = Utf8               Code
  #14 = Utf8               (II)I
  #15 = Utf8               mul
  #16 = NameAndType        #15:#14        // mul:(II)I
  #17 = Methodref          #2.#16         // Test.mul:(II)I
{
  public static void main();
    descriptor: ()V
    flags: (0x0009) ACC_PUBLIC, ACC_STATIC
    Code:
      stack=1, locals=1, args_size=0
         0: getstatic     #8                  // Field i:I
         3: if_icmpge     20
         6: nop
         7: iload_0
         8: getstatic     #8                  // Field i:I
        11: invokestatic  #17                 // Method mul:(II)I
        14: pop
        15: iconst_3
        16: istore_0
        17: iconst_2
        18: putstatic     #8                  // Field i:I
        21: return

  public static int mul(int, int);
    descriptor: (II)I
    flags: (0x0009) ACC_PUBLIC, ACC_STATIC
    Code:
      stack=2, locals=2, args_size=2
         0: iload_0
         1: iload_1
         2: imul
         3: ireturn
}

これを逆アセンブルすると、こうなりました。

class Test
{
  private static int i;
  
  public static void main()
  {
    int j;
    if (i < j)
    {
      mul(j, i);
      j = 3;
      i = 2;
    }
  }
  
  public static int mul(int paramInt1, int paramInt2)
  {
    return paramInt1 * paramInt2;
  }
}

この書籍がなければ絶対に書けなかったと思います。とても学びになりました。書籍の課題にもあるように、今はintだけなのでdoubleも処理できるようにまたやってみるかもです。