コンピュータシステムの理論と実装 (11)

前章で構文解析まで終了しているので、今回はシンボルテーブルの管理とコード生成の部分を完成させていく。

11 章コンパイラ#2: コード生成

シンボルテーブルの実装

まずは変数の管理から。本文に記載されている通り、
- サブルーチンスコープ
  - argument: サブルーチンの入力を指定する仮引数 (パラメータ変数)
  - local: サブルーチン内のみで有効なローカル変数。var で宣言
- クラススコープ
  - field: C++ や Python でいうクラスのメンバ変数
  - static: クラスの先頭で宣言される変数であり、そのクラスから生成される全てのオブジェクトで共有される
に Python の dict の形で格納していく。参照するときは当然サブルーチンスコープを優先する。
次に関数の方を何とかしなくてはならない。Jack 言語には 3 種類の Subroutine があり、
- function: クラスに附属し、インスタンスに依存しない。呼び出すときは className.subRoutineName()
- constructor: 慣例的に new という名前が用いられる。呼び出すときは function と同じ
- method: C++ や Python でいうメンバ関数。インスタンス依存。呼び出すときは、同一クラス内なら単に subRoutineName()、そうでなければ instanceName.subRoutineName()
となる。
サブルーチンの種類が method である場合、call 時にインスタンスの参照を隠れ引数として push しなければならないため、call をコンパイルする際にはサブルーチンの種類判定が必要になる。ここで、コンパイラが関数の call に遭遇した際の挙動を考えてみる。subRontineName() の際は method で確定。hoge.subRoutineName() の際は、hoge が既に宣言されており上記の変数シンボルテーブルに登録されていればインスタンス (つまりこのサブルーチンは method)、そうでなければ hoge はクラス名でサブルーチンは constructor あるいは function であることが確定する。
呼び出し時にサブルーチンが method であるかどうかさえ判定できればよいので、サブルーチンのシンボルテーブルをわざわざ作成しなくてもとりあえずコンパイルは可能である。当該クラスにそのサブルーチンが本当に存在するかどうかの判定は行わないことになるため、ない関数を書いても一切のエラーを吐かない激ヤバコンパイラが出来上がることになるが……。

コード生成

ここからは、各処理の概要とそれぞれの躓きポイントをメモしていこうと思う。実際の作業は、公式で提供されているコンパイラで .jack から .vm の正解ファイルを生成し、自分のコンパイラから出力されたファイルと正解のファイルを比較することにより行った。

サブルーチン宣言のコンパイル
- サブルーチンの種類が何であれ、VM コード上では function 表記になるので注意。Main クラス内にある hoge というサブルーチンがあり、内部で n 個のローカル変数が定義される場合の宣言は function Main.hoge n となる。n の値自体は subRoutineBody をコンパイルしてみないと分からないため、とりあえず空欄にしておき処理後に追記する方針とした。
- サブルーチンの種類が method のときは this がオブジェクトのベースアドレスを指すようにしなくてはならないため、push argument 0 pop pointer 0 を宣言後すぐに書く。
- サブルーチンの種類が constructor である場合は field 変数のためにメモリ割り当て作業も行う必要があるため、push constant n call Memory.alloc 1 pop pointer 0 を宣言後すぐに書くことになる。

let のコンパイル let a[1] = ... を処理するときは、次のようなコードを生成することになる。

  
push constant 1 // 添字
push local 2 // a が 3 番目に宣言されたローカル変数の場合
add // これで、スタックトップが a[1] のアドレスになる
// (右オペランドを処理してスタックトップに持ってくる)
pop temp 0 // 右オペランドの処理結果を temp 0 に退避する
pop pointer 1 // that の指す先をスタックトップ、つまり a[1] にする
push temp 0 // 退避しておいた右オペランドの処理結果をスタックトップに戻す
pop that 0 // 右オペランドの処理結果を that の指すアドレス、つまり a[1] の位置に格納

while のコンパイル

