122 ー 6 章アセンフラ アセンプリコード ( p て。 g. asm) / / 1 から 100 までの整数の和 バイナリコード ( p て og . hack) にの行は消去される ) 1110 1111 1100 10 0 0 0000 0000 0001 0 0 01 1110 1010 10 0 0 10 0 0 ( この行は消去される ) 0 0 01 110 0 1111 0 0 01 0 00 0 0110 010 0 1110 010 0 1101 0 00 0 0 0 01 0 010 を 1110 0 011 0 0 01 0 00 0 0 0 01 = 「 1111 110 0 0 001 0 0 00 0 001 0 0 01 0 0 0 0 1111 10 0 0 10 0 0 0 0 01 00 0 0 1111 1100 1101 1 0 0 0 0 0 0 0 010 0 コ 110 1010 10 0 0 0111 にの行は消去される ) 0 010 1110 1010 10 0 0 0111 1 0 0 sum= に 00P ) D=M @ 10 0 D=D—A D = 土ー 100 @END もしい一 10 の > 0 ならば END に移動 D; JGT D=M @sum M=D 十 M sum=sum 十土 M=M + 1 土 = i 十 1 3L00P 0 ;JMP LOOP に移動 D= 土 アセンプラ D= 土 (END) @END / / 無限ループ 0 JMP 図 6 - 2 同じプログラムに対するアセンブリとバイナリ表現 Parser モシューノレ 入力に対して構文解析 ( パース ) を行う。 COde モシュール アセンプリコードのニーモニックすべてをビットコードへ変換する。 SymboITabIe モジュール シンポルを扱う。 メインプログラム 変換処理のすべてを行う。

160 ー 7 章バーチャルマシン # 1 CodeWriter モジュール : スタック操作 VM コマンドを Hack アセンプリコードに変換する ( 表 7-2 ) 。 表 7 -2 CodeWriter モジュールの API ノレーチン コンストラクタ setFiIeName writeArithmetic writePushPop C 1 〇 S e 入力ファイル / ストリーム 引数 index ( 整数 ) segment ( 文字列 ) 、 または C_POP) 、 command (C_PUSH command ( 文字列 ) fileName ( 文字列 ) 戻り値 機能 出力ファイル / ストリームを開き、 書き込む準備を行う CodeWriter モジュールに新しい VM ファイルの変換が開始した とを知らせる 与えられた算術コマンドをアセン プリコードに変換し、それを書き 込む C_PUSH または C_P 〇 P コマンド をアセンプリコードに変換し、そ れを書き込む 出力ファイルを閉じる 8 章で、このモジュールにさらにルーチンが追加される。 メインプログラム 合、入力ファイルごとに別の Parser を使い、出力ファイルを扱うために CodeWriter ディレクトリに含まれるすべての . vm プログラムを処理しなければならない。その場 プログラムの引数がファイルではなくディレクトリの場合、メインプログラムはその ンドを 1 行すっ読み進めながら、アセンプリコードへと変換する。 プリコードを出力ファイルへ書き込む準備を行う。そして、入力ファイルの VM コマ モジュールで VM の入力ファイルのパースを行い、 Code 从子 iter モジュールでアセン メインプログラムでは Parser モジュールと Code Ⅵ石 ter モジュールを用いる。 Parser モジュールをひとつだけ用いる。 7.4 展望 本章は、高水準言語のコンパイラを開発する初めの一歩であった。我々が目指すコ

10.3 実装ー 237 図 10-4 は解析器の出力を示しているが、前にも同じようなものを見てきたはずで ある。本章の前のほうでは、プログラムの構造は構文木 (parse tree) へと解析される ことを示した ( 図 10-3 参照 ) 。実際、この XML の構造は、その木構造を単にテキス トで表現したものにすぎない。構文木の構造を見れば、「非終端記号が木の終端ノード からどのように構成されるか」ということがわかる。これは XML 出力においても同 様である ( つまり、 XML の非終端要素は、終端要素からどのように形成されるかとい うことを表している ) 。同様に、トークナイザによって生成されたトークンは、プログ ラムの構文木における終端記号と同じように、 XML 出力の最下部の要素に該当する。 セットアップや他モジュールの呼び出しを行うモジュ 10.3 実装 れによって、完全版の Jack コンパイラができあがる。 成するモジュールを実行可能な VM コードを生成するモジュールへと置き換える。そ こでは解析器の XML 出力について、その仕様を示した。次章では、 XML を生 コード生成 川 .2 節では、 Jack 言語のための構文解析器の作り方について、実装部分の詳細を省 いて説明を行った。本節では構文解析器の実装案を提示する。本書では、次の 3 つの モジュールを用いて実装を行うことを推奨する。 JackAnalyzer JackTokenizer トークナイザ。 CompiIationEngine これらのモジュールは言語の「構文」を扱う。次章では 再帰によるトップダウン式の解析器。 ール。 衄の「意味」に対応す るため、さらにふたつのモジュールを追加する。ふたつのモジュールとは、シンポル テープル (symbol table) と VM コード書き込み器 (VM-code writer) である。そ のモジュールを追加することで、 Jack 言語のコンパイラは完成に至る。本プロジェク トで作る構文解析を行うモジュールは、コンパイル全体を駆動する存在となるため、 そのモジュールを CompiIationEngine と呼ぶことにする。

