コンピュータシステムの理論と実装の11章のコンパイラ#2：コード生成を実装しました

コンピュータシステムの理論と実装 nand2tetris コンパイラ C言語

前回の続きです*1。今回はコンピュータシステムの理論と実装（以下、nand2tetris本）の11章のコンパイラ#2：コード生成をC言語で実装してみました。

今回のコード

下記、タグv0.0.4になります。

github.com

下記で動かせます。

git clone -b v0.0.4 https://github.com/nihemak/nand2tetris.git
cd nand2tetris
# download nand2tetris environment
./setup.sh
# test all
./test.sh

概要

今回はコンパイラのコード生成部分です。実装は書籍にしたがって２段階で行いました。

  1. シンボルテーブルを実装し10章で実装した構文解析器を拡張し解析結果である.xmlファイルに付加情報を追加
  2. 構文解析器を7章と8章で実装したバーチャルマシンで動く.vmファイルを生成するコマンドに改造

シンボルテーブル

ソースコードは11/JackCompiler/です。

ここではシンボルテーブルを作成し識別子（変数）の下記の情報を管理できるようにしました。

情報 概要
名前 識別子の名前（変数名）
型 int or boolean or char or クラス名
属性(スコープ) Static or Field or Argument or Var
属性内でのindex 属性ごとに0からの連番を付与

そして10章で実装した構文解析器の出力XMLのidentifierタグにシンボル情報を追加しました。

下記で使えます。

test11.sh:L3-L39

