「コンピュータシステムの理論と実装」を読んだメモを書いていきます。
前回のコンパイラ(字句解析器、構文解析器)の実装の記事は以下。
メモ
コンパイラ
データ変換
- 対象の変数の型、ライフサイクル、スコープなどによって変換作業が決まる
- スタックマシンへのpush/popの方法
- OSのどのサブルーチンを利用するか
- 格納するメモリ領域はヒープか、決められた領域か
- シンボルテーブル
- 対象の識別子についての情報を記録するテーブル
- 変数名なのかクラス名なのかサブルーチン名なのか、引数かローカル変数かフィールドか、など
- 同名の識別子はスコープによって別のものを指すこともあるため、シンボルテーブルは識別子のスコープも記録する
- ハッシュテーブルのリストを使ってスコープを表現する
- リストの要素は次の要素の中にネスト化されている
- 変数操作
- 配列操作
- オブジェクト操作
コマンド変換
- 式の評価
- フロー制御
- if,switch,whileを条件付きgoto, 無条件gotoで表現する
- ネストや複数のフロー制御に対応するためラベルをユニークにする
実装
前章で実装した字句解析器と構文解析器を改良してVM言語で書かれたコードを出力するコンパイラをKotlinで実装する。 実際に実装したソースコードは以下。
感想
今回の実装では、フィールドやコンンストラクタやメソッドなどオブジェクト指向の構文をVM言語に変換する点と、配列をVM言語に変換する点で苦戦した。 オブジェクト指向の構文の変換では、メソッド呼び出しの際にインスタンス変数をメソッドの第一引数として扱う必要があるため、メソッドの呼び出し側とメソッドの定義側でそれぞれlocalセグメントの値をpush する処理とargumentセグメントの値をpushする処理を埋め込むようコンパイラを改良した。
また、以下のように左辺と右辺両方に配列を利用している変換の場合、最初に左辺の配列のアドレスをTHISセグメントに代入するが、その後右辺の配列のアドレスでTHISセグメントが上書きされてしまうので、左辺の配列のアドレスがわからなくなってしまう。
// ... let a[0] = b[0] // ...
そのため左辺の配列のアドレスを計算した後、すぐにPOINTER 1に値をpopするのではなく一度TEMPセグメントに値を退避させて、右辺の値が計算できたあとでTEMPセグメントの値をPOINTER 1にpopするようコンパイラを改良した。 この際にpush/pop TEMP 0と記述していたが、OSのサブルーチンとして元々用意されていたVM関数の内部でTEMP 0をすでに利用していたため、うまくプログラムが動作せず2時間近くハマってしまった。
(追記) 2020年12月に原著の第2版がでるらしい www.amazon.com
次章はこちら