xxii ーイントロダクション : こんにちは、世界の下側 得るためには - ーーそして、骨の髄まで理解するには どのような方法がベストで あろうか ? 答えは、完全なるコンピュータシステムをゼロから構築すること。それが 筆者らの答えである。 抽象化 「完全なコンピュータシステムを、人の手でゼロから作り上げることが果たして可能 だろうか ? 」と疑問に思ったかもしれない。しかも、最初に使える材料は基本的な論 理ゲートだけであり、そこを出発点としなければならない。これは途方もなく複雑な 仕事に相違ない。我々はこの複雑性に対して、プロジェクトをモジュールに分割する ことで対処する。各モジュールは別個に独立した章で扱う。これを聞いて、「どのよ うにして、モジュール単位で独立に説明し、組み立てを行うのか ? 」と、またしても 疑問に思ったかもしれない。明らかに、それらのモジュールはすべて相互に関係性を 持つ ! これは本書を通して明らかになっていくことだが、優れたモジュール化を行え ば、各モジュールに対して、そのモジュールだけを考えることができる。つまり、他 のモジュールとは独立して一一その他のシステムについては考えないで一一一開発に取 り組める。実際のところ、自分の好きな順番でこれらのモジュールを組み立てていく ことも可能である。 このモジュール化による計画がうまく機能するのは、人間に与えられた特別な才能 のおかげである。特別な才能、それは、物事を抽象化して考える能力に他ならない。 「抽象化」という言葉は、心理的な思考において、ある物事の本質的要素を簡潔な方法 で提え、それを抜き出し、分離して考えるときに使われるのが一般的である。一方、 コンピュータサイエンスの分野で「抽象化」という言葉が使われる場合は、次のよう に非常に具体的な意味合いで使われる。それは「この要素は何をするのか (what) 」 だけを考え、その詳細である「それをどのように行うのか (how) 」は無視するという ことである。この機能部分のみを記述するためには、その要素に関係のない情報は含 めすに、それを使うために必要な情報はすべて記載する。つまり、その要素の実装部 分にかかわる情報は、それを使おうとするユーザーの目に触れてはならない。なぜな ら、ユーザーにとってそれは意味のない情報だからである。そのような抽象化を用い ることは、我々のような実践的な専門職を遂行するにあたって、基本となる考え方で ある。ハードウェア開発者またソフトウェア開発者は誰でも、常日頃、そのような抽 象化 ( または「インターフェイス」と呼ばれる ) について考える。そして、その抽象 化を実装するのである ( もしくは、他の人にその実装を頼むのである ) 。この抽象化は

アセンプラの開発は 5 つのソフトウェア開発における最初のプロジェクトであ る。この 5 つのプロジェクトにおいて、我々は変換器の階層 ( アセンプラ、バー チャルマシン、コンパイラ ) を構築する。これらのプロジェクトを開発するた めに、読者は自分の好きなプログラミング言語を用いることができる。そのた め、言語に依存しない形で、 API の実装ガイドラインを提示する。 一般的なプロジェクトの API は複数のモジュールで表現され、各モジュール はひとつまたは複数のルーチンを含む。 Java 、 C 十十、 C # などのオプジェクト 指向の言語では、モジュールはクラスに、ルーチンはメソッドに対応する。手 続き型言語においてルーチンに対応するのは、関数、サプルーチン、プロシー ジャなどであり、モジュールは関連データを処理するルーチンの集合に対応す る。ある言語においては ( たとえば、 Modula-2 など ) モジュールは明示的に 宣言され、他の言語においては ( C 言語ファイルなど ) 暗黙的に表され、また ある言語においては (pascal など ) 対応するコンストラクタを持たす、ルーチ ンの概念的な集合だけを持つ。 6.3.1 Pa 「 se 「モジュール 主な機能は各アセンプリコマンドをその基本要素 ( フィールドとシンポル ) に分解 することである。具体的には、入力コードへのアクセスをカプセル化し、アセンプリ ロ語のコマンドを読み、それをパースし、コマンドの要素 ( フィールドとシンポル ) へ 簡単にアクセスできるようなルーチンを提供する。さらに空白文字とコメントを削除 する。 API は表 6-1 のようになる。 表 6-1 Parser モジュールの API 6.3 実司 API 表記についての注意点 プール値 123 ルーチン コンストラクタ / 初期化 hasMoreCommands 入力ファ イル / スト 引数 戻り値 機能 入力にまだコマンドが存在するか ? 行う準備をする 入力ファイル / ストリームを開きパースを