cp -r ./nand2tetris/projects/10/Square 11/JackCompiler/ && \
mkdir -p 11/JackCompiler/Square/expect && \
mv 11/JackCompiler/Square/*.xml 11/JackCompiler/Square/expect/
patch -p1 -d 11/JackCompiler/Square/expect < 11/JackCompiler/test/Square.patch

# ...(省略)...

cd 11/JackCompiler/

clang --std=c11 -Wall -Wextra -o JackCompiler main.c JackTokenizer.c JackTokenizerPrivate.c SymbolTable.c SymbolTablePrivate.c CompilationEngine.c

./JackCompiler Square
./JackCompiler ExpressionLessSquare
./JackCompiler ArrayTest

cd -

./nand2tetris/tools/TextComparer.sh 11/JackCompiler/Square/expect/Main.xml 11/JackCompiler/Square/Main.xml 
./nand2tetris/tools/TextComparer.sh 11/JackCompiler/Square/expect/Square.xml 11/JackCompiler/Square/Square.xml 
./nand2tetris/tools/TextComparer.sh 11/JackCompiler/Square/expect/SquareGame.xml 11/JackCompiler/Square/SquareGame.xml 
./nand2tetris/tools/TextComparer.sh 11/JackCompiler/ExpressionLessSquare/expect/Main.xml 11/JackCompiler/ExpressionLessSquare/Main.xml
./nand2tetris/tools/TextComparer.sh 11/JackCompiler/ExpressionLessSquare/expect/Square.xml 11/JackCompiler/ExpressionLessSquare/Square.xml
./nand2tetris/tools/TextComparer.sh 11/JackCompiler/ExpressionLessSquare/expect/SquareGame.xml 11/JackCompiler/ExpressionLessSquare/SquareGame.xml
./nand2tetris/tools/TextComparer.sh 11/JackCompiler/ArrayTest/expect/Main.xml 11/JackCompiler/ArrayTest/Main.xml

SymbolTableモジュール

シンボルテーブルを管理するためのモジュールです。

CompilationEngineモジュールで利用する関数はSymbolTable.hで下記のように定義しました。symbol_table構造体はtypedefして定義はSymbolTable.c内に隠蔽するようにしてオブジェクトとして使うようにしました。それぞれの実装はSymbolTable.cで行いました。

11/JackCompiler/SymbolTable.h:L4-L21

typedef enum {
    SYMBOL_TABLE_KIND_STATIC = 1,
    SYMBOL_TABLE_KIND_FIELD,
    SYMBOL_TABLE_KIND_ARG,
    SYMBOL_TABLE_KIND_VAR,
    SYMBOL_TABLE_KIND_NONE,
} SymbolTable_Kind;

typedef struct symbol_table * SymbolTable;

SymbolTable SymbolTable_init();
void SymbolTable_startSubroutine(SymbolTable thisObject);
void SymbolTable_define(SymbolTable thisObject, char *name, char *type, SymbolTable_Kind kind);
int SymbolTable_varCount(SymbolTable thisObject, SymbolTable_Kind kind);
SymbolTable_Kind SymbolTable_kindOf(SymbolTable thisObject, char *name);
void SymbolTable_typeOf(SymbolTable thisObject, char *name, char *type);
int SymbolTable_indexOf(SymbolTable thisObject, char *name);
void SymbolTable_delete(SymbolTable thisObject);

またSymbolTable.c内で使う関数はSymbolTablePrivate.hで下記のように定義しSymbolTablePrivate.cで実装しました。

11/JackCompiler/SymbolTablePrivate.h:L8-L23

#define HASH_TABLE_BUCKET_NUM 50

typedef struct hash_table_bucket
{
    char key[JACK_TOKEN_SIZE];
    char type[JACK_TOKEN_SIZE];
    SymbolTable_Kind kind;
    int index;

    struct hash_table_bucket *next;
} HashTableBucket;

void HashTable_init(HashTableBucket *hash_table[]);
bool HashTable_find(HashTableBucket *hash_table[], char *key, HashTableBucket **pp_ret);
void HashTable_set(HashTableBucket *hash_table[], char* key, char *type, SymbolTable_Kind kind, int index);
void HashTable_deleteAll(HashTableBucket *hash_table[]);

シンボルの管理のためにはハッシュテーブルを実装しました。実装にあたっては定本　Ｃプログラマのためのアルゴリズムとデータ構造の 8. ハッシュ法 の 8.3. チェイン法 を参考にしました*2。効率は全く重視していないのでハッシュ関数は適当です。

11/JackCompiler/SymbolTablePrivate.c:L5-L60

int hash(char *s)
{
    int i = 0;
    while (*s) {
        i += *s++;
    }
    return i % HASH_TABLE_BUCKET_NUM;
}

void HashTable_init(HashTableBucket *hash_table[])
{
    for (int i = 0; i < HASH_TABLE_BUCKET_NUM; i++) {
        hash_table[i] = NULL;
    }
}

bool HashTable_find(HashTableBucket *hash_table[], char *key, HashTableBucket **pp_ret)
{
    for (HashTableBucket *p = hash_table[hash(key)]; p != NULL; p = p->next) {
        if (strcmp(key, p->key) == 0) {
            *pp_ret = p;
            return true;
        }
    }
    return false;
}

void HashTable_set(HashTableBucket *hash_table[], char* key, char *type, SymbolTable_Kind kind, int index)
{
    HashTableBucket *p;
    if (! HashTable_find(hash_table, key, &p)) {
        p = (HashTableBucket *)malloc(sizeof(HashTableBucket));
    }

    strcpy(p->key, key);
    strcpy(p->type, type);
    p->kind = kind;
    p->index = index;

    int h = hash(key);
    p->next = hash_table[h];
    hash_table[h] = p;
}

void HashTable_deleteAll(HashTableBucket *hash_table[])
{
    for (int i = 0; i < HASH_TABLE_BUCKET_NUM; i++) {
        HashTableBucket *current = hash_table[i];
        while (current != NULL) {
            HashTableBucket *next = current->next;
            free(current);
            current = next;
        }
        hash_table[i] = NULL;
    }
}

シンボルテーブルは変数の生存期間に応じてクラススコープ用とサブルーチンスコープ用の２つのハッシュテーブルを用意する事で実現しました。

11/JackCompiler/SymbolTable.c:L7-L17

typedef struct symbol_table * SymbolTable;
struct symbol_table
{
    HashTableBucket *class_hash_table[HASH_TABLE_BUCKET_NUM];
    int static_count;
    int field_count;

    HashTableBucket *subroutine_hash_table[HASH_TABLE_BUCKET_NUM];
    int arg_count;
    int var_count;
};

それぞれ実装の詳細はソースコードを参照。

CompilationEngineモジュール

10章で作成した.jackファイルを構文解析して.xmlファイルに出力するためのモジュールです。 SymbolTableモジュールを使って識別子にシンボル情報を付加して.xmlファイル出力するように改造しました。

SymbolTableモジュールを用いた処理を下記に追加しました。

場所 SymbolTableモジュールを用いた処理
CompilationEngine_init SymbolTable_init によるシンボルテーブルの初期化
CompilationEngine_compileClass 終了タイミングで SymbolTable_delete と SymbolTable_init によるシンボルテーブルの初期化
CompilationEngine_compileClassVarDec 変数宣言タイミングで SymbolTable_define によるシンボルテーブルの記録
CompilationEngine_compileSubroutine SymbolTable_startSubroutine によるシンボルテーブル・サブルーチンの初期化
CompilationEngine_compileParameterList 変数宣言タイミングで SymbolTable_define によるシンボルテーブルの記録
CompilationEngine_compileVarDec 変数宣言タイミングで SymbolTable_define によるシンボルテーブルの記録

またidentifierタグの出力関数の引数にシンボル情報を追加してidentifierタグにシンボル情報を含めるようにしました。

11/JackCompiler/CompilationEngine.c:L683-L725

void writeIdentifier(FILE *fp, JackTokenizer tokenizer, char *category, char *status, SymbolTable symbolTable)
{
    char token[JACK_TOKEN_SIZE];
    JackTokenizer_identifier(tokenizer, token);
    writeIdentifierByToken(fp, token, category, status, symbolTable);
}

// ...(省略)...

void writeIdentifierByToken(FILE *fp, char *token, char *category, char *status, SymbolTable symbolTable)
{
    fprintf(fp, "<identifier category=\"%s\" status=\"%s\"", category, status);
    if (symbolTable != NULL) {
        char kindStr[JACK_TOKEN_SIZE];
        getIdentifierKindString(symbolTable, token, kindStr);

        char typeStr[JACK_TOKEN_SIZE];
        SymbolTable_typeOf(symbolTable, token, typeStr);
        fprintf(fp, " kind=\"%s\" type=\"%s\" index=\"%d\"", kindStr, typeStr, SymbolTable_indexOf(symbolTable, token));
    }
    fprintf(fp, "> %s </identifier>\n", token);
}

テストの正解データについては提供されていないため目視でチェックした結果データを元にpatchを作成し自動テストに組み込みました。

11/JackCompiler/test

  • ArrayTest.patch
  • ExpressionLessSquare.patch
  • Square.patch

test11.sh:L6

patch -p1 -d 11/JackCompiler/Square/expect < 11/JackCompiler/test/Square.patch

patchの作成は下記で行いました。（xmlのインデントが異なるため-wで空白を無視しています）

diff -u -w -r expect expect_fix > ArrayTest.patch

コード生成

ここではバーチャルマシンへの標準マッピング仕様に基づき各構文をコードに変換し.vmファイルへ出力するようにしていきました。 段階的に対応構文を増やしていくテストプログラムが用意されているのでそれにしたがって実装を進めていきました。

最小限の構文要素

ソースコードは11/JackCompiler2/です。

ここでは下記を行いました。

  • コンパイラの出力を構文解析結果.xmlファイルからバーチャルマシンコード.vmファイルに変更
  • 最小限の構文要素に対応（定数値の算術式、do文、return文）
  • テストコードの Seven がコンパイルでき動作確認できるところを目指す

下記で使えます。

test11.sh:L41-L53

cp -r ./nand2tetris/projects/11/Seven 11/JackCompiler2/ && \
cp -r ./nand2tetris/tools/OS/* 11/JackCompiler2/Seven/

cd 11/JackCompiler2/

clang --std=c11 -Wall -Wextra -o JackCompiler main.c JackTokenizer.c JackTokenizerPrivate.c SymbolTable.c SymbolTablePrivate.c VMWriter.c CompilationEngine.c

./JackCompiler Seven

cd -

# ./nand2tetris/tools/VMEmulator.sh
#   11/JackCompiler2/Seven
  • 動かすためにOS提供関数の./nand2tetris/tools/OS/以下のファイルを使っています。
  • テストは自動実行できないので手動で確認する必要があります*3。

実行するとScreenエリアに 7 と表示されます。

main.c (JackCompilerモジュール)

コンパイラの出力を構文解析結果.xmlファイルからバーチャルマシンコード.vmファイルに変更しました。

差分は下記の通りです。

$ diff 11/JackCompiler/main.c 11/JackCompiler2/main.c 
8c8
< #define XML_FILENAME_MAX_LENGTH (JACK_FILENAME_MAX_LENGTH - 1)  // length('.jack') - length('.xml') = 1
---
> #define VM_FILENAME_MAX_LENGTH (JACK_FILENAME_MAX_LENGTH - 2)  // length('.jack') - length('.vm') = 2
11,13c11,13
< int analyzeByJackDir(DIR *dpJack, char *jackDirName);
< int analyzeByJackFile(char *jackFileName);
< int analyze(char *xmlFilePath, char *jackFilePath);
---
> int compileByJackDir(DIR *dpJack, char *jackDirName);
> int compileByJackFile(char *jackFileName);
> int compile(char *vmFilePath, char *jackFilePath);
16,17c16,17
< void createXmlFilePathFromDirName(char *jackDirName, char *jackFileName, char *xmlFilePath);
< void createXmlFilePathFromJackFileName(char *jackFileName, char *xmlFilePath);
---
> void createVmFilePathFromDirName(char *jackDirName, char *jackFileName, char *vmFilePath);
> void createVmFilePathFromJackFileName(char *jackFileName, char *vmFilePath);
37c37
<         int exitNo = analyzeByJackDir(dpJack, jackFileOrDirName);
---
>         int exitNo = compileByJackDir(dpJack, jackFileOrDirName);
41c41
<         return analyzeByJackFile(jackFileOrDirName);
---
>         return compileByJackFile(jackFileOrDirName);
50c50
< int analyzeByJackDir(DIR *dpJack, char *jackDirName)
---
> int compileByJackDir(DIR *dpJack, char *jackDirName)
53c53
<     char xmlFilePath[JACK_DIRNAME_MAX_LENGTH + XML_FILENAME_MAX_LENGTH + 1];
---
>     char vmFilePath[JACK_DIRNAME_MAX_LENGTH + VM_FILENAME_MAX_LENGTH + 1];
88,89c88,89
<         createXmlFilePathFromDirName(jackDirName, jackFileName, xmlFilePath);
<         if (analyze(xmlFilePath, jackFilePath) != 0) {
---
>         createVmFilePathFromDirName(jackDirName, jackFileName, vmFilePath);
>         if (compile(vmFilePath, jackFilePath) != 0) {
97c97
< int analyzeByJackFile(char *jackFileName)
---
> int compileByJackFile(char *jackFileName)
99c99
<     char xmlFilePath[XML_FILENAME_MAX_LENGTH];
---
>     char vmFilePath[VM_FILENAME_MAX_LENGTH];
117,118c117,118
<     createXmlFilePathFromJackFileName(jackFileName, xmlFilePath);
<     return analyze(xmlFilePath, jackFileName);
---
>     createVmFilePathFromJackFileName(jackFileName, vmFilePath);
>     return compile(vmFilePath, jackFileName);
121c121
< int analyze(char *xmlFilePath, char *jackFilePath)
---
> int compile(char *vmFilePath, char *jackFilePath)
123c123
<     FILE *fpJack, *fpXml;
---
>     FILE *fpJack, *fpVm;
131,132c131,132
<     if ((fpXml = fopen(xmlFilePath, "w")) == NULL) {
<         fprintf(stderr, "Error: xml file not open (%s)\n", xmlFilePath);
---
>     if ((fpVm = fopen(vmFilePath, "w")) == NULL) {
>         fprintf(stderr, "Error: vm file not open (%s)\n", vmFilePath);
137c137
<     compilationEngine = CompilationEngine_init(fpJack, fpXml);
---
>     compilationEngine = CompilationEngine_init(fpJack, fpVm);
140c140
<     fclose(fpXml);
---
>     fclose(fpVm);
172c172
< void createXmlFilePathFromDirName(char *jackDirName, char *jackFileName, char *xmlFilePath)
---
> void createVmFilePathFromDirName(char *jackDirName, char *jackFileName, char *vmFilePath)
174,178c174,178
<     // xmlFilePath is {jackDirName}/{jackFileName} - ".jack" + ".xml"
<     strcpy(xmlFilePath, jackDirName);
<     strcat(xmlFilePath, "/");
<     strncat(xmlFilePath, jackFileName, strlen(jackFileName) - strlen(".jack"));
<     strcat(xmlFilePath, ".xml");
---
>     // vmFilePath is {jackDirName}/{jackFileName} - ".jack" + ".vm"
>     strcpy(vmFilePath, jackDirName);
>     strcat(vmFilePath, "/");
>     strncat(vmFilePath, jackFileName, strlen(jackFileName) - strlen(".jack"));
>     strcat(vmFilePath, ".vm");
181c181
< void createXmlFilePathFromJackFileName(char *jackFileName, char *xmlFilePath)
---
> void createVmFilePathFromJackFileName(char *jackFileName, char *vmFilePath)
183,184c183,184
<     // XmlFilePath is {jackFileName} - ".jack" + ".xml"
<     size_t xmlFileNamePrefixLength = strlen(jackFileName) - strlen(".jack");
---
>     // VmFilePath is {jackFileName} - ".jack" + ".vm"
>     size_t vmFileNamePrefixLength = strlen(jackFileName) - strlen(".jack");
186,188c186,188
<     strncpy(xmlFilePath, jackFileName, xmlFileNamePrefixLength);
<     xmlFilePath[xmlFileNamePrefixLength] = '\0';
<     strcat(xmlFilePath, ".xml");
---
>     strncpy(vmFilePath, jackFileName, vmFileNamePrefixLength);
>     vmFilePath[vmFileNamePrefixLength] = '\0';
>     strcat(vmFilePath, ".vm");

VMWriterモジュール

VMコマンドの構文に従いVMコマンドをファイルに書き出すモジュールです。

CompilationEngineモジュールで利用する関数はVMWriter.hで下記のように定義しました。vm_writer構造体はtypedefして定義はVMWriter.c内に隠蔽するようにしてオブジェクトとして使うようにしました。それぞれの実装はVMWriter.cで行いました。

11/JackCompiler2/VMWriter.h:L4-L21

typedef enum {
    VM_WRITER_SEGMENT_CONST = 1,
    VM_WRITER_SEGMENT_ARG,
    VM_WRITER_SEGMENT_LOCAL,
    VM_WRITER_SEGMENT_STATIC,
    VM_WRITER_SEGMENT_THIS,
    VM_WRITER_SEGMENT_THAT,
    VM_WRITER_SEGMENT_POINTER,
    VM_WRITER_SEGMENT_TEMP,
} VMWriter_Segment;

typedef enum {
    VM_WRITER_COMMAND_ADD = 1,
    VM_WRITER_COMMAND_SUB,
    VM_WRITER_COMMAND_NEG,
    VM_WRITER_COMMAND_EQ,
    VM_WRITER_COMMAND_GT,
    VM_WRITER_COMMAND_LT,
    VM_WRITER_COMMAND_AND,
    VM_WRITER_COMMAND_OR,
    VM_WRITER_COMMAND_NOT,
} VMWriter_Command;

typedef struct vm_writer * WMWriter;

WMWriter WMWriter_init(FILE *fpVm);
void VMWriter_writePush(WMWriter thisObject, VMWriter_Segment segment, int index);
void VMWriter_writePop(WMWriter thisObject, VMWriter_Segment segment, int index);
void VMWriter_writeArithmetic(WMWriter thisObject, VMWriter_Command command);
void VMWriter_writeLabel(WMWriter thisObject, char *label);
void VMWriter_writeGoto(WMWriter thisObject, char *label);
void VMWriter_writeIf(WMWriter thisObject, char *label);
void VMWriter_writeCall(WMWriter thisObject, char *name, int nArgs);
void VMWriter_writeFunction(WMWriter thisObject, char *name, int nLocals);
void VMWriter_writeReturn(WMWriter thisObject);
void VMWriter_close(WMWriter thisObject);

実装はfprintfでファイルに書き出しているだけです。

11/JackCompiler2/VMWriter.c

CompilationEngineモジュール

以降の対応のためにXML出力向けに共通化していた部分をVM出力しやすくリファクタリングしました。

11/JackCompiler2/CompilationEngine.c

CompilationEngine_compileSubroutine

サブルーチンはローカル変数の数を 0 で決め打ちしてテストを動かすための最小限の実装にしました。

11/JackCompiler2/CompilationEngine.c:L118-L179

void CompilationEngine_compileSubroutine(CompilationEngine thisObject)
{
    // ...(省略)...

    char functionName[JACK_TOKEN_SIZE];
    sprintf(functionName, "%s.%s", thisObject->className, subroutineName);
    VMWriter_writeFunction(thisObject->vmWriter, functionName, 0 /* FIXME */);

    // ...(省略)...
}