while 文のコンパイル結果は以下のようになるので、これを目標にコード生成をすればよい。

  
label WHILE_EXP0
// while () のカッコ内に入る expression を処理
not
if-goto WHILE_END0 // カッコ内が false の場合、ここが true になり末尾に跳ぶ
// {} 内の statements を処理
goto WHILE_EXP0
label WHILE_END0

while 文の始まりと終わりに固有のラベルを振って制御することになるが、ここで他の while 文のラベルと被らないようにラベルの末尾にカウンタを振ることにする。ここで注意すべきは while 文が多重になっているときであり、この場合 statements 処理時に再帰で呼び出しまくっていると while 文のカウンタがめちゃくちゃになりうる。今回のコードでは、クラスのメンバ変数で管理しているカウンタとは別に関数内でカウンタの値を保持しておく方針とした。

if のコンパイル

コンパイル結果は以下のようになる。while 同様、多重になっている場合の処理に注意が必要。

  
// (expression) の処理
if-goto IF_TRUE0
goto IF_FALSE0
label IF_TRUE0
// {true のときの statements}
goto IF_END0
label IF_FALSE0
// {false のときの statements}
label IF_END0

return のコンパイル
- return hoge; の場合は hoge を処理してスタックトップに載せてから単に return と書けばよい。
- void の関数であり単に return; の場合でも、簡単のため push constant 0 return と疑似的に 0 を返すようにする。
do のコンパイル
- do subRontineName() の場合
  - 上述の通りその関数は method であることは確定なので、push pointer 0 をすることにより this の指す先、つまりオブジェクトの参照を隠れ引数として push してから他の引数を push し、その後 call className.subRoutineName n する必要がある (n はパラメータの数)。
- do hoge.subRoutineName() の場合
  - hoge がインスタンスの場合その関数は method であるため、まず push local 0 などでインスタンスを隠れ引数として push する。他の引数を push したのち、インスタンスの型名 (つまりそのインスタンスの生成元であるクラス名) を取得して call className.subRoutineName n とする。
  - それ以外の場合 hoge はクラス名であるため、単に call className.subRoutineName n とすればよい。
- call の末尾につけるべき n はパラメータ処理の後でないと判明しないため、とりあえず空欄にしておいて後で埋める方針を採った。method の場合は +1 すべきなので注意。
- 上述の通り、void の関数を実行したとしてもスタックトップには 0 が残ってしまう。これを解決するため、いずれの場合でも末尾に pop temp 0 を追記して値を捨てる。
expression のコンパイル
- 例えば a - b のコンパイルの場合、push a push b sub とすればよい。
- ややこしいのが、単なる -b のときは push b neg としなければならないこと。- 記号が登場した場合は、それが expression の先頭に位置する token でないかどうかをチェックする必要がある。

term のコンパイル

let のコンパイル時にも問題になったが、a[1] のような term の処理は以下のようにする。

  
push constant 1 // 添字
push local 2 // a が 3 番目に宣言されたローカル変数の場合
add // これで、スタックトップが a[1] のアドレスになる
pop pointer 1 // that が a[1] を指すようにする
push that 0 // that の指す先、つまり a[1] の中身をスタックトップに持ってくる

文字列処理
- まず文字列の文字数 l を取得し、push constant l call String.new 1 とする。
- アルファベットの指定は Unicode コードポイントを用いて行うことになり、これは Python では組み込み関数の ord() で実現できる。末尾に a を追加した場合、push constant 97 call String.appendChar 2 を呼べばよい。

感想

とりあえずできたはいいものの、一切のシンタックスエラーを検出しないばかりか、存在しない関数を書いてもなんの疑いもなくコンパイルが通るようになっておりとても実用に耐えるものではない。
完成したコンパイラはこれ、シンボルテーブルはこれである。慣れない言語においてコンパイラ作成という目新しい作業をすることになったのでめちゃくちゃ疲れた。

コンピュータシステムの理論と実装 (11)

11 章 コンパイラ#2: コード生成

シンボルテーブルの実装

コード生成

感想

Further Reading

コンピュータシステムの理論と実装 (7)

コンピュータシステムの理論と実装 (8)

コンピュータシステムの理論と実装 (10)

11 章コンパイラ#2: コード生成