184 ー 8 章バーチャルマシン # 2 : プロクラム制御 8.3.3 VM 実装の設計案 7 章で作成した基本となる VM 変換器はふたつのモジュールをベースとした。その ふたつのモジュールは Parser と CodeWriter というモジュールであった。この変換 器を完全版の VM 実装へと拡張するために、このふたつのモジュールに以下に示す機 能を追加する。 Parser モジュール もし 7 章で実装した Parser モジュールが本章で指定した 6 つの VM コマンド をパースする準備ができていなければ、それを追加すること。 6 つのコマンドとは C_LABEL 、 C_G 〇 T 〇、 C_ 工 F 、 C_FUNCTION 、 C_RETURN 、 C_CALL である。 7 章で 実装した commandType というメソッドは、この 6 つのコマンドも対応しなければ ならない。 CodeWriter モジュール 7 章で実装した CodeWriter を拡張する。具体的には、 VM コマンドをアセンプリ コードへ変換する。表 8-1 に挙げるルーチンは 7 章で与えた API に追加して実装す る必要がある。 8.4 展望 サプルーチン呼び出しとプログラムのフロー制御は、高水準言語において必須の機 能である。これが意味することは、高水準言語がバイナリコードへと変換される過程 のどこかで、誰かがその複雑なハウスキーピング処理を行わなければならない、とい うことである。 Java や C# 、 Jack などの言語において、この仕事は VM のレベルで 行われる。そして、本章で示したとおり、スタックベースの VM は、この仕事を行う のに適している。一般的に言って、サプルーチン呼び出しと再帰処理をプリミテイプ な機能として実装したバーチャルマシンは、重要で有益な抽象化を行っていることに なる。 もちろん、これは実装に関する選択肢のひとつにすぎない。あるコンパイラは、 VM をまったく用いないでサプルーチン呼び出しを直接扱う。また、他のコンパイラは VM の形式は使用するが、サプルーチンを扱うために用いない。さらに、あるアーキテク チャにおいては、ほとんどのサプルーチン呼び出しに関する機能はハードウェアで直 接扱われる。

XXXiV 一目冫欠 10 章コンバイラ # 1 : 構文解析 10.1 背景・ 10.1.1 10.1.2 10.1.3 川 .2 仕様・・ 10.2.1 10.2.2 10.2.3 川 .3 実装・・ 10.3.1 10.3.2 10.3.3 10.4 展望・・ 字句解析・ 文法・ 構文解析・ Jack 言語のための構文解析器・・ Ja. ck 言語の文法・ 構文解析器への入力・ 10.2.4 構文解析器の出力・ JackAnalyzer モジュール・ JackTokenizer モジュール・ CompilationEngine モジュ 11 章コンバイラ # 2 : コード生成 10.5.3 第 2 段階 : パーサ・ 川 .5.2 第 1 段階 : トークナイザ・ 10.5.1 テストプログラム・ 10.5 プロジェクト・ 11.1 背景・ 11.1.1 11.1.2 11.2 仕様・・ 11.2.1 11.2.2 11.3 実装・・ 11.3.1 11.3.2 11.3.3 11.3.4 1 工 3.5 データ変換 . コマンド変換・ バーチャルマシンへの標準マッピング・ SymbolTabIe モジュ JackTokenizer モジュール・ JackCompiler モジュ コンノヾイルの例 CompilationEngine モジュ VMWriter モジュール・・ 223 ・ 268 ・ 268 ・ 266 ・ 266 ・ 266 ・ 264 ・ 264 ・ 261 ・ 261 ・ 258 ・ 251 ・ 250 249 ・ 247 ・ 246 ・ 244 ・ 243 ・ 242 ・ 240 ・ 239 ・ 239 ・ 237 ・ 236 ・ 235 ・ 234 ・ 232 ・ 231 ・ 229 ・ 227 ・ 226 ・ 224