CompilationEngine_compileDo

  • サブルーチン名は クラス名.メソッド名 の形式のみ対応しました。
  • do文は戻り値を使わないのでtempセグメントに捨てるようにしました。

11/JackCompiler2/CompilationEngine.c:L284-L342

void CompilationEngine_compileDo(CompilationEngine thisObject)
{
    // ...(省略)...

    // subroutineName | (className | varName)
    char token[JACK_TOKEN_SIZE];
    JackTokenizer_identifier(thisObject->tokenizer, token);
    JackTokenizer_advance(thisObject->tokenizer);

    sprintf(functionName, "%s", token);

    // '(' or '.'
    JackTokenizer_symbol(thisObject->tokenizer, symbol);
    if (isSymbolToken(thisObject, ".")) {
        // (className | varName) used
        // ...(省略)...

        // subroutineName (subroutine used)
        JackTokenizer_identifier(thisObject->tokenizer, identifier);
        JackTokenizer_advance(thisObject->tokenizer);

        sprintf(functionName, "%s%s%s", functionName, symbol, identifier);

        // '('
        JackTokenizer_symbol(thisObject->tokenizer, symbol);
    } else {
        // token is subroutineName (subroutine used)
    }
    JackTokenizer_advance(thisObject->tokenizer);

    int nArgs = CompilationEngine_compileExpressionList(thisObject);

    // ...(省略)...

    VMWriter_writeCall(thisObject->vmWriter, functionName, nArgs);
    VMWriter_writePop(thisObject->vmWriter, VM_WRITER_SEGMENT_TEMP, 0);
}

CompilationEngine_compileReturn

return文はvoidのみ対応として戻り値を 0 固定にしました。

11/JackCompiler2/CompilationEngine.c:L416-L436

void CompilationEngine_compileReturn(CompilationEngine thisObject)
{
    // ...(省略)...

    VMWriter_writePush(thisObject->vmWriter, VM_WRITER_SEGMENT_CONST, 0);  /* FIXME */
    VMWriter_writeReturn(thisObject->vmWriter);
}

CompilationEngine_compileExpression

  • 加算と乗算のみ対応しました。乗算はOSが提供するMath.multiplyを呼び出すようにしました。
  • 演算が逆ポーランドの順番になるようにしました。

11/JackCompiler2/CompilationEngine.c:L488-L510

void CompilationEngine_compileExpression(CompilationEngine thisObject)
{
    char symbol[JACK_TOKEN_SIZE];

    CompilationEngine_compileTerm(thisObject);

    while (inSymbolListToken(thisObject, "+", "-", "*",  "/", "&", "|", "<", ">", "=", NULL)) {
        // op
        JackTokenizer_symbol(thisObject->tokenizer, symbol);
        JackTokenizer_advance(thisObject->tokenizer);

        CompilationEngine_compileTerm(thisObject);

        // op is after terms because it is Reverse Polish Notation (RPN)
        // term1 term2 op (ex. 1+(2*3) => 1(2*3)+ => 1(23*)+)
        if (strcmp(symbol, "+") == 0) {
            VMWriter_writeArithmetic(thisObject->vmWriter, VM_WRITER_COMMAND_ADD);
        }
        if (strcmp(symbol, "*") == 0) {
            VMWriter_writeCall(thisObject->vmWriter, "Math.multiply", 2);
        }
    }
}

CompilationEngine_compileTerm

数値のみ対応しました。

11/JackCompiler2/CompilationEngine.c:L515-L607

void CompilationEngine_compileTerm(CompilationEngine thisObject)
{
    // ...(省略)...

    if (JackTokenizer_tokenType(thisObject->tokenizer) == JACK_TOKENIZER_TOKEN_TYPE_INT_CONST) {
        // integerConstant
        JackTokenizer_intVal(thisObject->tokenizer, &intVal);
        JackTokenizer_advance(thisObject->tokenizer);

        VMWriter_writePush(thisObject->vmWriter, VM_WRITER_SEGMENT_CONST, intVal);
    } else if (JackTokenizer_tokenType(thisObject->tokenizer) == JACK_TOKENIZER_TOKEN_TYPE_STRING_CONST) {
        // ...(省略)...
    } else {    // varName | varName '[' expression ']' | subroutineCall
        // ...(省略)...
    }
}

全ての手続き的要素

ソースコードは11/JackCompiler3/です。

ここでは下記を行いました。

  • 全ての手続き的要素に対応（配列とメソッド呼び出しを除く式、ファンクション、文）
  • テストコードの ConvertToBin がコンパイルでき動作確認できるところを目指す

下記で使えます。

test11.sh:L55-L72