10.3 実装ー 239 10.3.1 JackAnaIyzer モジュール JackAnalyzer モジュールには s 〇 urce が与えられる。この s 〇 urce は xxx . jack というファイル名、もしくはひとつ以上の . j ack ファイルを含むディレクトリ名の どちらかである。ソースとなる各 xxx . j ack ファイルに対して、 JackAnalyzer モ ジュールは次のロジックによる処理を行う。 1. 2. 3. 入力ファイルの xxx . jack から、 JackTokenizer を生成する。 xxx . xml という名前の出力ファイルを作り、それに書き込みを行う準備をする。 入力である JackTokenizer を出力ファイルへコンパイルするために CompilationEngine を用いる。 1 3.2 JackTokenizer モジュール JackTokenizer モジュールは入力ストリームからすべてのコメントと空白文字を取 り除き、 Jack 文法に従い Jack 言語のトークンへ分割する ( 表 10-1 ) 。 表 1 0-I JackTokenizer モジュールの API コンストラクタ tokenType advance hasMoreT 〇 kens 引数 入力ファイル / ストリーム 戻り値 プールイ直 KEYWORD 、 SYMBOL 、 IDENTIFIER 、 INT CONST 、 S T R 工 NG C ON S T 機能 入力ファイル / ストリームを開き、 トークン化を行う準備をする 入力にまだトークンは存在するか ? 入力から次のトークンを取得し、 それを現在のトークン ( 現トー クン ) とする。このルーチンは、 hasMoreTokens ( ) が true の場合のみ呼び出すことができる。 また、最初は現トークンは設定され ていない 現トークンの種類を返す

ー 339 録言 リ ク ス ト ス 失敗は発見の扉である。 作家ジェイムス・ジョイス ( 1882 ー 1941 ) システム開発において、テストを行うことは非常に重要である。しかしながら、コ ンピュータサイエンスの教育においては、その重要性が説かれることはめったにない。 本書では、テストを重要な要素として扱っている。もっとも筆者らの信するところに よれば、 P という新しいソフトウェアモジュール ( もしくはハードウェア ) を作る前 に、それをテストするための T というモジュールを先に開発すべきである。さらに T は P の正式な開発規約の一部とすべきである。 新たに設計したモジュールの最終的なテストは、そのモジュールの開発者ではなく、 そのモジュールのインターフェイスの設計者によって書かれるべきである。それがべ ストプラクティスであろう。そのため、本書で提示したすべての回路およびソフトウェ アシステムには、著者らによって書かれた正式なテストプログラムが用意されている。 自分の仕事を自分のやり方で進めるのは一向にかまわないが、テストはその最終的な 規約である。そのため、あなたの実装は本書のテストを通過しなければならない。 本書ではいたるところでテストを行う。テストを効率良く行うために、筆者らは統 一されたテストスクリプト言語 (test scripting language) を設計した。この衄は に 1 ロロ、 本書のすべてのシミュレータでほとんど同じように動く。本書で提供するシミュレー タは以下に示すとおりである。 ハードウェアシミュレータ HDL で書かれた回路をシミュレートし、テストを行うために用いる。 CPU 工ミュレータ 機械語で書かれたプログラムをシミュレートし、テストを行うために用いる。

266 い 1 章コンバイラ # 2 : コード生成 1 れ 3.1 JackCompiIer モジュール コンパイラは与えられた s 〇 urce に対して処理を行う。 s 〇 urce は、 xxx. jack と いうようなファイル名、もしくは、 . j ack ファイルが含まれるディレクトリ名である。 入力ファイルである各 xxx . jack に対して、コンパイラは JackTokenizer と出力ファ イルである xxx. vm を生成する。続いて、 3 つのモジュールーーーー CompiIationEngine 、 SymbolTabIe 、 VMWriter—を用いて出力ファイルへ書き込みを行う。 1 1 .3.2 JackTokenizer モジュール トークナイザの API は 10.3.2 節で与えたものと同じである。 11.3.3 Symbo 灯åb 厄モジュール このモジュールは、シンポルテープルの作成とそれを使用するためのサービスを提 供する。シンポルはそれぞれにスコープがあり、そのスコープによってソースコード 内で各シンポルの見える範囲が決定される。シンポルテープルはこの抽象化を実装す るために、各シンポルにスコープ内における実行番号 ( インデックス ) を与える。イン デックスは 0 から始まり、テープルに識別子が追加されるたびに 1 すっ加算され、新 しいスコープが始まると 0 にリセットされる。次に示す属性の識別子がシンポルテー プルに現れる ( 可能性がある ) 。 Static スコープ : クラス スコープ : クラス Argument ーチン ( メソッド / ファンクション / コンストラクタ ) スコープ : サプル ーチン ( メソッド / ファンクション / コンストラクタ ) スコープ : サプル 工ラーのない Jack コードをコンパイルした場合、シンボルテープルで見つからない 哉別子があると、それはサプルーチンかクラスの名前のどちらかであると想定するこ とができる。 Jack 言語の構文では、そのふたつの可能性を見分けることができるルー ルがあるため、そして、コンパイラによって " リンク " を行う必要がないため、それ Field Var