cp -r ./nand2tetris/projects/11/Seven 11/JackCompiler3/ && \
cp -r ./nand2tetris/tools/OS/* 11/JackCompiler3/Seven/

cp -r ./nand2tetris/projects/11/ConvertToBin 11/JackCompiler3/ && \
cp -r ./nand2tetris/tools/OS/* 11/JackCompiler3/ConvertToBin/

cd 11/JackCompiler3/

clang --std=c11 -Wall -Wextra -o JackCompiler main.c JackTokenizer.c JackTokenizerPrivate.c SymbolTable.c SymbolTablePrivate.c VMWriter.c CompilationEngine.c

./JackCompiler Seven
./JackCompiler ConvertToBin

cd -

# ./nand2tetris/tools/VMEmulator.sh
#   11/JackCompiler3/Seven
#   11/JackCompiler3/ConvertToBin
  • 動かすためにOS提供関数の./nand2tetris/tools/OS/以下のファイルを使っています。
  • テストは自動実行できないので手動で確認する必要があります*4。

RAM8000番地に数値を設定して実行すると2進数に変換され8001番地以降に設定されます。 (今回は221をセットしたので0xDD = 0000000011011101がセットされた)

CompilationEngineモジュール

CompilationEngine_compileSubroutine

サブルーチンのローカル変数の数に対応しました。

11/JackCompiler3/CompilationEngine.c:L122-L188

void CompilationEngine_compileSubroutine(CompilationEngine thisObject)
{
    // ...(省略)...

    // subroutineBody
    {
        // ...(省略)...

        VMWriter_writeFunction(
            thisObject->vmWriter,
            functionName,
            SymbolTable_varCount(thisObject->symbolTable, SYMBOL_TABLE_KIND_VAR)
        );

        // ...(省略)...
    }
}

CompilationEngine_compileLet

変数への代入に対応しました。

11/JackCompiler3/CompilationEngine.c:L354-L396

void CompilationEngine_compileLet(CompilationEngine thisObject)
{
    // ...(省略)...

    VMWriter_writePop(
        thisObject->vmWriter,
        kind == SYMBOL_TABLE_KIND_VAR ? VM_WRITER_SEGMENT_LOCAL : VM_WRITER_SEGMENT_ARG,
        SymbolTable_indexOf(thisObject->symbolTable, varName)
    );

    // ...(省略)...
}

CompilationEngine_compileWhile

while文に対応しました。

11/JackCompiler3/CompilationEngine.c:L399-L441

void CompilationEngine_compileWhile(CompilationEngine thisObject)
{
    JackTokenizer_Keyword keyword;
    char symbol[JACK_TOKEN_SIZE];

    // 'while'
    keyword = JackTokenizer_keyword(thisObject->tokenizer);
    JackTokenizer_advance(thisObject->tokenizer);

    char labelExp[JACK_TOKEN_SIZE], labelEnd[JACK_TOKEN_SIZE];
    sprintf(labelExp, "%s$$$WHILE_EXP.%d", thisObject->className, thisObject->whileLabelCount);
    sprintf(labelEnd, "%s$$$WHILE_END.%d", thisObject->className, thisObject->whileLabelCount);
    thisObject->whileLabelCount++;

    VMWriter_writeLabel(thisObject->vmWriter, labelExp);

    // '('
    JackTokenizer_symbol(thisObject->tokenizer, symbol);
    JackTokenizer_advance(thisObject->tokenizer);

    CompilationEngine_compileExpression(thisObject);

    // ')'
    JackTokenizer_symbol(thisObject->tokenizer, symbol);
    JackTokenizer_advance(thisObject->tokenizer);

    VMWriter_writeArithmetic(thisObject->vmWriter, VM_WRITER_COMMAND_NOT);
    VMWriter_writeIf(thisObject->vmWriter, labelEnd);

    // '{'
    JackTokenizer_symbol(thisObject->tokenizer, symbol);
    JackTokenizer_advance(thisObject->tokenizer);

    CompilationEngine_compileStatements(thisObject);

    VMWriter_writeGoto(thisObject->vmWriter, labelExp);

    // '}'
    JackTokenizer_symbol(thisObject->tokenizer, symbol);
    JackTokenizer_advance(thisObject->tokenizer);

    VMWriter_writeLabel(thisObject->vmWriter, labelEnd);
}

CompilationEngine_compileReturn

値のreturnがない場合のみ 0 を戻り値にするようにしました。

11/JackCompiler3/CompilationEngine.c:L444-L465

void CompilationEngine_compileReturn(CompilationEngine thisObject)
{
    // ...(省略)...

    // expression or ';'
    if (! isSymbolToken(thisObject, ";")) {
        CompilationEngine_compileExpression(thisObject);
    } else {
        VMWriter_writePush(thisObject->vmWriter, VM_WRITER_SEGMENT_CONST, 0);
    }

    // ...(省略)...

    VMWriter_writeReturn(thisObject->vmWriter);
}

CompilationEngine_compileIf

if文に対応しました。

11/JackCompiler3/CompilationEngine.c:L468-L528

void CompilationEngine_compileIf(CompilationEngine thisObject)
{
    // ...(省略)...

    char labelTrue[JACK_TOKEN_SIZE], labelFalse[JACK_TOKEN_SIZE], labelEnd[JACK_TOKEN_SIZE];
    sprintf(labelTrue, "%s$$$IF_TRUE.%d", thisObject->className, thisObject->ifLabelCount);
    sprintf(labelFalse, "%s$$$IF_FALSE.%d", thisObject->className, thisObject->ifLabelCount);
    sprintf(labelEnd, "%s$$$IF_END.%d", thisObject->className, thisObject->ifLabelCount);
    thisObject->ifLabelCount++;

    // '('
    JackTokenizer_symbol(thisObject->tokenizer, symbol);
    JackTokenizer_advance(thisObject->tokenizer);

    CompilationEngine_compileExpression(thisObject);

    // ')'
    JackTokenizer_symbol(thisObject->tokenizer, symbol);
    JackTokenizer_advance(thisObject->tokenizer);

    VMWriter_writeIf(thisObject->vmWriter, labelTrue);
    VMWriter_writeGoto(thisObject->vmWriter, labelFalse);
    VMWriter_writeLabel(thisObject->vmWriter, labelTrue);

    // '{'
    JackTokenizer_symbol(thisObject->tokenizer, symbol);
    JackTokenizer_advance(thisObject->tokenizer);

    CompilationEngine_compileStatements(thisObject);

    // '}'
    JackTokenizer_symbol(thisObject->tokenizer, symbol);
    JackTokenizer_advance(thisObject->tokenizer);

    VMWriter_writeGoto(thisObject->vmWriter, labelEnd);
    VMWriter_writeLabel(thisObject->vmWriter, labelFalse);

    // 'else' or not
    if (isKeywordToken(thisObject, JACK_TOKENIZER_KEYWORD_ELSE)) {
        // ...(省略)...
    }

    VMWriter_writeLabel(thisObject->vmWriter, labelEnd);
}

CompilationEngine_compileExpression

全ての演算子に対応しました。

11/JackCompiler3/CompilationEngine.c:L532-L575

void CompilationEngine_compileExpression(CompilationEngine thisObject)
{
    // ...(省略)...
        if (strcmp(symbol, "+") == 0) {
            VMWriter_writeArithmetic(thisObject->vmWriter, VM_WRITER_COMMAND_ADD);
        }
        if (strcmp(symbol, "-") == 0) {
            VMWriter_writeArithmetic(thisObject->vmWriter, VM_WRITER_COMMAND_SUB);
        }
        if (strcmp(symbol, "*") == 0) {
            VMWriter_writeCall(thisObject->vmWriter, "Math.multiply", 2);
        }
        if (strcmp(symbol, "/") == 0) {
            VMWriter_writeCall(thisObject->vmWriter, "Math.divide", 2);
        }
        if (strcmp(symbol, "&") == 0) {
            VMWriter_writeArithmetic(thisObject->vmWriter, VM_WRITER_COMMAND_AND);
        }
        if (strcmp(symbol, "|") == 0) {
            VMWriter_writeArithmetic(thisObject->vmWriter, VM_WRITER_COMMAND_OR);
        }
        if (strcmp(symbol, "<") == 0) {
            VMWriter_writeArithmetic(thisObject->vmWriter, VM_WRITER_COMMAND_LT);
        }
        if (strcmp(symbol, ">") == 0) {
            VMWriter_writeArithmetic(thisObject->vmWriter, VM_WRITER_COMMAND_GT);
        }
        if (strcmp(symbol, "=") == 0) {
            VMWriter_writeArithmetic(thisObject->vmWriter, VM_WRITER_COMMAND_EQ);
        }
    // ...(省略)...
}

CompilationEngine_compileTerm

  • TRUE, FALSE, NULLに対応しました
  • 単項演算の -, ~に対応しました
  • サブルーチン呼び出しに対応しました
  • 変数参照（ローカル変数、パラメータ変数）に対応しました

11/JackCompiler3/CompilationEngine.c:L580-L694

void CompilationEngine_compileTerm(CompilationEngine thisObject)
{
    // ...(省略)...

    if (JackTokenizer_tokenType(thisObject->tokenizer) == JACK_TOKENIZER_TOKEN_TYPE_INT_CONST) {
        // ...(省略)...
    } else if (JackTokenizer_tokenType(thisObject->tokenizer) == JACK_TOKENIZER_TOKEN_TYPE_STRING_CONST) {
        // ...(省略)...
    } else if (JackTokenizer_tokenType(thisObject->tokenizer) == JACK_TOKENIZER_TOKEN_TYPE_KEYWORD) {
         // ...(省略)...

        if (keyword == JACK_TOKENIZER_KEYWORD_TRUE) {
            VMWriter_writePush(thisObject->vmWriter, VM_WRITER_SEGMENT_CONST, 0);
            VMWriter_writeArithmetic(thisObject->vmWriter, VM_WRITER_COMMAND_NOT);
        }
        if (keyword == JACK_TOKENIZER_KEYWORD_FALSE || keyword == JACK_TOKENIZER_KEYWORD_NULL) {
            VMWriter_writePush(thisObject->vmWriter, VM_WRITER_SEGMENT_CONST, 0);
        }
    } else if (isSymbolToken(thisObject, "(")) {    // '(' expression ')'
        // ...(省略)...
    } else if (inSymbolListToken(thisObject, "-", "~", NULL)) { // unaryOp term
        // ...(省略)...

        VMWriter_writeArithmetic(
            thisObject->vmWriter,
            strcmp(symbol, "-") == 0 ? VM_WRITER_COMMAND_NEG : VM_WRITER_COMMAND_NOT
        );
    } else {    // varName | varName '[' expression ']' | subroutineCall
        // varName | subroutineName | className (used)
        char token[JACK_TOKEN_SIZE];
        JackTokenizer_identifier(thisObject->tokenizer, token);
        SymbolTable_Kind kind = SymbolTable_kindOf(thisObject->symbolTable, token);
        if (kind == SYMBOL_TABLE_KIND_NONE) {
            // token is className
        }
        JackTokenizer_advance(thisObject->tokenizer);

        // '[' or '(' or '.' or not
        if (isSymbolToken(thisObject, "[")) {
            // token is Array of varName (varName[])

            JackTokenizer_symbol(thisObject->tokenizer, symbol);
            JackTokenizer_advance(thisObject->tokenizer);

            CompilationEngine_compileExpression(thisObject);

            // ']'
            JackTokenizer_symbol(thisObject->tokenizer, symbol);
            JackTokenizer_advance(thisObject->tokenizer);
        } else if (inSymbolListToken(thisObject, "(", ".", NULL)) {
            char functionName[JACK_TOKEN_SIZE];
            sprintf(functionName, "%s", token);
            if (isSymbolToken(thisObject, "(")) {
                // token is subroutineName (subroutine used)
            } else {    // "."
                // token is (className | varName)
            }

            // '(' or '.'
            JackTokenizer_symbol(thisObject->tokenizer, symbol);
            if (isSymbolToken(thisObject, ".")) {
                JackTokenizer_advance(thisObject->tokenizer);

                // subroutineName (subroutine used)
                JackTokenizer_identifier(thisObject->tokenizer, identifier);
                JackTokenizer_advance(thisObject->tokenizer);

                sprintf(functionName, "%s%s%s", functionName, symbol, identifier);

                // '('
                JackTokenizer_symbol(thisObject->tokenizer, symbol);
            }
            JackTokenizer_advance(thisObject->tokenizer);

            int nArgs = CompilationEngine_compileExpressionList(thisObject);

            // ')'
            JackTokenizer_symbol(thisObject->tokenizer, symbol);
            JackTokenizer_advance(thisObject->tokenizer);

            VMWriter_writeCall(thisObject->vmWriter, functionName, nArgs);
        } else {
            // token is varName
            VMWriter_writePush(
                thisObject->vmWriter,
                kind == SYMBOL_TABLE_KIND_VAR ? VM_WRITER_SEGMENT_LOCAL : VM_WRITER_SEGMENT_ARG,
                SymbolTable_indexOf(thisObject->symbolTable, token)
            );
        }
    }
}

オブジェクト指向の構成要素

ソースコードは11/JackCompiler4/です。

ここでは下記を行いました。

  • オブジェクト指向の構成要素に対応（コンストラクタ、メソッド、フィールド、メソッド呼び出しを含む式）
  • テストコードの Square がコンパイルでき動作確認できるところを目指す

下記で使えます。

test11.sh:L74-L96

cp -r ./nand2tetris/projects/11/Seven 11/JackCompiler4/ && \
cp -r ./nand2tetris/tools/OS/* 11/JackCompiler4/Seven/

cp -r ./nand2tetris/projects/11/ConvertToBin 11/JackCompiler4/ && \
cp -r ./nand2tetris/tools/OS/* 11/JackCompiler4/ConvertToBin/

cp -r ./nand2tetris/projects/11/Square 11/JackCompiler4/ && \
cp -r ./nand2tetris/tools/OS/* 11/JackCompiler4/Square/

cd 11/JackCompiler4/

clang --std=c11 -Wall -Wextra -o JackCompiler main.c JackTokenizer.c JackTokenizerPrivate.c SymbolTable.c SymbolTablePrivate.c VMWriter.c CompilationEngine.c

./JackCompiler Seven
./JackCompiler ConvertToBin
./JackCompiler Square

cd -

# ./nand2tetris/tools/VMEmulator.sh
#   11/JackCompiler4/Seven
#   11/JackCompiler4/ConvertToBin
#   11/JackCompiler4/Square
  • 動かすためにOS提供関数の./nand2tetris/tools/OS/以下のファイルを使っています。
  • テストは自動実行できないので手動で確認する必要があります*5。

実行するとScreenエリアに黒い四角が表示されて上下左右に動かすことや大きさを変えることができます。

CompilationEngineモジュール

CompilationEngine_compileSubroutine

  • コンストラクタの場合は Memory.allocでフィールド領域を確保しpointerセグメントの0番目(this)にセットしました
  • メソッドの場合は第一引数に自身のオブジェクトが指定されている前提にしました

11/JackCompiler4/CompilationEngine.c:L121-L203

void CompilationEngine_compileSubroutine(CompilationEngine thisObject)
{
    // ...(省略)...

    CompilationEngine_compileParameterList(thisObject);

    if (functionKind == JACK_TOKENIZER_KEYWORD_METHOD) {
        // b.mult(5) => mult(b,5)
        // it is ok because "this" is keyword, not verName
        SymbolTable_define(thisObject->symbolTable, "this", thisObject->className, SYMBOL_TABLE_KIND_ARG);
    }

    // ...(省略)...

    // subroutineBody
    {
        // '{'
        JackTokenizer_symbol(thisObject->tokenizer, symbol);
        JackTokenizer_advance(thisObject->tokenizer);

        // 'var' or statements or '}'
        while (isKeywordToken(thisObject, JACK_TOKENIZER_KEYWORD_VAR)) {
            CompilationEngine_compileVarDec(thisObject);
        }
        VMWriter_writeFunction(
            thisObject->vmWriter,
            functionName,
            SymbolTable_varCount(thisObject->symbolTable, SYMBOL_TABLE_KIND_VAR)
        );
        if (functionKind == JACK_TOKENIZER_KEYWORD_CONSTRUCTION) {
            int fieldCount = SymbolTable_varCount(thisObject->symbolTable, SYMBOL_TABLE_KIND_FIELD);
            VMWriter_writePush(thisObject->vmWriter, VM_WRITER_SEGMENT_CONST, fieldCount);
            VMWriter_writeCall(thisObject->vmWriter, "Memory.alloc", 1);
            VMWriter_writePop(thisObject->vmWriter, VM_WRITER_SEGMENT_POINTER, 0);
        }
        if (functionKind == JACK_TOKENIZER_KEYWORD_METHOD) {
            VMWriter_writePush(thisObject->vmWriter, VM_WRITER_SEGMENT_ARG, 0);
            VMWriter_writePop(thisObject->vmWriter, VM_WRITER_SEGMENT_POINTER, 0);
        }

        // statements or '}'
        if (! isSymbolToken(thisObject, "}")) {
            CompilationEngine_compileStatements(thisObject);
        }

        // '}'
        JackTokenizer_symbol(thisObject->tokenizer, symbol);
        JackTokenizer_advance(thisObject->tokenizer);
    }
}

CompilationEngine_compileDo

  • フィールド変数経由でのサブルーチン呼び出しに対応しました
  • メソッド呼び出しの場合は第１引数にオブジェクトを指定するようにしました

11/JackCompiler4/CompilationEngine.c:L308-L391

void CompilationEngine_compileDo(CompilationEngine thisObject)
{
    // ...(省略)...

    // '(' or '.'
    JackTokenizer_symbol(thisObject->tokenizer, symbol);
    if (isSymbolToken(thisObject, ".")) {
        // (className | varName) used
        SymbolTable_Kind functionKind = SymbolTable_kindOf(thisObject->symbolTable, token);
        JackTokenizer_advance(thisObject->tokenizer);

        // subroutineName (subroutine used)
        JackTokenizer_identifier(thisObject->tokenizer, identifier);
        JackTokenizer_advance(thisObject->tokenizer);

        if (functionKind != SYMBOL_TABLE_KIND_NONE) {
            // token is varName
            char className[JACK_TOKEN_SIZE];
            SymbolTable_typeOf(thisObject->symbolTable, token, className);
            sprintf(functionName, "%s.%s", className, identifier);

            VMWriter_Segment segment;
            switch (SymbolTable_kindOf(thisObject->symbolTable, token))
            {
            case SYMBOL_TABLE_KIND_VAR:
                segment = VM_WRITER_SEGMENT_LOCAL;
                break;
            case SYMBOL_TABLE_KIND_ARG:
                segment = VM_WRITER_SEGMENT_ARG;
                break;
            case SYMBOL_TABLE_KIND_FIELD:
            default:
                segment = VM_WRITER_SEGMENT_THIS;
                break;
            }
            VMWriter_writePush(
                thisObject->vmWriter,
                segment,
                SymbolTable_indexOf(thisObject->symbolTable, token)
            );
            nArgs++;
        } else {
            // token is className
            sprintf(functionName, "%s.%s", token, identifier);
        }

        // '('
        JackTokenizer_symbol(thisObject->tokenizer, symbol);
    } else {
        // token is subroutineName (subroutine used)
        sprintf(functionName, "%s.%s", thisObject->className, token);

        VMWriter_writePush(thisObject->vmWriter, VM_WRITER_SEGMENT_POINTER, 0);
        nArgs++;
    }
    JackTokenizer_advance(thisObject->tokenizer);

    nArgs += CompilationEngine_compileExpressionList(thisObject);

    // ...(省略)...

    VMWriter_writeCall(thisObject->vmWriter, functionName, nArgs);
    VMWriter_writePop(thisObject->vmWriter, VM_WRITER_SEGMENT_TEMP, 0);
}

CompilationEngine_compileLet

フィールド変数への代入に対応しました

11/JackCompiler4/CompilationEngine.c:L394-L450

void CompilationEngine_compileLet(CompilationEngine thisObject)
{
    // ...(省略)...

    CompilationEngine_compileExpression(thisObject);

    VMWriter_Segment segment;
    switch (kind)
    {
    case SYMBOL_TABLE_KIND_VAR:
        segment = VM_WRITER_SEGMENT_LOCAL;
        break;
    case SYMBOL_TABLE_KIND_ARG:
        segment = VM_WRITER_SEGMENT_ARG;
        break;
    case SYMBOL_TABLE_KIND_FIELD:
    default:
        segment = VM_WRITER_SEGMENT_THIS;
        break;
    }
    VMWriter_writePop(
        thisObject->vmWriter,
        segment,
        SymbolTable_indexOf(thisObject->symbolTable, varName)
    );

    // ...(省略)...
}

CompilationEngine_compileTerm

  • thisに対応しました
  • フィールド変数に対応しました
  • メソッド呼び出しの場合は第１引数にオブジェクトを指定するようにしました

11/JackCompiler4/CompilationEngine.c:L634-L796

void CompilationEngine_compileTerm(CompilationEngine thisObject)
{
    // ...(省略)...

    if (JackTokenizer_tokenType(thisObject->tokenizer) == JACK_TOKENIZER_TOKEN_TYPE_INT_CONST) {
        // ...(省略)...
    } else if (JackTokenizer_tokenType(thisObject->tokenizer) == JACK_TOKENIZER_TOKEN_TYPE_STRING_CONST) {
        // ...(省略)...
    } else if (JackTokenizer_tokenType(thisObject->tokenizer) == JACK_TOKENIZER_TOKEN_TYPE_KEYWORD) {
        // ...(省略)...
        if (keyword == JACK_TOKENIZER_KEYWORD_THIS) {
            VMWriter_writePush(thisObject->vmWriter, VM_WRITER_SEGMENT_POINTER, 0);
        }
    } else if (isSymbolToken(thisObject, "(")) {    // '(' expression ')'
        // ...(省略)...
    } else if (inSymbolListToken(thisObject, "-", "~", NULL)) { // unaryOp term
        // ...(省略)...
    } else {    // varName | varName '[' expression ']' | subroutineCall
        // ...(省略)...

        // '[' or '(' or '.' or not
        if (isSymbolToken(thisObject, "[")) {
            // ...(省略)...
        } else if (inSymbolListToken(thisObject, "(", ".", NULL)) {
            char functionName[JACK_TOKEN_SIZE];
            int nArgs = 0;

            // '(' or '.'
            JackTokenizer_symbol(thisObject->tokenizer, symbol);
            if (isSymbolToken(thisObject, ".")) {
                // token is (className | varName)
                JackTokenizer_advance(thisObject->tokenizer);

                // subroutineName (subroutine used)
                JackTokenizer_identifier(thisObject->tokenizer, identifier);
                JackTokenizer_advance(thisObject->tokenizer);

                if (kind != SYMBOL_TABLE_KIND_NONE) {
                    // token is varName
                    char className[JACK_TOKEN_SIZE];
                    SymbolTable_typeOf(thisObject->symbolTable, token, className);
                    sprintf(functionName, "%s.%s", className, identifier);

                    VMWriter_Segment segment;
                    switch (SymbolTable_kindOf(thisObject->symbolTable, token))
                    {
                    case SYMBOL_TABLE_KIND_VAR:
                        segment = VM_WRITER_SEGMENT_LOCAL;
                        break;
                    case SYMBOL_TABLE_KIND_ARG:
                        segment = VM_WRITER_SEGMENT_ARG;
                        break;
                    case SYMBOL_TABLE_KIND_FIELD:
                    default:
                        segment = VM_WRITER_SEGMENT_THIS;
                        break;
                    }
                    VMWriter_writePush(
                        thisObject->vmWriter,
                        segment,
                        SymbolTable_indexOf(thisObject->symbolTable, token)
                    );
                    nArgs++;
                } else {
                    // token is className
                    sprintf(functionName, "%s.%s", token, identifier);
                }

                // '('
                JackTokenizer_symbol(thisObject->tokenizer, symbol);
            } else {
                // token is subroutineName (subroutine used)
                sprintf(functionName, "%s.%s", thisObject->className, token);

                VMWriter_writePush(thisObject->vmWriter, VM_WRITER_SEGMENT_POINTER, 0);
                nArgs++;
            }
            JackTokenizer_advance(thisObject->tokenizer);

            nArgs += CompilationEngine_compileExpressionList(thisObject);

            // ')'
            JackTokenizer_symbol(thisObject->tokenizer, symbol);
            JackTokenizer_advance(thisObject->tokenizer);

            VMWriter_writeCall(thisObject->vmWriter, functionName, nArgs);
        } else {
            // token is varName
            VMWriter_Segment segment;
            switch (kind)
            {
            case SYMBOL_TABLE_KIND_VAR:
                segment = VM_WRITER_SEGMENT_LOCAL;
                break;
            case SYMBOL_TABLE_KIND_ARG:
                segment = VM_WRITER_SEGMENT_ARG;
                break;
            case SYMBOL_TABLE_KIND_FIELD:
            default:
                segment = VM_WRITER_SEGMENT_THIS;
                break;
            }
            VMWriter_writePush(
                thisObject->vmWriter,
                segment,
                SymbolTable_indexOf(thisObject->symbolTable, token)
            );
        }
    }
}

配列と文字列

ソースコードは11/JackCompiler5/です。

ここでは下記を行いました。

  • 配列と文字列に対応
  • テストコードの Average がコンパイルでき動作確認できるところを目指す

下記で使えます。

test11.sh:L98-L125

cp -r ./nand2tetris/projects/11/Seven 11/JackCompiler5/ && \
cp -r ./nand2tetris/tools/OS/* 11/JackCompiler5/Seven/

cp -r ./nand2tetris/projects/11/ConvertToBin 11/JackCompiler5/ && \
cp -r ./nand2tetris/tools/OS/* 11/JackCompiler5/ConvertToBin/

cp -r ./nand2tetris/projects/11/Square 11/JackCompiler5/ && \
cp -r ./nand2tetris/tools/OS/* 11/JackCompiler5/Square/

cp -r ./nand2tetris/projects/11/Average 11/JackCompiler5/ && \
cp -r ./nand2tetris/tools/OS/* 11/JackCompiler5/Average/

cd 11/JackCompiler5/

clang --std=c11 -Wall -Wextra -o JackCompiler main.c JackTokenizer.c JackTokenizerPrivate.c SymbolTable.c SymbolTablePrivate.c VMWriter.c CompilationEngine.c

./JackCompiler Seven
./JackCompiler ConvertToBin
./JackCompiler Square
./JackCompiler Average

cd -

# ./nand2tetris/tools/VMEmulator.sh
#   11/JackCompiler5/Seven
#   11/JackCompiler5/ConvertToBin
#   11/JackCompiler5/Square
#   11/JackCompiler5/Average
  • 動かすためにOS提供関数の./nand2tetris/tools/OS/以下のファイルを使っています。
  • テストは自動実行できないので手動で確認する必要があります*6。

実行するとScreenエリアにプロンプトが現れて入力した数値の平均が計算されます。

CompilationEngineモジュール

CompilationEngine_compileLet

配列に対する代入に対応しました。expression結果の1時的な退避先としてtmpセグメントを使用しています。

11/JackCompiler5/CompilationEngine.c:L381-L439

void CompilationEngine_compileLet(CompilationEngine thisObject)
{
    // ...(省略)...

    // '[' or '='
    bool isArray = false;
    JackTokenizer_symbol(thisObject->tokenizer, symbol);
    if (isSymbolToken(thisObject, "[")) {
        // varName is Array
        isArray = true;
        JackTokenizer_advance(thisObject->tokenizer);

        // push index of array
        CompilationEngine_compileExpression(thisObject);
        // push varName
        VMWriter_writePush(
            thisObject->vmWriter,
            convertKindToSegment(kind),
            SymbolTable_indexOf(thisObject->symbolTable, varName)
        );
        // setup that segment 0 (1/2)
        VMWriter_writeArithmetic(thisObject->vmWriter, VM_WRITER_COMMAND_ADD);

        // ']'
        JackTokenizer_symbol(thisObject->tokenizer, symbol);
        JackTokenizer_advance(thisObject->tokenizer);

        // '='
        JackTokenizer_symbol(thisObject->tokenizer, symbol);
    }
    JackTokenizer_advance(thisObject->tokenizer);

    CompilationEngine_compileExpression(thisObject);

    if (isArray) {
        // setup that segment 0 (2/2)
        // pop expression result, pop, push expression result
        VMWriter_writePop(thisObject->vmWriter, VM_WRITER_SEGMENT_TEMP, 0);
        VMWriter_writePop(thisObject->vmWriter, VM_WRITER_SEGMENT_POINTER, 1);
        VMWriter_writePush(thisObject->vmWriter, VM_WRITER_SEGMENT_TEMP, 0);
        VMWriter_writePop(thisObject->vmWriter, VM_WRITER_SEGMENT_THAT, 0);
    } else {
        VMWriter_writePop(
            thisObject->vmWriter,
            convertKindToSegment(kind),
            SymbolTable_indexOf(thisObject->symbolTable, varName)
        );
    }

    // ...(省略)...
}

CompilationEngine_compileTerm

  • 文字列に対応しました。
  • 配列への代入に対応しました。

11/JackCompiler5/CompilationEngine.c:L628-L778

void CompilationEngine_compileTerm(CompilationEngine thisObject)
{
    // ...(省略)...

    if (JackTokenizer_tokenType(thisObject->tokenizer) == JACK_TOKENIZER_TOKEN_TYPE_INT_CONST) {
        // ...(省略)...
    } else if (JackTokenizer_tokenType(thisObject->tokenizer) == JACK_TOKENIZER_TOKEN_TYPE_STRING_CONST) {
        // stringConstant
        JackTokenizer_stringVal(thisObject->tokenizer, stringVal);
        JackTokenizer_advance(thisObject->tokenizer);

        int length = strlen(stringVal);
        VMWriter_writePush(thisObject->vmWriter, VM_WRITER_SEGMENT_CONST, length);
        VMWriter_writeCall(thisObject->vmWriter, "String.new", 1);
        for (int i = 0; i < length; i++) {
            VMWriter_writePush(thisObject->vmWriter, VM_WRITER_SEGMENT_CONST, stringVal[i]);
            VMWriter_writeCall(thisObject->vmWriter, "String.appendChar", 2);
        }
    } else if (JackTokenizer_tokenType(thisObject->tokenizer) == JACK_TOKENIZER_TOKEN_TYPE_KEYWORD) {
        // ...(省略)...
    } else if (isSymbolToken(thisObject, "(")) {    // '(' expression ')'
        // ...(省略)...
    } else if (inSymbolListToken(thisObject, "-", "~", NULL)) { // unaryOp term
        // ...(省略)...
    } else {    // varName | varName '[' expression ']' | subroutineCall
        // varName | subroutineName | className (used)
        char token[JACK_TOKEN_SIZE];
        JackTokenizer_identifier(thisObject->tokenizer, token);
        SymbolTable_Kind kind = SymbolTable_kindOf(thisObject->symbolTable, token);
        JackTokenizer_advance(thisObject->tokenizer);

        // '[' or '(' or '.' or not
        if (isSymbolToken(thisObject, "[")) {
            // token is Array of varName (varName[])
            JackTokenizer_symbol(thisObject->tokenizer, symbol);
            JackTokenizer_advance(thisObject->tokenizer);

            // push index of array
            CompilationEngine_compileExpression(thisObject);
            // push varName
            VMWriter_writePush(
                thisObject->vmWriter,
                convertKindToSegment(kind),
                SymbolTable_indexOf(thisObject->symbolTable, token)
            );
            // setup that segment 0
            VMWriter_writeArithmetic(thisObject->vmWriter, VM_WRITER_COMMAND_ADD);
            VMWriter_writePop(thisObject->vmWriter, VM_WRITER_SEGMENT_POINTER, 1);

            // ']'
            JackTokenizer_symbol(thisObject->tokenizer, symbol);
            JackTokenizer_advance(thisObject->tokenizer);

            VMWriter_writePush(thisObject->vmWriter, VM_WRITER_SEGMENT_THAT, 0);
        } else if (inSymbolListToken(thisObject, "(", ".", NULL)) {
        // ...(省略)...
        } else {
        // ...(省略)...
        }
    }
}

スタティック変数を含むオブジェクト

ソースコードは11/JackCompiler6/です。

ここでは下記を行いました。

  • スタティック変数に対応
  • テストコードの Pong がコンパイルでき動作確認できるところを目指す

下記で使えます。

test11.sh:L127-L164

cp -r ./nand2tetris/projects/11/Seven 11/JackCompiler6/ && \
cp -r ./nand2tetris/tools/OS/* 11/JackCompiler6/Seven/

cp -r ./nand2tetris/projects/11/ConvertToBin 11/JackCompiler6/ && \
cp -r ./nand2tetris/tools/OS/* 11/JackCompiler6/ConvertToBin/

cp -r ./nand2tetris/projects/11/Square 11/JackCompiler6/ && \
cp -r ./nand2tetris/tools/OS/* 11/JackCompiler6/Square/

cp -r ./nand2tetris/projects/11/Average 11/JackCompiler6/ && \
cp -r ./nand2tetris/tools/OS/* 11/JackCompiler6/Average/

cp -r ./nand2tetris/projects/11/Pong 11/JackCompiler6/ && \
cp -r ./nand2tetris/tools/OS/* 11/JackCompiler6/Pong/

cp -r ./nand2tetris/projects/11/ComplexArrays 11/JackCompiler6/ && \
cp -r ./nand2tetris/tools/OS/* 11/JackCompiler6/ComplexArrays/

cd 11/JackCompiler6/

clang --std=c11 -Wall -Wextra -o JackCompiler main.c JackTokenizer.c JackTokenizerPrivate.c SymbolTable.c SymbolTablePrivate.c VMWriter.c CompilationEngine.c

./JackCompiler Seven
./JackCompiler ConvertToBin
./JackCompiler Square
./JackCompiler Average
./JackCompiler Pong
./JackCompiler ComplexArrays

cd -

# ./nand2tetris/tools/VMEmulator.sh
#   11/JackCompiler6/Seven
#   11/JackCompiler6/ConvertToBin
#   11/JackCompiler6/Square
#   11/JackCompiler6/Average
#   11/JackCompiler6/Pong
#   11/JackCompiler6/ComplexArrays
  • 動かすためにOS提供関数の./nand2tetris/tools/OS/以下のファイルを使っています。
  • テストは自動実行できないので手動で確認する必要があります*7。

実行するとScreenエリアでPongゲームをプレイすることができます。

CompilationEngineモジュール

CompilationEngine_compileLet

スタティック変数に対応しました。

$ diff 11/JackCompiler5/CompilationEngine.c 11/JackCompiler6/CompilationEngine.c
903a904,906
>     case SYMBOL_TABLE_KIND_STATIC:
>         segment = VM_WRITER_SEGMENT_STATIC;
>         break;

配列の参照と式の評価

ソースコードは11/JackCompiler6/です。

変更はありません。 テストコードの ComplexArrays はコンパイルでき動作確認できる状態です。

実行するとScreenエリアにテスト結果が表示されます。

まとめ

今回でようやくコンパイラは完成です。自作したコンパイラの結果が自作したCPUで動くのは嬉しいですね。ブログにまとめてあったおかげで前回から４年ほど時間が空いてますが記憶を取り戻して続きを進めることができました。C言語の実装についてはRustなどに書き換えたい気持ち。12章はオペレーティングシステムらしいですがたぶんシステムコール相当の関数をJack言語で実装していくみたいです。また気が向いたら進めたいです。

*1:前回から４年も経っている。。

*2:たまたま本棚にあった

*3:確認はNo animationにすること

*4:確認はNo animationにすること

*5:確認はNo animationにすること

*6:確認はNo animationにすること

*7:確認はNo animationにすること