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

前回の続きです*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

概要

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

  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[]);

シンボルの管理のためにはハッシュテーブルを実装しました。実装にあたっては定本 Cプログラマのためのアルゴリズムとデータ構造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;
    }
}

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

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_deleteSymbolTable_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

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

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に対応しました
  • フィールド変数に対応しました
  • メソッド呼び出しの場合は第1引数にオブジェクトを指定するようにしました

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で動くのは嬉しいですね。ブログにまとめてあったおかげで前回から4年ほど時間が空いてますが記憶を取り戻して続きを進めることができました。C言語の実装についてはRustなどに書き換えたい気持ち。12章はオペレーティングシステムらしいですがたぶんシステムコール相当の関数をJack言語で実装していくみたいです。また気が向いたら進めたいです。

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

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

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

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

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

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

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

コンピュータシステムの理論と実装の10章のコンパイラ#1:構文解析を実装しました

前回の続きです。今回はコンピュータシステムの理論と実装(以下、nand2tetris本)の10章のコンパイラ#1:構文解析C言語で実装してみました。

今回のコード

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

github.com

下記で動かせます。

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

概要

今回はコンパイラ構文解析部分です。実装は書籍にしたがって2段階で行いました。

  1. .jackファイルまたは.jackファイル群を入力として受け取りそれぞれに対応する字句解析結果であるT.xmlファイルを生成するコマンドを実装
  2. 構文解析結果である.xmlファイルを生成するコマンドに改造

f:id:nihma:20200726191224p:plain

トークナイザ

ソースコード10/JackAnalyzer/です。

ここでは字句解析を行い下記のトークンに分割しました。

トーク 概要
keyword class, method, function, constructor, int, boolean, char, void, var, static, field, let, do, if, else, while, return, true, false, null, this
symbol {, }, (, ), [, ], ., ,, ;, +, -, *, /, &, |, <, >, =, ~
identifier 数字以外から始まるアルファベット、数字、アンダースコアの文字列
integerConstant 0から32767
stringConstant ダブルクォートで囲まれた文字列

下記で使えます。

test10.sh:L3-L19

cp -r ./nand2tetris/projects/10/Square 10/JackAnalyzer/ && \
mkdir -p 10/JackAnalyzer/Square/expect && \
mv 10/JackAnalyzer/Square/*.xml 10/JackAnalyzer/Square/expect/

# ...(省略)...

cd 10/JackAnalyzer/

clang --std=c11 -Wall -Wextra -o JackAnalyzer main.c JackTokenizer.c JackTokenizerPrivate.c

./JackAnalyzer Square

main.c (JackAnalyzerモジュール)

コマンドのエントリポイントです。書籍ではJackAnalyzerモジュールと呼ばれています。
main.cではコマンド引数の解析、JackTokenizerモジュールを用いた字句解析結果であるT.xmlファイルへの変換処理を行います。main.cの中で使う関数はmain.c内で下記のように定義しました。

10/JackAnalyzer/main.c:L10-L23

int analyzeByJackDir(DIR *dpJack, char *jackDirName);
int analyzeByJackFile(char *jackFileName);
int analyze(char *xmlFilePath, char *jackFilePath);
bool isJackFileName(char *jackFileName);
void createJackFilePath(char *jackDirName, char *jackFileName, char *jackFilePath);
void createXmlFilePathFromDirName(char *jackDirName, char *jackFileName, char *xmlFilePath);
void createXmlFilePathFromJackFileName(char *jackFileName, char *xmlFilePath);
void writeTokens(FILE *fp, JackTokenizer tokenizer);
void writeToken(FILE *fp, JackTokenizer tokenizer);
void writeKeyword(FILE *fp, JackTokenizer tokenizer);
void writeSymbol(FILE *fp, JackTokenizer tokenizer);
void writeIdentifier(FILE *fp, JackTokenizer tokenizer);
void writeIntegerConstant(FILE *fp, JackTokenizer tokenizer);
void writeStringConstant(FILE *fp, JackTokenizer tokenizer);

コマンド引数には.jackファイルまたはjackファイルを複数含むディレクトリいづれかを指定できます。関数はanalyzeByJackDirおよびanalyzeByJackFileです。この処理は前回のバーチャルマシンでの実装とほぼ同じです。ただし出力が1ファイルのバーチャルマシンと違いこちらは.jackに対して一対一に対応する.xmlを出力します。

変換処理の実装は下記の通りです。JackTokenizerモジュールを使用して.xmlを作成します。

10/JackAnalyzer/main.c:L127-L150

int analyze(char *xmlFilePath, char *jackFilePath)
{
    FILE *fpJack, *fpXml;
    JackTokenizer tokenizer;

    if ((fpJack = fopen(jackFilePath, "r")) == NULL) {
        fprintf(stderr, "Error: jack file not found (%s)\n", jackFilePath);
        return 1;
    }

    if ((fpXml = fopen(xmlFilePath, "w")) == NULL) {
        fprintf(stderr, "Error: xml file not open (%s)\n", xmlFilePath);
        fclose(fpJack);
        return 1;
    }

    tokenizer = JackTokenizer_init(fpJack);
    writeTokens(fpXml, tokenizer);

    fclose(fpXml);
    fclose(fpJack);

    return 0;
}

.xmlへのタグの書き込みは下記の通りです。.xmlなので<, >, &はそれぞれ&lt;, &gt;, &amp;"に変換しました。

10/JackAnalyzer/main.c:L197-L309

void writeTokens(FILE *fp, JackTokenizer tokenizer)
{
    fprintf(fp, "<tokens>\n");
    while (JackTokenizer_hasMoreTokens(tokenizer)) {
        JackTokenizer_advance(tokenizer);
        writeToken(fp, tokenizer);
    }
    fprintf(fp, "</tokens>\n");
}

void writeToken(FILE *fp, JackTokenizer tokenizer)
{
    switch (JackTokenizer_tokenType(tokenizer))
    {
    case JACK_TOKENIZER_TOKEN_TYPE_KEYWORD:
        writeKeyword(fp, tokenizer);
        break;
    case JACK_TOKENIZER_TOKEN_TYPE_SYMBOL:
        writeSymbol(fp, tokenizer);
        break;
    case JACK_TOKENIZER_TOKEN_TYPE_IDENTIFIER:
        writeIdentifier(fp, tokenizer);
        break;
    case JACK_TOKENIZER_TOKEN_TYPE_INT_CONST:
        writeIntegerConstant(fp, tokenizer);
        break;
    case JACK_TOKENIZER_TOKEN_TYPE_STRING_CONST:
        writeStringConstant(fp, tokenizer);
        break; 
    default:
        break;
    }
}

void writeKeyword(FILE *fp, JackTokenizer tokenizer)
{
    struct keyword {
        JackTokenizer_Keyword id;
        char *string;
    };
    struct keyword keywords[] = {
        { JACK_TOKENIZER_KEYWORD_CLASS,        "class" },
        { JACK_TOKENIZER_KEYWORD_METHOD,       "method" },
        { JACK_TOKENIZER_KEYWORD_FUNCTION,     "function" },
        { JACK_TOKENIZER_KEYWORD_CONSTRUCTION, "constructor" },
        { JACK_TOKENIZER_KEYWORD_INT,          "int" },
        { JACK_TOKENIZER_KEYWORD_BOOLEAN,      "boolean" },
        { JACK_TOKENIZER_KEYWORD_CHAR,         "char" },
        { JACK_TOKENIZER_KEYWORD_VOID,         "void" },
        { JACK_TOKENIZER_KEYWORD_VAR,          "var" },
        { JACK_TOKENIZER_KEYWORD_STATIC,       "static" },
        { JACK_TOKENIZER_KEYWORD_FIELD,        "field" },
        { JACK_TOKENIZER_KEYWORD_LET,          "let" },
        { JACK_TOKENIZER_KEYWORD_DO,           "do" },
        { JACK_TOKENIZER_KEYWORD_IF,           "if" },
        { JACK_TOKENIZER_KEYWORD_ELSE,         "else" },
        { JACK_TOKENIZER_KEYWORD_WHILE,        "while" },
        { JACK_TOKENIZER_KEYWORD_RETURN,       "return" },
        { JACK_TOKENIZER_KEYWORD_TRUE,         "true" },
        { JACK_TOKENIZER_KEYWORD_FALSE,        "false" },
        { JACK_TOKENIZER_KEYWORD_NULL,         "null" },
        { JACK_TOKENIZER_KEYWORD_THIS,         "this" },
    };
    JackTokenizer_Keyword id = JackTokenizer_keyword(tokenizer);

    fprintf(fp, "<keyword> ");
    for (size_t i = 0; i < sizeof(keywords) / sizeof(keywords[0]); i++) {
        if (id == keywords[i].id) {
            fprintf(fp, "%s", keywords[i].string);
            break;
        }
    }
    fprintf(fp, " </keyword>\n");
}

void writeSymbol(FILE *fp, JackTokenizer tokenizer)
{
    char token[JACK_TOKEN_SIZE];
    JackTokenizer_symbol(tokenizer, token);

    fprintf(fp, "<symbol> ");
    if (strcmp(token, "<") == 0) {
        fprintf(fp, "&lt;");
    } else if (strcmp(token, ">") == 0) {
        fprintf(fp, "&gt;");
    } else if (strcmp(token, "&") == 0) {
        fprintf(fp, "&amp;");
    } else {
        fprintf(fp, "%s", token);
    }
    fprintf(fp, " </symbol>\n");
}

void writeIdentifier(FILE *fp, JackTokenizer tokenizer)
{
    char token[JACK_TOKEN_SIZE];
    JackTokenizer_identifier(tokenizer, token);
    fprintf(fp, "<identifier> %s </identifier>\n", token);
}

void writeIntegerConstant(FILE *fp, JackTokenizer tokenizer)
{
    int intVal;
    JackTokenizer_intVal(tokenizer, &intVal);
    fprintf(fp, "<integerConstant> %d </integerConstant>\n", intVal);
}

void writeStringConstant(FILE *fp, JackTokenizer tokenizer)
{
    char token[JACK_TOKEN_SIZE];
    JackTokenizer_stringVal(tokenizer, token);
    fprintf(fp, "<stringConstant> %s </stringConstant>\n", token);
}

JackTokenizerモジュール

.jackファイルを字句解析するためのモジュールです。
main.cで利用する関数はJackTokenizer.hで下記のように定義しました。jack_tokenizer構造体はtypedefして定義はJackTokenizer.c内に隠蔽するようにしてオブジェクトとして使うようにしました。それぞれの実装はJackTokenizer.cで行いました。

10/JackAnalyzer/JackTokenizer.h:L9-L53

typedef enum {
    JACK_TOKENIZER_TOKEN_TYPE_KEYWORD = 1,
    JACK_TOKENIZER_TOKEN_TYPE_SYMBOL,
    JACK_TOKENIZER_TOKEN_TYPE_IDENTIFIER,
    JACK_TOKENIZER_TOKEN_TYPE_INT_CONST,
    JACK_TOKENIZER_TOKEN_TYPE_STRING_CONST,
    JACK_TOKENIZER_TOKEN_TYPE_STRING_UNKNOWN
} JackTokenizer_TokenType;

typedef enum {
    JACK_TOKENIZER_KEYWORD_CLASS = 1,
    JACK_TOKENIZER_KEYWORD_METHOD,
    JACK_TOKENIZER_KEYWORD_FUNCTION,
    JACK_TOKENIZER_KEYWORD_CONSTRUCTION,
    JACK_TOKENIZER_KEYWORD_INT,
    JACK_TOKENIZER_KEYWORD_BOOLEAN,
    JACK_TOKENIZER_KEYWORD_CHAR,
    JACK_TOKENIZER_KEYWORD_VOID,
    JACK_TOKENIZER_KEYWORD_VAR,
    JACK_TOKENIZER_KEYWORD_STATIC,
    JACK_TOKENIZER_KEYWORD_FIELD,
    JACK_TOKENIZER_KEYWORD_LET,
    JACK_TOKENIZER_KEYWORD_DO,
    JACK_TOKENIZER_KEYWORD_IF,
    JACK_TOKENIZER_KEYWORD_ELSE,
    JACK_TOKENIZER_KEYWORD_WHILE,
    JACK_TOKENIZER_KEYWORD_RETURN,
    JACK_TOKENIZER_KEYWORD_TRUE,
    JACK_TOKENIZER_KEYWORD_FALSE,
    JACK_TOKENIZER_KEYWORD_NULL,
    JACK_TOKENIZER_KEYWORD_THIS,
    JACK_TOKENIZER_KEYWORD_UNKNOWN
} JackTokenizer_Keyword;

typedef struct jack_tokenizer * JackTokenizer;

JackTokenizer JackTokenizer_init(FILE *fpJack);
bool JackTokenizer_hasMoreTokens(JackTokenizer thisObject);
void JackTokenizer_advance(JackTokenizer thisObject);
JackTokenizer_TokenType JackTokenizer_tokenType(JackTokenizer thisObject);
JackTokenizer_Keyword JackTokenizer_keyword(JackTokenizer thisObject);
void JackTokenizer_symbol(JackTokenizer thisObject, char *symbol);
void JackTokenizer_identifier(JackTokenizer thisObject, char *identifier);
void JackTokenizer_intVal(JackTokenizer thisObject, int *intVal);
void JackTokenizer_stringVal(JackTokenizer thisObject, char *stringVal);

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

10/JackAnalyzer/JackTokenizerPrivate.h:L7-L12

void moveNextToken(FILE *fp);
bool isEndOfFile(FILE *fp);
bool getTokenSymbol(FILE *fp, char *token);
bool getTokenStringConstant(FILE *fp, char *token);
bool getTokenIntConstant(FILE *fp, char *token);
bool getTokenIdentifierOrKeyword(FILE *fp, char *token);

現在のトークンの種類やキーワードの場合のキーワードの種類の判断はJackTokenizer_advance関数で行いました。

10/JackAnalyzer/JackTokenizer.c:L36-L56

void JackTokenizer_advance(JackTokenizer thisObject)
{
    thisObject->keyword = JACK_TOKENIZER_KEYWORD_UNKNOWN;
    if (getTokenSymbol(thisObject->fpJack, thisObject->token)) {
        thisObject->type = JACK_TOKENIZER_TOKEN_TYPE_SYMBOL;
    } else if (getTokenStringConstant(thisObject->fpJack, thisObject->token)) {
        thisObject->type = JACK_TOKENIZER_TOKEN_TYPE_STRING_CONST;
    } else if (getTokenIntConstant(thisObject->fpJack, thisObject->token)) {
        thisObject->type = JACK_TOKENIZER_TOKEN_TYPE_INT_CONST;
    } else {
        getTokenIdentifierOrKeyword(thisObject->fpJack, thisObject->token);

        thisObject->keyword = convertIdentifierToKeyword(thisObject->token);
        if (thisObject->keyword == JACK_TOKENIZER_KEYWORD_UNKNOWN) {
            thisObject->type = JACK_TOKENIZER_TOKEN_TYPE_IDENTIFIER;
        } else {
            thisObject->type = JACK_TOKENIZER_TOKEN_TYPE_KEYWORD;
        }
    }
    moveNextToken(thisObject->fpJack);
}

キーワードの種類の文字列をJackTokenizer_Keyword定数に変換する処理は下記の通りです。

10/JackAnalyzer/JackTokenizer.c:L96-L131

JackTokenizer_Keyword convertIdentifierToKeyword(char *token)
{
    struct keyword {
        JackTokenizer_Keyword id;
        char *string;
    };
    struct keyword keywords[] = {
        { JACK_TOKENIZER_KEYWORD_CLASS,        "class" },
        { JACK_TOKENIZER_KEYWORD_METHOD,       "method" },
        { JACK_TOKENIZER_KEYWORD_FUNCTION,     "function" },
        { JACK_TOKENIZER_KEYWORD_CONSTRUCTION, "constructor" },
        { JACK_TOKENIZER_KEYWORD_INT,          "int" },
        { JACK_TOKENIZER_KEYWORD_BOOLEAN,      "boolean" },
        { JACK_TOKENIZER_KEYWORD_CHAR,         "char" },
        { JACK_TOKENIZER_KEYWORD_VOID,         "void" },
        { JACK_TOKENIZER_KEYWORD_VAR,          "var" },
        { JACK_TOKENIZER_KEYWORD_STATIC,       "static" },
        { JACK_TOKENIZER_KEYWORD_FIELD,        "field" },
        { JACK_TOKENIZER_KEYWORD_LET,          "let" },
        { JACK_TOKENIZER_KEYWORD_DO,           "do" },
        { JACK_TOKENIZER_KEYWORD_IF,           "if" },
        { JACK_TOKENIZER_KEYWORD_ELSE,         "else" },
        { JACK_TOKENIZER_KEYWORD_WHILE,        "while" },
        { JACK_TOKENIZER_KEYWORD_RETURN,       "return" },
        { JACK_TOKENIZER_KEYWORD_TRUE,         "true" },
        { JACK_TOKENIZER_KEYWORD_FALSE,        "false" },
        { JACK_TOKENIZER_KEYWORD_NULL,         "null" },
        { JACK_TOKENIZER_KEYWORD_THIS,         "this" },
    };
    for (size_t i = 0; i < sizeof(keywords) / sizeof(keywords[0]); i++) {
        if (strcmp(token, keywords[i].string) == 0) {
            return keywords[i].id;
        }
    }
    return JACK_TOKENIZER_KEYWORD_UNKNOWN;
}

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

パーサ

ここでは下記の通りJack言語の文法に従い構文解析処理の実装を行いました。各実装はCompilationEngineモジュールを参照。

  • CompilationEngine_compileClass関数
    • class: 'class' className '{' classVarDec* subroutineDec* '}'
  • CompilationEngine_compileClassVarDec関数
    • classVarDec: ('static' | 'field') type varName (',' varName)* ';'
  • CompilationEngine_compileSubroutine関数
    • subroutineDec: ('constructor' | 'function' | 'method') ('void' | type) subroutineName '(' parameterList ')' subroutineBody
    • subroutineBody: '{' varDec* statements '}'
  • CompilationEngine_compileParameterList関数
    • parameterList: ((type varName) (',' type varName)*)?
  • CompilationEngine_compileVarDec関数
    • varDec: 'var' type varName (',' varName)* ';'
  • CompilationEngine_compileStatements関数
    • statements: statement*
    • statement: letStatement | ifStatement | whileStatement | doStatement | returnStatement
  • CompilationEngine_compileDo関数
    • doStatement: 'do' subroutineCall ';'
    • subroutineCall: subroutineName '(' expressionList ')' | (className | varName) '.' subroutineName '(' expressionList ')'
  • CompilationEngine_compileLet関数
    • letStatement: 'let' varName ('[' expression ']')? '=' expression ';'
  • CompilationEngine_compileWhile関数
    • whileStatement: 'while' '(' expression ')' '{' statements '}'
  • CompilationEngine_compileReturn関数
    • returnStatement: 'return' expression? ';'
  • CompilationEngine_compileIf関数
    • ifStatement: 'if' '(' expression ')' '{' statements '}' ('else' '{' statements '}')?
  • CompilationEngine_compileExpression関数
    • expression: term (op term)*
    • op: '+' | '-' | '*' | '/' | '&' | '|' | '<' | '>' | '='
  • CompilationEngine_compileTerm関数
    • term: integerConstant | stringConstant | keywordConstant | varName | varName '[' expression ']' | subroutineCall | '(' expression ')' | unaryOp term
    • subroutineCall: subroutineName '(' expressionList ')' | (className | varName) '.' subroutineName '(' expressionList ')'
    • unaryOp: '-' | '~'
  • CompilationEngine_compileExpressionList関数
    • expressionList: (expression (',' expression)*)?

式を含まない版

ソースコード10/JackAnalyzer2/です。

ここではJack言語の文法のうちCompilationEngine_compileTerm以外について実装しました。

下記で使えます。

test10.sh:L34-L42

cp -r ./nand2tetris/projects/10/ExpressionLessSquare 10/JackAnalyzer2/ && \
mkdir -p 10/JackAnalyzer2/ExpressionLessSquare/expect && \
mv 10/JackAnalyzer2/ExpressionLessSquare/*.xml 10/JackAnalyzer2/ExpressionLessSquare/expect/

cd 10/JackAnalyzer2/

clang --std=c11 -Wall -Wextra -o JackAnalyzer main.c JackTokenizer.c JackTokenizerPrivate.c CompilationEngine.c

./JackAnalyzer ExpressionLessSquare

main.c (JackAnalyzerモジュール)

下記の変更を行いました。

  • 生成する.xmlファイルの名前をXxxT.xmlからXxx.xmlに変更
  • analyze関数をCompilationEngineモジュールを用いるように変更
  • writeXXX関数を削除(CompilationEngineモジュールへ移動)

差分は下記の通りです。

$ diff 10/JackAnalyzer/main.c 10/JackAnalyzer2/main.c 
1c1
< #include "JackTokenizer.h"
---
> #include "CompilationEngine.h"
2a3
> #include <stdbool.h>
7c8
< #define XML_FILENAME_MAX_LENGTH JACK_FILENAME_MAX_LENGTH  // length('.jack') - length('T.xml') = 0
---
> #define XML_FILENAME_MAX_LENGTH (JACK_FILENAME_MAX_LENGTH - 1)  // length('.jack') - length('.xml') = 1
17,23d17
< void writeTokens(FILE *fp, JackTokenizer tokenizer);
< void writeToken(FILE *fp, JackTokenizer tokenizer);
< void writeKeyword(FILE *fp, JackTokenizer tokenizer);
< void writeSymbol(FILE *fp, JackTokenizer tokenizer);
< void writeIdentifier(FILE *fp, JackTokenizer tokenizer);
< void writeIntegerConstant(FILE *fp, JackTokenizer tokenizer);
< void writeStringConstant(FILE *fp, JackTokenizer tokenizer);
130c124
<     JackTokenizer tokenizer;
---
>     CompilationEngine compilationEngine;
143,144c137,138
<     tokenizer = JackTokenizer_init(fpJack);
<     writeTokens(fpXml, tokenizer);
---
>     compilationEngine = CompilationEngine_init(fpJack, fpXml);
>     CompilationEngine_compileClass(compilationEngine);
180c174
<     // xmlFilePath is {jackDirName}/{jackFileName} - ".jack" + "T.xml"
---
>     // xmlFilePath is {jackDirName}/{jackFileName} - ".jack" + ".xml"
184c178
<     strcat(xmlFilePath, "T.xml");
---
>     strcat(xmlFilePath, ".xml");
189c183
<     // XmlFilePath is {jackFileName} - ".jack" + "T.xml"
---
>     // XmlFilePath is {jackFileName} - ".jack" + ".xml"
194,308c188
<     strcat(xmlFilePath, "T.xml");
< }
< 
< void writeTokens(FILE *fp, JackTokenizer tokenizer)
< {
<     fprintf(fp, "<tokens>\n");
<     while (JackTokenizer_hasMoreTokens(tokenizer)) {
<         JackTokenizer_advance(tokenizer);
<         writeToken(fp, tokenizer);
<     }
<     fprintf(fp, "</tokens>\n");
< }
< 
< void writeToken(FILE *fp, JackTokenizer tokenizer)
< {
<     switch (JackTokenizer_tokenType(tokenizer))
<     {
<     case JACK_TOKENIZER_TOKEN_TYPE_KEYWORD:
<         writeKeyword(fp, tokenizer);
<         break;
<     case JACK_TOKENIZER_TOKEN_TYPE_SYMBOL:
<         writeSymbol(fp, tokenizer);
<         break;
<     case JACK_TOKENIZER_TOKEN_TYPE_IDENTIFIER:
<         writeIdentifier(fp, tokenizer);
<         break;
<     case JACK_TOKENIZER_TOKEN_TYPE_INT_CONST:
<         writeIntegerConstant(fp, tokenizer);
<         break;
<     case JACK_TOKENIZER_TOKEN_TYPE_STRING_CONST:
<         writeStringConstant(fp, tokenizer);
<         break; 
<     default:
<         break;
<     }
< }
< 
< void writeKeyword(FILE *fp, JackTokenizer tokenizer)
< {
<     struct keyword {
<         JackTokenizer_Keyword id;
<         char *string;
<     };
<     struct keyword keywords[] = {
<         { JACK_TOKENIZER_KEYWORD_CLASS,        "class" },
<         { JACK_TOKENIZER_KEYWORD_METHOD,       "method" },
<         { JACK_TOKENIZER_KEYWORD_FUNCTION,     "function" },
<         { JACK_TOKENIZER_KEYWORD_CONSTRUCTION, "constructor" },
<         { JACK_TOKENIZER_KEYWORD_INT,          "int" },
<         { JACK_TOKENIZER_KEYWORD_BOOLEAN,      "boolean" },
<         { JACK_TOKENIZER_KEYWORD_CHAR,         "char" },
<         { JACK_TOKENIZER_KEYWORD_VOID,         "void" },
<         { JACK_TOKENIZER_KEYWORD_VAR,          "var" },
<         { JACK_TOKENIZER_KEYWORD_STATIC,       "static" },
<         { JACK_TOKENIZER_KEYWORD_FIELD,        "field" },
<         { JACK_TOKENIZER_KEYWORD_LET,          "let" },
<         { JACK_TOKENIZER_KEYWORD_DO,           "do" },
<         { JACK_TOKENIZER_KEYWORD_IF,           "if" },
<         { JACK_TOKENIZER_KEYWORD_ELSE,         "else" },
<         { JACK_TOKENIZER_KEYWORD_WHILE,        "while" },
<         { JACK_TOKENIZER_KEYWORD_RETURN,       "return" },
<         { JACK_TOKENIZER_KEYWORD_TRUE,         "true" },
<         { JACK_TOKENIZER_KEYWORD_FALSE,        "false" },
<         { JACK_TOKENIZER_KEYWORD_NULL,         "null" },
<         { JACK_TOKENIZER_KEYWORD_THIS,         "this" },
<     };
<     JackTokenizer_Keyword id = JackTokenizer_keyword(tokenizer);
< 
<     fprintf(fp, "<keyword> ");
<     for (size_t i = 0; i < sizeof(keywords) / sizeof(keywords[0]); i++) {
<         if (id == keywords[i].id) {
<             fprintf(fp, "%s", keywords[i].string);
<             break;
<         }
<     }
<     fprintf(fp, " </keyword>\n");
< }
< 
< void writeSymbol(FILE *fp, JackTokenizer tokenizer)
< {
<     char token[JACK_TOKEN_SIZE];
<     JackTokenizer_symbol(tokenizer, token);
< 
<     fprintf(fp, "<symbol> ");
<     if (strcmp(token, "<") == 0) {
<         fprintf(fp, "&lt;");
<     } else if (strcmp(token, ">") == 0) {
<         fprintf(fp, "&gt;");
<     } else if (strcmp(token, "&") == 0) {
<         fprintf(fp, "&amp;");
<     } else {
<         fprintf(fp, "%s", token);
<     }
<     fprintf(fp, " </symbol>\n");
< }
< 
< void writeIdentifier(FILE *fp, JackTokenizer tokenizer)
< {
<     char token[JACK_TOKEN_SIZE];
<     JackTokenizer_identifier(tokenizer, token);
<     fprintf(fp, "<identifier> %s </identifier>\n", token);
< }
< 
< void writeIntegerConstant(FILE *fp, JackTokenizer tokenizer)
< {
<     int intVal;
<     JackTokenizer_intVal(tokenizer, &intVal);
<     fprintf(fp, "<integerConstant> %d </integerConstant>\n", intVal);
< }
< 
< void writeStringConstant(FILE *fp, JackTokenizer tokenizer)
< {
<     char token[JACK_TOKEN_SIZE];
<     JackTokenizer_stringVal(tokenizer, token);
<     fprintf(fp, "<stringConstant> %s </stringConstant>\n", token);
---
>     strcat(xmlFilePath, ".xml");

JackTokenizerモジュール

変更はありません。

$ diff 10/JackAnalyzer/JackTokenizer.h 10/JackAnalyzer2/JackTokenizer.h 
$ diff 10/JackAnalyzer/JackTokenizer.c 10/JackAnalyzer2/JackTokenizer.c 
$ diff 10/JackAnalyzer/JackTokenizerPrivate.h 10/JackAnalyzer2/JackTokenizerPrivate.h
$ diff 10/JackAnalyzer/JackTokenizerPrivate.c 10/JackAnalyzer2/JackTokenizerPrivate.c

CompilationEngineモジュール

.jackファイル構文解析して.xmlファイルに出力するためのモジュールです。
main.cで利用する関数はCompilationEngine.hで下記のように定義しました。compilation_engine構造体はtypedefして定義はCompilationEngine.c内に隠蔽するようにしてオブジェクトとして使うようにしました。それぞれの実装はCompilationEngine.cで行いました。

10/JackAnalyzer2/CompilationEngine.h:L6-L22

typedef struct compilation_engine * CompilationEngine;

CompilationEngine CompilationEngine_init(FILE *fpJack, FILE *fpXml);
void CompilationEngine_compileClass(CompilationEngine thisObject);
void CompilationEngine_compileClassVarDec(CompilationEngine thisObject);
void CompilationEngine_compileSubroutine(CompilationEngine thisObject);
void CompilationEngine_compileParameterList(CompilationEngine thisObject);
void CompilationEngine_compileVarDec(CompilationEngine thisObject);
void CompilationEngine_compileStatements(CompilationEngine thisObject);
void CompilationEngine_compileDo(CompilationEngine thisObject);
void CompilationEngine_compileLet(CompilationEngine thisObject);
void CompilationEngine_compileWhile(CompilationEngine thisObject);
void CompilationEngine_compileReturn(CompilationEngine thisObject);
void CompilationEngine_compileIf(CompilationEngine thisObject);
void CompilationEngine_compileExpression(CompilationEngine thisObject);
void CompilationEngine_compileTerm(CompilationEngine thisObject);
void CompilationEngine_compileExpressionList(CompilationEngine thisObject);

またCompilationEngine.c内で使う関数は下記の通りです。writeXXX関数はmain.cから移動してきました。

10/JackAnalyzer2/CompilationEngine.c:L6-L15

void writeToken(FILE *fp, JackTokenizer tokenizer);
void writeKeyword(FILE *fp, JackTokenizer tokenizer);
void writeSymbol(FILE *fp, JackTokenizer tokenizer);
void writeIdentifier(FILE *fp, JackTokenizer tokenizer);
void writeIntegerConstant(FILE *fp, JackTokenizer tokenizer);
void writeStringConstant(FILE *fp, JackTokenizer tokenizer);
void advanceAndWriteToken(CompilationEngine thisObject);
bool isKeywordToken(CompilationEngine thisObject, JackTokenizer_Keyword keyword);
bool isSymbolToken(CompilationEngine thisObject, char *symbol);
bool inSymbolListToken(CompilationEngine thisObject, ...);

Jack言語の文法にしたがって構文解析して.xmlファイルに出力する実装は下記の通りです。ほぼLL(1)文法であるため割とシンプルです。なお、CompilationEngine_compileTermだけは次節で実装するためきちんとした実装にはなっていません。

10/JackAnalyzer2/CompilationEngine.c:L34-L359

// 'class' className '{' classVarDec* subroutineDec* '}'
void CompilationEngine_compileClass(CompilationEngine thisObject)
{
    fprintf(thisObject->fpXml, "<class>\n");

    advanceAndWriteToken(thisObject);   // 'class'
    advanceAndWriteToken(thisObject);   // className
    advanceAndWriteToken(thisObject);   // '{'

    JackTokenizer_advance(thisObject->tokenizer);   // '}' or not
    while (! isSymbolToken(thisObject, "}")) {
        if (
            isKeywordToken(thisObject, JACK_TOKENIZER_KEYWORD_STATIC) ||
            isKeywordToken(thisObject, JACK_TOKENIZER_KEYWORD_FIELD)
        ) {  // classVarDec
            CompilationEngine_compileClassVarDec(thisObject);
        } else if (
            isKeywordToken(thisObject, JACK_TOKENIZER_KEYWORD_CONSTRUCTION) ||
            isKeywordToken(thisObject, JACK_TOKENIZER_KEYWORD_FUNCTION) ||
            isKeywordToken(thisObject, JACK_TOKENIZER_KEYWORD_METHOD)
        ) {  // subroutineDec
            CompilationEngine_compileSubroutine(thisObject);
        } else {
            break;
        }
    }
    writeToken(thisObject->fpXml ,thisObject->tokenizer);    // '}'

    fprintf(thisObject->fpXml, "</class>\n");
}

// ('static' | 'field') type varName (',' varName)* ';'
void CompilationEngine_compileClassVarDec(CompilationEngine thisObject)
{
    fprintf(thisObject->fpXml, "<classVarDec>\n");

    writeToken(thisObject->fpXml ,thisObject->tokenizer);   // ('static' | 'field')
    advanceAndWriteToken(thisObject);   // type

    do {
        advanceAndWriteToken(thisObject);   // varName
        advanceAndWriteToken(thisObject);   // ',' or ';'
    } while (! isSymbolToken(thisObject, ";"));

    fprintf(thisObject->fpXml, "</classVarDec>\n");

    JackTokenizer_advance(thisObject->tokenizer);
}

// ('constructor' | 'function' | 'method') ('void' | type) subroutineName '(' parameterList ')' subroutineBody
// subroutineBody: '{' varDec* statements '}'
void CompilationEngine_compileSubroutine(CompilationEngine thisObject)
{
    fprintf(thisObject->fpXml, "<subroutineDec>\n");

    writeToken(thisObject->fpXml ,thisObject->tokenizer);   // ('constructor' | 'function' | 'method')
    advanceAndWriteToken(thisObject);   // ('void' | type)
    advanceAndWriteToken(thisObject);   // subroutineName
    advanceAndWriteToken(thisObject);   // '('

    JackTokenizer_advance(thisObject->tokenizer);
    CompilationEngine_compileParameterList(thisObject);

    writeToken(thisObject->fpXml ,thisObject->tokenizer);   // ')'

    fprintf(thisObject->fpXml, "<subroutineBody>\n");

    advanceAndWriteToken(thisObject);   // '{'

    JackTokenizer_advance(thisObject->tokenizer);   // 'var' or statements or '}'
    while (isKeywordToken(thisObject, JACK_TOKENIZER_KEYWORD_VAR)) {
        CompilationEngine_compileVarDec(thisObject);
    }
    if (! isSymbolToken(thisObject, "}")) {   // statements or '}'
        CompilationEngine_compileStatements(thisObject);
    }
    writeToken(thisObject->fpXml, thisObject->tokenizer);   // '}'

    fprintf(thisObject->fpXml, "</subroutineBody>\n");

    fprintf(thisObject->fpXml, "</subroutineDec>\n");

    JackTokenizer_advance(thisObject->tokenizer);
}

// ((type varName) (',' type varName)*)?
void CompilationEngine_compileParameterList(CompilationEngine thisObject)
{
    fprintf(thisObject->fpXml, "<parameterList>\n");

    if (JackTokenizer_tokenType(thisObject->tokenizer) == JACK_TOKENIZER_TOKEN_TYPE_KEYWORD) {  // type
        writeToken(thisObject->fpXml ,thisObject->tokenizer);   // type
        advanceAndWriteToken(thisObject);   // varName

        JackTokenizer_advance(thisObject->tokenizer);   // ',' or not
        while (isSymbolToken(thisObject, ",")) {
            writeToken(thisObject->fpXml ,thisObject->tokenizer);   // ','
            advanceAndWriteToken(thisObject);   // type
            advanceAndWriteToken(thisObject);   // varName
            JackTokenizer_advance(thisObject->tokenizer);   // ',' or not
        }
    }

    fprintf(thisObject->fpXml, "</parameterList>\n");
}

// 'var' type varName (',' varName)* ';'
void CompilationEngine_compileVarDec(CompilationEngine thisObject)
{
    fprintf(thisObject->fpXml, "<varDec>\n");

    writeToken(thisObject->fpXml, thisObject->tokenizer);   // 'var'
    advanceAndWriteToken(thisObject);   // type

    do {
        advanceAndWriteToken(thisObject);   // varName
        advanceAndWriteToken(thisObject);   // ',' or ';'
    } while (! isSymbolToken(thisObject, ";"));

    fprintf(thisObject->fpXml, "</varDec>\n");

    JackTokenizer_advance(thisObject->tokenizer);
}

// statement*
// statement: letStatement | ifStatement | whileStatement | doStatement | returnStatement
void CompilationEngine_compileStatements(CompilationEngine thisObject)
{
    fprintf(thisObject->fpXml, "<statements>\n");

    do {
        if (isKeywordToken(thisObject, JACK_TOKENIZER_KEYWORD_LET)) {
            CompilationEngine_compileLet(thisObject);
        } else if (isKeywordToken(thisObject, JACK_TOKENIZER_KEYWORD_IF)) {
            CompilationEngine_compileIf(thisObject);
        } else if (isKeywordToken(thisObject, JACK_TOKENIZER_KEYWORD_WHILE)) {
            CompilationEngine_compileWhile(thisObject);
        } else if (isKeywordToken(thisObject, JACK_TOKENIZER_KEYWORD_DO)) {
            CompilationEngine_compileDo(thisObject);
        } else if (isKeywordToken(thisObject, JACK_TOKENIZER_KEYWORD_RETURN)) {
            CompilationEngine_compileReturn(thisObject);
        } else {
            break;
        }
    } while (true);

    fprintf(thisObject->fpXml, "</statements>\n");
}

// 'do' subroutineCall ';'
// subroutineCall: subroutineName '(' expressionList ')' | (className | varName) '.' subroutineName '(' expressionList ')'
void CompilationEngine_compileDo(CompilationEngine thisObject)
{
    fprintf(thisObject->fpXml, "<doStatement>\n");

    writeToken(thisObject->fpXml ,thisObject->tokenizer);   // 'do'

    advanceAndWriteToken(thisObject);   // subroutineName | (className | varName)
    advanceAndWriteToken(thisObject);   // '(' or '.'
    if (isSymbolToken(thisObject, ".")) {
        advanceAndWriteToken(thisObject);   // subroutineName
        advanceAndWriteToken(thisObject);   // '('
    }

    JackTokenizer_advance(thisObject->tokenizer);
    CompilationEngine_compileExpressionList(thisObject);

    writeToken(thisObject->fpXml ,thisObject->tokenizer);   // ')'
    advanceAndWriteToken(thisObject);   // ';'

    fprintf(thisObject->fpXml, "</doStatement>\n");

    JackTokenizer_advance(thisObject->tokenizer);
}

// 'let' varName ('[' expression ']')? '=' expression ';'
void CompilationEngine_compileLet(CompilationEngine thisObject)
{
    fprintf(thisObject->fpXml, "<letStatement>\n");

    writeToken(thisObject->fpXml ,thisObject->tokenizer);   // 'let'
    advanceAndWriteToken(thisObject);   // varName
    advanceAndWriteToken(thisObject);   // '[' or '='
    if (isSymbolToken(thisObject, "[")) {
        JackTokenizer_advance(thisObject->tokenizer);
        CompilationEngine_compileExpression(thisObject);

        writeToken(thisObject->fpXml ,thisObject->tokenizer);   // ']'
        advanceAndWriteToken(thisObject);   // '='
    }

    JackTokenizer_advance(thisObject->tokenizer);
    CompilationEngine_compileExpression(thisObject);

    writeToken(thisObject->fpXml ,thisObject->tokenizer);   // ';'

    fprintf(thisObject->fpXml, "</letStatement>\n");

    JackTokenizer_advance(thisObject->tokenizer);
}

// 'while' '(' expression ')' '{' statements '}'
void CompilationEngine_compileWhile(CompilationEngine thisObject)
{
    fprintf(thisObject->fpXml, "<whileStatement>\n");

    writeToken(thisObject->fpXml ,thisObject->tokenizer);   // 'while'
    advanceAndWriteToken(thisObject);   // '('

    JackTokenizer_advance(thisObject->tokenizer);
    CompilationEngine_compileExpression(thisObject);

    writeToken(thisObject->fpXml ,thisObject->tokenizer);   // ')'
    advanceAndWriteToken(thisObject);   // '{'

    JackTokenizer_advance(thisObject->tokenizer);
    CompilationEngine_compileStatements(thisObject);

    writeToken(thisObject->fpXml ,thisObject->tokenizer);   // '}'

    fprintf(thisObject->fpXml, "</whileStatement>\n");

    JackTokenizer_advance(thisObject->tokenizer);
}

// 'return' expression? ';'
void CompilationEngine_compileReturn(CompilationEngine thisObject)
{
    fprintf(thisObject->fpXml, "<returnStatement>\n");

    writeToken(thisObject->fpXml ,thisObject->tokenizer);   // 'return'

    JackTokenizer_advance(thisObject->tokenizer);   // expression or ';'
    if (! isSymbolToken(thisObject, ";")) {
        CompilationEngine_compileExpression(thisObject);
    }
    writeToken(thisObject->fpXml ,thisObject->tokenizer);   // ';'

    fprintf(thisObject->fpXml, "</returnStatement>\n");

    JackTokenizer_advance(thisObject->tokenizer);
}

// 'if' '(' expression ')' '{' statements '}' ('else' '{' statements '}')?
void CompilationEngine_compileIf(CompilationEngine thisObject)
{
    fprintf(thisObject->fpXml, "<ifStatement>\n");

    writeToken(thisObject->fpXml ,thisObject->tokenizer);   // 'if'
    advanceAndWriteToken(thisObject);   // '('

    JackTokenizer_advance(thisObject->tokenizer);
    CompilationEngine_compileExpression(thisObject);

    writeToken(thisObject->fpXml ,thisObject->tokenizer);   // ')'
    advanceAndWriteToken(thisObject);   // '{'

    JackTokenizer_advance(thisObject->tokenizer);
    CompilationEngine_compileStatements(thisObject);

    writeToken(thisObject->fpXml ,thisObject->tokenizer);   // '}'

    JackTokenizer_advance(thisObject->tokenizer);   // 'else' or not
    if (isKeywordToken(thisObject, JACK_TOKENIZER_KEYWORD_ELSE)) {
        writeToken(thisObject->fpXml ,thisObject->tokenizer);   // 'else'
        advanceAndWriteToken(thisObject);   // '{'

        JackTokenizer_advance(thisObject->tokenizer);
        CompilationEngine_compileStatements(thisObject);

        writeToken(thisObject->fpXml ,thisObject->tokenizer);   // '}'

        JackTokenizer_advance(thisObject->tokenizer);
    }

    fprintf(thisObject->fpXml, "</ifStatement>\n");
}

// term (op term)*
// op: '+' | '-' | '*' | '/' | '&' | '|' | '<' | '>' | '='
void CompilationEngine_compileExpression(CompilationEngine thisObject)
{
    fprintf(thisObject->fpXml, "<expression>\n");

    CompilationEngine_compileTerm(thisObject);

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

        JackTokenizer_advance(thisObject->tokenizer);
        CompilationEngine_compileTerm(thisObject);
    }

    fprintf(thisObject->fpXml, "</expression>\n");
}

// integerConstant | stringConstant | keywordConstant | varName | varName '[' expression ']' | subroutineCall | '(' expression ')' | unaryOp term
void CompilationEngine_compileTerm(CompilationEngine thisObject)
{
    fprintf(thisObject->fpXml, "<term>\n");

    writeToken(thisObject->fpXml ,thisObject->tokenizer);   // term

    fprintf(thisObject->fpXml, "</term>\n");

    JackTokenizer_advance(thisObject->tokenizer);
}

// (expression (',' expression)*)?
void CompilationEngine_compileExpressionList(CompilationEngine thisObject)
{
    fprintf(thisObject->fpXml, "<expressionList>\n");

    if (! isSymbolToken(thisObject, ")")) { // expression is not ')'
        CompilationEngine_compileExpression(thisObject);

        while (isSymbolToken(thisObject, ",")) {
            writeToken(thisObject->fpXml ,thisObject->tokenizer);   // ','

            JackTokenizer_advance(thisObject->tokenizer);   // expression
            CompilationEngine_compileExpression(thisObject);
        }
    }

    fprintf(thisObject->fpXml, "</expressionList>\n");
}

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

完全版

ソースコード10/JackAnalyzer3/です。

ここではJack言語の文法のCompilationEngine_compileTermを実装しました。

下記で使えます。

test10.sh:L51-L67

cp -r ./nand2tetris/projects/10/Square 10/JackAnalyzer3/ && \
mkdir -p 10/JackAnalyzer3/Square/expect && \
mv 10/JackAnalyzer3/Square/*.xml 10/JackAnalyzer3/Square/expect/

# ...(省略)...

cd 10/JackAnalyzer3/

clang --std=c11 -Wall -Wextra -o JackAnalyzer main.c JackTokenizer.c JackTokenizerPrivate.c CompilationEngine.c

./JackAnalyzer Square

main.c (JackAnalyzerモジュール)

変更はありません。

$ diff 10/JackAnalyzer2/main.c 10/JackAnalyzer3/main.c 

JackTokenizerモジュール

変更はありません。

$ diff 10/JackAnalyzer2/JackTokenizer.h 10/JackAnalyzer3/JackTokenizer.h 
$ diff 10/JackAnalyzer2/JackTokenizer.c 10/JackAnalyzer3/JackTokenizer.c 
$ diff 10/JackAnalyzer2/JackTokenizerPrivate.h 10/JackAnalyzer3/JackTokenizerPrivate.h
$ diff 10/JackAnalyzer2/JackTokenizerPrivate.c 10/JackAnalyzer3/JackTokenizerPrivate.c

CompilationEngineモジュール

CompilationEngine_compileTerm関数を実装しました。

10/JackAnalyzer3/CompilationEngine.c:L330-L388

// integerConstant | stringConstant | keywordConstant | varName | varName '[' expression ']' | subroutineCall | '(' expression ')' | unaryOp term
// subroutineCall: subroutineName '(' expressionList ')' | (className | varName) '.' subroutineName '(' expressionList ')'
// unaryOp: '-' | '~'
void CompilationEngine_compileTerm(CompilationEngine thisObject)
{
    fprintf(thisObject->fpXml, "<term>\n");

    if (
        JackTokenizer_tokenType(thisObject->tokenizer) == JACK_TOKENIZER_TOKEN_TYPE_INT_CONST ||
        JackTokenizer_tokenType(thisObject->tokenizer) == JACK_TOKENIZER_TOKEN_TYPE_STRING_CONST ||
        JackTokenizer_tokenType(thisObject->tokenizer) == JACK_TOKENIZER_TOKEN_TYPE_KEYWORD
    ) { // integerConstant | stringConstant | keywordConstant
        writeToken(thisObject->fpXml ,thisObject->tokenizer);   // integerConstant or stringConstant or keywordConstant
        JackTokenizer_advance(thisObject->tokenizer);
    } else if (isSymbolToken(thisObject, "(")) {    // '(' expression ')'
        writeToken(thisObject->fpXml ,thisObject->tokenizer);   // '('

        JackTokenizer_advance(thisObject->tokenizer);
        CompilationEngine_compileExpression(thisObject);

        writeToken(thisObject->fpXml ,thisObject->tokenizer);   // ')'

        JackTokenizer_advance(thisObject->tokenizer);
    } else if (inSymbolListToken(thisObject, "-", "~", NULL)) { // unaryOp term
        writeToken(thisObject->fpXml ,thisObject->tokenizer);   // unaryOp

        JackTokenizer_advance(thisObject->tokenizer);
        CompilationEngine_compileTerm(thisObject);
    } else {    // varName | varName '[' expression ']' | subroutineCall
        writeToken(thisObject->fpXml ,thisObject->tokenizer);   // varName | subroutineName | className

        JackTokenizer_advance(thisObject->tokenizer);   // '[' or '(' or '.' or not
        if (isSymbolToken(thisObject, "[")) {
            writeToken(thisObject->fpXml ,thisObject->tokenizer);

            JackTokenizer_advance(thisObject->tokenizer);
            CompilationEngine_compileExpression(thisObject);

            writeToken(thisObject->fpXml ,thisObject->tokenizer);   // ']'

            JackTokenizer_advance(thisObject->tokenizer);
        } else if (inSymbolListToken(thisObject, "(", ".", NULL)) {
            writeToken(thisObject->fpXml ,thisObject->tokenizer);   // '(' or '.'

            if (isSymbolToken(thisObject, ".")) {
                advanceAndWriteToken(thisObject);   // subroutineName
                advanceAndWriteToken(thisObject);   // '('
            }
            JackTokenizer_advance(thisObject->tokenizer);
            CompilationEngine_compileExpressionList(thisObject);

            writeToken(thisObject->fpXml ,thisObject->tokenizer);   // ')'

            JackTokenizer_advance(thisObject->tokenizer);
        }
    }

    fprintf(thisObject->fpXml, "</term>\n");
}

まとめ

今回はJack言語の文法にしたがった構文解析器を実装しました。11章は今回の構文解析器を改造してコード生成を行えるようにしてコンパイラを完成させるようです。11章にはシンボルテーブルのテストが用意されていなかったりテストプログラムが目視テストだったりと大変そうですが時間があれば挑んでみたいです。

コンピュータシステムの理論と実装の7章と8章のバーチャルマシンを実装しました

前回の続きです。今回はコンピュータシステムの理論と実装(以下、nand2tetris本)の7章と8章のバーチャルマシンをC言語で実装してみました。

今回のコード

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

github.com

下記で動かせます。

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

概要

今回、実装したのは.vmファイルまたは.vmファイル群を入力として受け取り.asmファイルを生成するコマンドです。

f:id:nihma:20200613174708p:plain

バーチャルマシンはスタックベースです。長くなってしまうためここでは細かい仕様の説明は省略します。気になる場合はコンピュータシステムの理論と実装の7章と8章に詳しく記載されています。この記事の目的は自分が後から思い出すためのとっかかりを残すことであるため実装してみた内容の概要の記述にとどめます。

なお、実装は書籍が用意したテストプログラムに対応する形でインクリメンタルに進めました。そのため、次の5つのバージョンが存在し後になるほど高機能になっていきます。

  1. スタック算術コマンド に対応
  2. メモリアクセスコマンド に対応
  3. プログラムフローコマンド に対応
  4. 関数呼び出しコマンド(ブートストラップなし) に対応
  5. 関数呼び出しコマンド(完全版) に対応

7章(スタック操作)

スタック算術コマンド

ソースコード07/VMtranslator1/です。

ここでは下記のコマンドに対応しました。

コマンド 概要
add pop y, pop x, push (x + y)
sub pop y, pop x, push (x - y)
neg pop y, push (-y)
eq pop y, pop x, push (x == y ? -1(true/0xFFFF) : 0(false/0x0000))
gt pop y, pop x, push (x > y ? -1(true/0xFFFF) : 0(false/0x0000))
lt pop y, pop x, push (x < y ? -1(true/0xFFFF) : 0(false/0x0000))
and pop y, pop x, push (x and y)
or pop y, pop x, push (x or y)
not pop y, push (not y)
push constant index push index

下記で使えます。

test07.sh:L3-L16

cp ./nand2tetris/projects/07/StackArithmetic/SimpleAdd/* 07/VMtranslator1/

# ...(省略)...

cd 07/VMtranslator1/

clang --std=c11 -Wall -Wextra -o VMtranslator main.c Parser.c ParserPrivate.c CodeWriter.c CodeWriterPrivate.c

./VMtranslator SimpleAdd.vm 

main.c

コマンドのエントリポイントです。
main.cではコマンド引数の解析、ParserモジュールおよびCodeモジュールを用いたアセンブラへの変換処理を行います。main.cの中で使う関数はmain.c内で下記のように定義しました。

07/VMtranslator1/main.c:L15-L21

int translateByVmDir(DIR *dpVm, char *vmDirName);
int translateByVmFile(char *vmFileName);
bool isVmFileName(char *vmFileName);
void createVmFilePath(char *vmDirName, char *vmFileName, char *vmFilePath);
void createAsmFilePathFromDirName(char *vmDirName, char *asmFilePath);
void createAsmFilePathFromVmFileName(char *vmFileName, char *asmFilePath);
void translate(Parser parser, CodeWriter codeWriter);

コマンド引数には.vmファイルまたは.vmファイルを複数含むディレクトリいづれかを指定できます。ただし複数の.vmファイルに対応するのは最後になるためここでは1ファイルのみ処理するようにしました。

ディレクトリが指定された場合の処理は次の通りです。.asmファイルを作成し.vmファイルが見つかったら変換処理(translate関数)に引き渡しています。ただしファイル数分ループしていますが1ファイル処理したらbreakで抜けるようにしてあります。

07/VMtranslator1/main.c:L54-L125

int translateByVmDir(DIR *dpVm, char *vmDirName)
{
    char asmFilePath[VM_DIRNAME_MAX_LENGTH + ASM_FILENAME_MAX_LENGTH + 1];
    char vmFilePath[VM_DIRNAME_MAX_LENGTH + VM_FILENAME_MAX_LENGTH + 1];
    int vmFileNum = 0;
    FILE *fpVm, *fpAsm;
    struct dirent *dEntry;
    Parser parser;
    CodeWriter codeWriter;

    if (strlen(vmDirName) > VM_DIRNAME_MAX_LENGTH) {
        fprintf(
            stderr, 
            "Error: Vm dirname max size is invalid. Max size is %d. (%s) is %lu\n", 
            VM_DIRNAME_MAX_LENGTH, 
            vmDirName,
            strlen(vmDirName)
        );
        return 1;
    }

    createAsmFilePathFromDirName(vmDirName, asmFilePath);
    if ((fpAsm = fopen(asmFilePath, "w")) == NULL) {
        fprintf(stderr, "Error: asm file not open (%s)\n", asmFilePath);
        return 1;
    }
    codeWriter = CodeWriter_init(fpAsm);

    while ((dEntry = readdir(dpVm)) != NULL) {
        char *vmFileName = dEntry->d_name;
        if (dEntry->d_type != DT_REG) {  // not file
            continue;
        }
        if (! isVmFileName(vmFileName)) {
            continue;
        }
        if (strlen(vmFileName) > VM_FILENAME_MAX_LENGTH) {
            fprintf(
                stderr, 
                "Skip: Vm filename max size is invalid. Max size is %d. (%s) is %lu\n", 
                VM_FILENAME_MAX_LENGTH, 
                vmFileName,
                strlen(vmFileName)
            );
            continue;
        }
        vmFileNum++;

        createVmFilePath(vmDirName, vmFileName, vmFilePath);
        if ((fpVm = fopen(vmFilePath, "r")) == NULL) {
            fprintf(stderr, "Error: vm file not found (%s)\n", vmFilePath);
            CodeWriter_close(codeWriter);
            return 1;
        }
        CodeWriter_setFileName(codeWriter, vmFileName);

        parser = Parser_init(fpVm);
        translate(parser, codeWriter);

        fclose(fpVm);

        break;
    }
    CodeWriter_close(codeWriter);

    if (vmFileNum == 0) {
        fprintf(stderr, "Error: vm file not found\n");
        return 1;
    }

    return 0;
}

ファイルが指定された場合の処理は次の通りです。.asmファイルを作成し変換処理(translate関数)に引き渡しています。

07/VMtranslator1/main.c:L127-L171

int translateByVmFile(char *vmFileName)
{
    char asmFilePath[ASM_FILENAME_MAX_LENGTH];
    FILE *fpVm, *fpAsm;
    Parser parser;
    CodeWriter codeWriter;

    if (! isVmFileName(vmFileName)) {
        fprintf(stderr, "Error: Vm filename extension(.vm) is invalid. (%s)\n", vmFileName);
        return 1;
    }

    if (strlen(vmFileName) > VM_FILENAME_MAX_LENGTH) {
        fprintf(
            stderr, 
            "Error: Vm filename max size is invalid. Max size is %d. (%s) is %lu\n", 
            VM_FILENAME_MAX_LENGTH, 
            vmFileName,
            strlen(vmFileName)
        );
        return 1;
    }

    if ((fpVm = fopen(vmFileName, "r")) == NULL) {
        fprintf(stderr, "Error: vm file not found (%s)\n", vmFileName);
        return 1;
    }
    parser = Parser_init(fpVm);

    createAsmFilePathFromVmFileName(vmFileName, asmFilePath);
    if ((fpAsm = fopen(asmFilePath, "w")) == NULL) {
        fprintf(stderr, "Error: asm file not open (%s)\n", asmFilePath);
        fclose(fpVm);
        return 1;
    }
    codeWriter = CodeWriter_init(fpAsm);

    CodeWriter_setFileName(codeWriter, vmFileName);
    translate(parser, codeWriter);

    CodeWriter_close(codeWriter);
    fclose(fpVm);

    return 0;
}

変換処理の実装は下記の通りです。.vmファイルをParserモジュールでパースしつつcommandTypeに応じてCodeWriterモジュールで対応するアセンブリ処理を.asmファイルに追記しています。

07/VMtranslator1/main.c:L219-L239

void translate(Parser parser, CodeWriter codeWriter)
{
    char command[PARSER_COMMAND_MAX_LENGTH + 1];
    char segment[PARSER_ARG1_MAX_LENGTH + 1];

    while (Parser_hasMoreCommands(parser)) {
        Parser_advance(parser);
        switch (Parser_commandType(parser)) {
        case PARSER_COMMAND_TYPE_C_ARITHMETIC:
            Parser_arg1(parser, command);
            CodeWriter_writeArithmetic(codeWriter, command);
            break;
        case PARSER_COMMAND_TYPE_C_PUSH:
            Parser_arg1(parser, segment);
            CodeWriter_writePushPop(codeWriter, Parser_commandType(parser), segment, Parser_arg2(parser));
            break;
        default:
            break;
        }
    }
}

Parserモジュール

.vmファイルをパースするためのモジュールです。
main.cで利用する関数はParser.hで下記のように定義しました。parser構造体はtypedefして定義はParser.c内に隠蔽するようにしてオブジェクトとして使うようにしました。それぞれの実装はParser.cで行いました。

07/VMtranslator1/Parser.h:L11-L23

typedef enum {
    PARSER_COMMAND_TYPE_C_ARITHMETIC = 1,
    PARSER_COMMAND_TYPE_C_PUSH
} Parser_CommandType;

typedef struct parser * Parser;

Parser Parser_init(FILE *fpVm);
bool Parser_hasMoreCommands(Parser thisObject);
void Parser_advance(Parser thisObject);
Parser_CommandType Parser_commandType(Parser thisObject);
void Parser_arg1(Parser thisObject, char *arg1);
int Parser_arg2(Parser thisObject);

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

07/VMtranslator1/ParserPrivate.h:L7-L16

bool isSpace(FILE *fpVm);
bool isComment(FILE *fpVm);
bool isEndOfFile(FILE *fpVm);
bool isEndOfLine(FILE *fpVm);
bool isToken(FILE *fpVm);
void skipSpaces(FILE *fpVm);
void skipEndOFLines(FILE *fpVm);
void skipComment(FILE *fpVm);
void moveNextAdvance(FILE *fpVm);
void getToken(FILE *fpVm, char *token);

各コマンドごとの処理は下記の通りです。

07/VMtranslator1/Parser.c:L55-L86

Parser_CommandType Parser_commandType(Parser thisObject)
{
    IF_CMP_RET(thisObject->command,  "add", PARSER_COMMAND_TYPE_C_ARITHMETIC);
    IF_CMP_RET(thisObject->command,  "sub", PARSER_COMMAND_TYPE_C_ARITHMETIC);   
    IF_CMP_RET(thisObject->command,  "neg", PARSER_COMMAND_TYPE_C_ARITHMETIC);
    IF_CMP_RET(thisObject->command,   "eq", PARSER_COMMAND_TYPE_C_ARITHMETIC);
    IF_CMP_RET(thisObject->command,   "gt", PARSER_COMMAND_TYPE_C_ARITHMETIC);
    IF_CMP_RET(thisObject->command,   "lt", PARSER_COMMAND_TYPE_C_ARITHMETIC);
    IF_CMP_RET(thisObject->command,  "and", PARSER_COMMAND_TYPE_C_ARITHMETIC);
    IF_CMP_RET(thisObject->command,   "or", PARSER_COMMAND_TYPE_C_ARITHMETIC);
    IF_CMP_RET(thisObject->command,  "not", PARSER_COMMAND_TYPE_C_ARITHMETIC);
    IF_CMP_RET(thisObject->command, "push", PARSER_COMMAND_TYPE_C_PUSH);

    return -1;
}

void Parser_arg1(Parser thisObject, char *arg1)
{
    if (Parser_commandType(thisObject) == PARSER_COMMAND_TYPE_C_ARITHMETIC) {
        strcpy(arg1, thisObject->command);
    } else if (Parser_commandType(thisObject) == PARSER_COMMAND_TYPE_C_PUSH) {
        strcpy(arg1, thisObject->arg1);
    }
}

int Parser_arg2(Parser thisObject)
{
    if (Parser_commandType(thisObject) == PARSER_COMMAND_TYPE_C_PUSH) {
        return atoi(thisObject->arg2);
    }
    return -1;
}

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

CodeWriterモジュール

コマンドに対応するアセンブリ処理を.asmファイルに追記するためのモジュールです。
main.cで利用する関数はCodeWriter.hで下記のように定義しました。code_writer構造体はtypedefして定義はCodeWriter.c内に隠蔽するようにしてオブジェクトとして使うようにしました。それぞれの実装はCodeWriter.cで行いました。

07/VMtranslator1/CodeWriter.h:L9-L20

typedef struct code_writer * CodeWriter;

CodeWriter CodeWriter_init(FILE *fpAsm);
void CodeWriter_setFileName(CodeWriter thisObject, char *fileName);
void CodeWriter_writeArithmetic(CodeWriter thisObject, char *command);
void CodeWriter_writePushPop(
    CodeWriter thisObject,
    Parser_CommandType command,
    char *segment,
    int index
);
void CodeWriter_close(CodeWriter thisObject);

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

07/VMtranslator1/CodeWriterPrivate.h:L8-L16

void fputslist(FILE* fp, ...);

void writeArithmethicAdd(FILE* fpAsm);
void writeArithmethicSub(FILE* fpAsm);
void writeArithmethicNeg(FILE* fpAsm);
void writeArithmethicEq(FILE* fpAsm, char *skipLabel);
void writeArithmethicGt(FILE* fpAsm, char *skipLabel);
void writeArithmethicLt(FILE* fpAsm, char *skipLabel);
void writeArithmethicAnd(FILE* fpAsm);
void writeArithmethicOr(FILE* fpAsm);
void writeArithmethicNot(FILE* fpAsm);

void writePushConstant(FILE* fpAsm, int index);

長くなってしまうため詳細は省きますが例えばaddの実装は下記の通り、対応するアセンブリ処理をfputsで追記しているだけです。fputslist関数は自作のfputsを連続して呼び出す関数です。

07/VMtranslator1/CodeWriterPrivate.c:L11-

// pop y, pop x, push (x + y)
void writeArithmethicAdd(FILE* fpAsm) { writeArithmethicBinaryOperation(fpAsm, "D+M"); }

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

// Binary operation (M <- x, D <- y)
void writeArithmethicBinaryOperation(FILE* fpAsm, char *comp)
{
    fputslist(
        fpAsm,
        "// BinaryOperation ", comp, "\n",
        // Memory[SP] -= 1
        "@SP\n",
        "M=M-1\n",
        // y <- Memory[Memory[SP]]
        "A=M\n",
        "D=M\n",
        // Memory[SP] -= 1
        "@SP\n",
        "M=M-1\n",
        // x <- Memory[Memory[SP]]
        "A=M\n",
        // Memory[Memory[SP]] <- comp
        "M=", comp, "\n",
        // Memory[SP] += 1
        "@SP\n",
        "M=M+1\n",
        NULL
    );
}

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

void fputslist(FILE* fp, ...)
{
    char* string;

    va_list args;
    va_start(args, fp);

    while ((string = va_arg(args, char*)) != NULL) {
        fputs(string, fp);
    }

    va_end(args);
}

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

メモリアクセスコマンド

ソースコード07/VMtranslator2/です。

ここでは下記のコマンドに対応しました。

コマンド 概要
push local index push Memory[Memory[LCL]+index]
pop local index pop Memory[Memory[LCL]+index]
push argument index push Memory[Memory[ARG]+index]
pop argument index pop Memory[Memory[ARG]+index]
push this index push Memory[Memory[THIS]+index]
pop this index pop Memory[Memory[THIS]+index]
push that index push Memory[Memory[THAT]+index]
pop that index pop Memory[Memory[THAT]+index]
push pointer index push R{3+index}
pop pointer index pop R{3+index}
push temp index push R{5+index}
pop temp index pop R{5+index}
push static index push Memory[vmFileName.index]
pop static index pop Memory[vmFileName.index]

下記で使えます。

test07.sh:L20-L40

cp ./nand2tetris/projects/07/MemoryAccess/BasicTest/* 07/VMtranslator2/

# ...(省略)...

cd 07/VMtranslator2/

clang --std=c11 -Wall -Wextra -o VMtranslator main.c Parser.c ParserPrivate.c CodeWriter.c CodeWriterPrivate.c

# ...(省略)...
./VMtranslator BasicTest.vm 

main.c

popに対応しました。

$ diff -r 07/VMtranslator1/main.c 07/VMtranslator2/main.c 
231a232
>         case PARSER_COMMAND_TYPE_C_POP:

Parserモジュール

popに対応しました。

$ diff -r 07/VMtranslator1/Parser.h 07/VMtranslator2/Parser.h 
13c13,14
<     PARSER_COMMAND_TYPE_C_PUSH
---
>     PARSER_COMMAND_TYPE_C_PUSH,
>     PARSER_COMMAND_TYPE_C_POP
$ diff -r 07/VMtranslator1/Parser.c 07/VMtranslator2/Parser.c
40a41
>     case PARSER_COMMAND_TYPE_C_POP:
66a68
>     IF_CMP_RET(thisObject->command,  "pop", PARSER_COMMAND_TYPE_C_POP);
75c77
<     } else if (Parser_commandType(thisObject) == PARSER_COMMAND_TYPE_C_PUSH) {
---
>     } else {
82c84,85
<     if (Parser_commandType(thisObject) == PARSER_COMMAND_TYPE_C_PUSH) {
---
>     if (Parser_commandType(thisObject) == PARSER_COMMAND_TYPE_C_PUSH ||
>         Parser_commandType(thisObject) == PARSER_COMMAND_TYPE_C_POP) {
$ diff -r 07/VMtranslator1/ParserPrivate.h 07/VMtranslator2/ParserPrivate.h
$ diff -r 07/VMtranslator1/ParserPrivate.c 07/VMtranslator2/ParserPrivate.c

CodeWriterモジュール

constant以外のpushpopに対応しました。

$ diff -w -r 07/VMtranslator1/CodeWriter.h 07/VMtranslator2/CodeWriter.h 
$ diff -w -r 07/VMtranslator1/CodeWriter.c 07/VMtranslator2/CodeWriter.c
57,60c57,78
<     if (command == PARSER_COMMAND_TYPE_C_PUSH) {
<         if (strcmp(segment, "constant") == 0) {
<             writePushConstant(thisObject->fpAsm, index);
<         }
---
>     switch (command) {
>     case PARSER_COMMAND_TYPE_C_PUSH:
>              if (strcmp(segment, "constant") == 0) writePushConstant(thisObject->fpAsm, index);
>         else if (strcmp(segment,    "local") == 0) writePushLocal(thisObject->fpAsm, index);
>         else if (strcmp(segment, "argument") == 0) writePushArgument(thisObject->fpAsm, index);
>         else if (strcmp(segment,     "this") == 0) writePushThis(thisObject->fpAsm, index);
>         else if (strcmp(segment,     "that") == 0) writePushThat(thisObject->fpAsm, index);
>         else if (strcmp(segment,  "pointer") == 0) writePushPointer(thisObject->fpAsm, index);
>         else if (strcmp(segment,     "temp") == 0) writePushTemp(thisObject->fpAsm, index);
>         else if (strcmp(segment,   "static") == 0) writePushStatic(thisObject->fpAsm, thisObject->vmFileName, index);
>         break;
>     case PARSER_COMMAND_TYPE_C_POP:
>              if (strcmp(segment,    "local") == 0) writePopLocal(thisObject->fpAsm, index);
>         else if (strcmp(segment, "argument") == 0) writePopArgument(thisObject->fpAsm, index);
>         else if (strcmp(segment,     "this") == 0) writePopThis(thisObject->fpAsm, index);
>         else if (strcmp(segment,     "that") == 0) writePopThat(thisObject->fpAsm, index);
>         else if (strcmp(segment,  "pointer") == 0) writePopPointer(thisObject->fpAsm, index);
>         else if (strcmp(segment,     "temp") == 0) writePopTemp(thisObject->fpAsm, index);
>         else if (strcmp(segment,   "static") == 0) writePopStatic(thisObject->fpAsm, thisObject->vmFileName, index);
>         break;
>     default:
>         break;
$ diff -w -r 07/VMtranslator1/CodeWriterPrivate.h 07/VMtranslator2/CodeWriterPrivate.h
18a19,32
> void writePushLocal(FILE* fpAsm, int index);
> void writePopLocal(FILE* fpAsm, int index);
> void writePushArgument(FILE* fpAsm, int index);
> void writePopArgument(FILE* fpAsm, int index);
> void writePushThis(FILE* fpAsm, int index);
> void writePopThis(FILE* fpAsm, int index);
> void writePushThat(FILE* fpAsm, int index);
> void writePopThat(FILE* fpAsm, int index);
> void writePushPointer(FILE* fpAsm, int index);
> void writePopPointer(FILE* fpAsm, int index);
> void writePushTemp(FILE* fpAsm, int index);
> void writePopTemp(FILE* fpAsm, int index);
> void writePushStatic(FILE* fpAsm, char *vmFileName, int index);
> void writePopStatic(FILE* fpAsm, char *vmFileName, int index);
$ diff -w -r 07/VMtranslator1/CodeWriterPrivate.c 07/VMtranslator2/CodeWriterPrivate.c
1a2
> #include "CodeWriter.h"
4c5,6
< #define PUSH_CONSTANT_INDEX_MAX_DIGIT (6)
---
> #define PUSH_POP_INDEX_MAX_DIGIT   (6)
> #define PUSH_POP_SYMBOL_MAX_LENGTH (CODE_WRITER_VM_FILENAME_MAX_LENGTH + PUSH_POP_INDEX_MAX_DIGIT + 1)
9a12,16
> void writePushSymbol(FILE* fpAsm, char *symbol, int index);
> void writePopSymbol(FILE* fpAsm, char *symbol, int index);
> void writePushRegister(FILE* fpAsm, int registerNumber);
> void writePopRegister(FILE* fpAsm, int registerNumber);
> 
34c41
<     char indexStr[PUSH_CONSTANT_INDEX_MAX_DIGIT + 1];
---
>     char indexStr[PUSH_POP_INDEX_MAX_DIGIT + 1];
52a60,131
> // push Memory[Memory[LCL]+index]
> void writePushLocal(FILE* fpAsm, int index) { writePushSymbol(fpAsm, "LCL", index); }
> // pop Memory[Memory[LCL]+index]
> void writePopLocal(FILE* fpAsm, int index)  { writePopSymbol(fpAsm, "LCL", index); }
> 
> // push Memory[Memory[ARG]+index]
> void writePushArgument(FILE* fpAsm, int index) { writePushSymbol(fpAsm, "ARG", index); }
> // pop Memory[Memory[ARG]+index]
> void writePopArgument(FILE* fpAsm, int index)  { writePopSymbol(fpAsm, "ARG", index); }
> 
> // push Memory[Memory[THIS]+index]
> void writePushThis(FILE* fpAsm, int index) { writePushSymbol(fpAsm, "THIS", index); }
> // pop Memory[Memory[THIS]+index]
> void writePopThis(FILE* fpAsm, int index)  { writePopSymbol(fpAsm, "THIS", index); }
> 
> // push Memory[Memory[THAT]+index]
> void writePushThat(FILE* fpAsm, int index) { writePushSymbol(fpAsm, "THAT", index); }
> // pop Memory[Memory[THAT]+index]
> void writePopThat(FILE* fpAsm, int index)  { writePopSymbol(fpAsm, "THAT", index); }
> 
> // push R{3+index}
> void writePushPointer(FILE* fpAsm, int index) { writePushRegister(fpAsm, 3 + index); }
> // pop R{3+index}
> void writePopPointer(FILE* fpAsm, int index)  { writePopRegister(fpAsm, 3 + index); }
> 
> // push R{5+index}
> void writePushTemp(FILE* fpAsm, int index) { writePushRegister(fpAsm, 5 + index); }
> // pop R{5+index}
> void writePopTemp(FILE* fpAsm, int index)  { writePopRegister(fpAsm, 5 + index); }
> 
> // push Memory[vmFileName.index]
> void writePushStatic(FILE* fpAsm, char *vmFileName, int index)
> {
>     char symbol[PUSH_POP_SYMBOL_MAX_LENGTH + 1];
>     sprintf(symbol, "%s.%d", vmFileName, index);
> 
>     fputslist(
>         fpAsm,
>         // Memory[Memory[SP]] <- Memory[symbol]
>         "@", symbol, "\n",
>         "D=M\n",
>         "@SP\n",
>         "A=M\n",
>         "M=D\n",
>         // Memory[SP] += 1
>         "@SP\n",
>         "M=M+1\n",
>         NULL
>     );
> }
> 
> // pop Memory[vmFileName.index]
> void writePopStatic(FILE* fpAsm, char *vmFileName, int index)
> {
>     char symbol[PUSH_POP_SYMBOL_MAX_LENGTH + 1];
>     sprintf(symbol, "%s.%d", vmFileName, index);
> 
>     fputslist(
>         fpAsm,
>         // Memory[SP] -= 1
>         "@SP\n",
>         "M=M-1\n",
>         // Memory[symbol] <- Memory[Memory[SP]]
>         "@SP\n",
>         "A=M\n",
>         "D=M\n",
>         "@", symbol, "\n",
>         "M=D\n",
>         NULL
>     );
> }
> 
137a217,316
> // push Memory[Memory[Symbol]+index]
> void writePushSymbol(FILE* fpAsm, char *symbol, int index)
> {
>     char indexStr[PUSH_POP_INDEX_MAX_DIGIT + 1];
>     sprintf(indexStr, "%d", index);
> 
>     fputslist(
>         fpAsm,
>         "// push symbol ", symbol, " ", indexStr, "\n",
>         // R13 <- Memory[Symbol]+index
>         "@", indexStr, "\n",
>         "D=A\n",
>         "@", symbol, "\n",
>         "D=D+M\n",
>         "@R13\n",
>         "M=D\n",
>         // Memory[Memory[SP]] <- Memory[R13] 
>         "A=M\n",
>         "D=M\n",
>         "@SP\n",
>         "A=M\n",
>         "M=D\n",
>         // Memory[SP] += 1
>         "@SP\n",
>         "M=M+1\n",
>         NULL
>     );
> }
> 
> // pop Memory[Memory[Symbol]+index]
> void writePopSymbol(FILE* fpAsm, char *symbol, int index)
> {
>     char indexStr[PUSH_POP_INDEX_MAX_DIGIT + 1];
>     sprintf(indexStr, "%d", index);
> 
>     fputslist(
>         fpAsm,
>         // Memory[SP] -= 1
>         "@SP\n",
>         "M=M-1\n",
>         // R13 <- Memory[Symbol]+index
>         "@", indexStr, "\n",
>         "D=A\n",
>         "@", symbol, "\n",
>         "D=D+M\n",
>         "@R13\n",
>         "M=D\n",
>         // Memory[R13] <- Memory[Memory[SP]]
>         "@SP\n",
>         "A=M\n",
>         "D=M\n",
>         "@R13\n",
>         "A=M\n",
>         "M=D\n",
>         NULL
>     );
> }
> 
> // push R{registerNumber}
> void writePushRegister(FILE* fpAsm, int registerNumber)
> {
>     char symbol[8];
>     sprintf(symbol, "R%d", registerNumber);
> 
>     fputslist(
>         fpAsm,
>         // Memory[Memory[SP]] <- register
>         "@", symbol, "\n",
>         "D=M\n",
>         "@SP\n",
>         "A=M\n",
>         "M=D\n",
>         // Memory[SP] += 1
>         "@SP\n",
>         "M=M+1\n",
>         NULL
>     );
> }
> 
> // pop R{registerNumber}
> void writePopRegister(FILE* fpAsm, int registerNumber)
> {
>     char symbol[8];
>     sprintf(symbol, "R%d", registerNumber);
> 
>     fputslist(
>         fpAsm,
>         // Memory[SP] -= 1
>         "@SP\n",
>         "M=M-1\n",
>         // register <- Memory[Memory[SP]]
>         "@SP\n",
>         "A=M\n",
>         "D=M\n",
>         "@", symbol, "\n",
>         "M=D\n",
>         NULL
>     );
> }
> 

8章(プログラム制御)

プログラムフローコマンド

ソースコード08/VMtranslator3/です。

ここでは下記のコマンドに対応しました。

コマンド 概要
label xxx (vmFileName$xxx)
goto xxx jump to vmFileName$xxx
if-goto xxx pop y, if y != 0(false/0x0000) then jump to vmFileName$xxx

下記で使えます。

test08.sh:L8-L31

cp ./nand2tetris/projects/08/ProgramFlow/BasicLoop/* 08/VMtranslator3/

# ...(省略)...

cd 08/VMtranslator3/

clang --std=c11 -Wall -Wextra -o VMtranslator main.c Parser.c ParserPrivate.c CodeWriter.c CodeWriterPrivate.c

# ...(省略)...
./VMtranslator BasicLoop.vm 

main.c

label, goto, if-gotoに対応しました。

$ diff -w -r 07/VMtranslator2/main.c 08/VMtranslator3/main.c 
235a236,247
>         case PARSER_COMMAND_TYPE_C_LABEL:
>             Parser_arg1(parser, segment);
>             CodeWriter_writeLabel(codeWriter, segment);
>             break;
>         case PARSER_COMMAND_TYPE_C_GOTO:
>             Parser_arg1(parser, segment);
>             CodeWriter_writeGoto(codeWriter, segment);
>             break;
>         case PARSER_COMMAND_TYPE_C_IF:
>             Parser_arg1(parser, segment);
>             CodeWriter_writeIf(codeWriter, segment);
>             break;

Parserモジュール

label, goto, if-gotoに対応しました。

$ diff -w -r 07/VMtranslator2/Parser.h 08/VMtranslator3/Parser.h
7c7
< #define PARSER_COMMAND_MAX_LENGTH (4)
---
> #define PARSER_COMMAND_MAX_LENGTH (8)
14c14,17
<     PARSER_COMMAND_TYPE_C_POP
---
>     PARSER_COMMAND_TYPE_C_POP,
>     PARSER_COMMAND_TYPE_C_LABEL,
>     PARSER_COMMAND_TYPE_C_GOTO,
>     PARSER_COMMAND_TYPE_C_IF
$ diff -w -r 07/VMtranslator2/Parser.c 08/VMtranslator3/Parser.c
46a47,53
>     case PARSER_COMMAND_TYPE_C_LABEL:
>     case PARSER_COMMAND_TYPE_C_GOTO:
>     case PARSER_COMMAND_TYPE_C_IF:
>         skipSpaces(thisObject->fpVm);
>         getToken(thisObject->fpVm, thisObject->arg1);
>         strcpy(thisObject->arg2, "");
>         break;
68a76,78
>     IF_CMP_RET(thisObject->command,   "label", PARSER_COMMAND_TYPE_C_LABEL);
>     IF_CMP_RET(thisObject->command,    "goto", PARSER_COMMAND_TYPE_C_GOTO);
>     IF_CMP_RET(thisObject->command, "if-goto", PARSER_COMMAND_TYPE_C_IF);
$ diff -w -r 07/VMtranslator2/ParserPrivate.h 08/VMtranslator3/ParserPrivate.h
$ diff -w -r 07/VMtranslator2/ParserPrivate.c 08/VMtranslator3/ParserPrivate.c

CodeWriterモジュール

label, goto, if-gotoに対応しました。

$ diff -w -r 07/VMtranslator2/CodeWriter.h 08/VMtranslator3/CodeWriter.h
19a20,22
> void CodeWriter_writeLabel(CodeWriter thisObject, char *label);
> void CodeWriter_writeGoto(CodeWriter thisObject, char *label);
> void CodeWriter_writeIf(CodeWriter thisObject, char *label);
$ diff -w -r 07/VMtranslator2/CodeWriter.c 08/VMtranslator3/CodeWriter.c
5a6
> #define LABEL_SYMBOL_MAX_LENGTH (CODE_WRITER_VM_FILENAME_MAX_LENGTH + 24)
81a83,129
> void CodeWriter_writeLabel(CodeWriter thisObject, char *label)
> {
>     char labelSymbol[LABEL_SYMBOL_MAX_LENGTH + 1];
>     sprintf(labelSymbol, "%s$%s", thisObject->vmFileName, label);
> 
>     fputslist(
>         thisObject->fpAsm,
>         "(", labelSymbol, ")\n",
>         NULL
>     );
> }
> 
> void CodeWriter_writeGoto(CodeWriter thisObject, char *label)
> {
>     char labelSymbol[LABEL_SYMBOL_MAX_LENGTH + 1];
>     sprintf(labelSymbol, "%s$%s", thisObject->vmFileName, label);
> 
>     fputslist(
>         thisObject->fpAsm,
>         // goto labelSymbol
>         "@", labelSymbol, "\n",
>         "0;JMP\n",
>         NULL
>     );
> }
> 
> void CodeWriter_writeIf(CodeWriter thisObject, char *label)
> {
>     char labelSymbol[LABEL_SYMBOL_MAX_LENGTH + 1];
>     sprintf(labelSymbol, "%s$%s", thisObject->vmFileName, label);
> 
>     fputslist(
>         thisObject->fpAsm,
>         // Memory[SP] -= 1
>         "@SP\n",
>         "M=M-1\n",
>         // Register <- Memory[Memory[SP]]
>         "@SP\n",
>         "A=M\n",
>         "D=M\n",
>         // if jump(Register != 0) then goto labelSymbol
>         "@", labelSymbol, "\n",
>         "D;JNE\n",
>         NULL
>     );
> }
> 
$ diff -w -r 07/VMtranslator2/CodeWriterPrivate.h 08/VMtranslator3/CodeWriterPrivate.h
$ diff -w -r 07/VMtranslator2/CodeWriterPrivate.c 08/VMtranslator3/CodeWriterPrivate.c

関数呼び出しコマンド(ブートストラップなし)

ソースコード08/VMtranslator4/です。

ここでは下記のコマンドに対応しました。

コマンド 概要
function f n (f), push 0 repeat n
return 各種レジスタ復元, goto リターンアドレス

下記で使えます。

test08.sh:L40-L64

cp ./nand2tetris/projects/08/FunctionCalls/SimpleFunction/* 08/VMtranslator4/

# ...(省略)...

cd 08/VMtranslator4/

clang --std=c11 -Wall -Wextra -o VMtranslator main.c Parser.c ParserPrivate.c CodeWriter.c CodeWriterPrivate.c

# ...(省略)...
./VMtranslator SimpleFunction.vm 

main.c

function, returnに対応しました。

$ diff -w -r 08/VMtranslator3/main.c 08/VMtranslator4/main.c 
247a248,254
>         case PARSER_COMMAND_TYPE_C_RETURN:
>             CodeWriter_writeReturn(codeWriter);
>             break;
>         case PARSER_COMMAND_TYPE_C_FUNCTION:
>             Parser_arg1(parser, segment);
>             CodeWriter_writeFunction(codeWriter, segment, Parser_arg2(parser));
>             break;

Parserモジュール

function, returnに対応しました。

$ diff -w -r 08/VMtranslator3/Parser.h 08/VMtranslator4/Parser.h
7,8c7,8
< #define PARSER_COMMAND_MAX_LENGTH (8)
< #define PARSER_ARG1_MAX_LENGTH    (8)
---
> #define PARSER_COMMAND_MAX_LENGTH (16)
> #define PARSER_ARG1_MAX_LENGTH    (32)
17c17,19
<     PARSER_COMMAND_TYPE_C_IF
---
>     PARSER_COMMAND_TYPE_C_IF,
>     PARSER_COMMAND_TYPE_C_FUNCTION,
>     PARSER_COMMAND_TYPE_C_RETURN
$ diff -w -r 08/VMtranslator3/Parser.c 08/VMtranslator4/Parser.c
41a42
>     case PARSER_COMMAND_TYPE_C_FUNCTION:
53a55
>     case PARSER_COMMAND_TYPE_C_RETURN:
78a81,82
>     IF_CMP_RET(thisObject->command, "function", PARSER_COMMAND_TYPE_C_FUNCTION);
>     IF_CMP_RET(thisObject->command,   "return", PARSER_COMMAND_TYPE_C_RETURN);
95c99,100
<         Parser_commandType(thisObject) == PARSER_COMMAND_TYPE_C_POP) {
---
>         Parser_commandType(thisObject) == PARSER_COMMAND_TYPE_C_POP ||
>         Parser_commandType(thisObject) == PARSER_COMMAND_TYPE_C_FUNCTION) {
$ diff -w -r 08/VMtranslator3/ParserPrivate.h 08/VMtranslator4/ParserPrivate.h 
$ diff -w -r 08/VMtranslator3/ParserPrivate.c 08/VMtranslator4/ParserPrivate.c

CodeWriterモジュール

function, returnに対応しました。

$ diff -w -r 08/VMtranslator3/CodeWriter.h 08/VMtranslator4/CodeWriter.h 
22a23,24
> void CodeWriter_writeReturn(CodeWriter thisObject);
> void CodeWriter_writeFunction(CodeWriter thisObject, char *functionName, int numLocals);
$ diff -w -r 08/VMtranslator3/CodeWriter.c 08/VMtranslator4/CodeWriter.c
129a130,218
> void CodeWriter_writeReturn(CodeWriter thisObject)
> {
>     fputslist(
>         thisObject->fpAsm,
>         "// return\n",
>         // Memory[R13] <- Memory[LCL]
>         "@LCL\n",
>         "D=M\n",
>         "@R13\n",
>         "M=D\n",
>         // Memory[R14] <- Memory[Memory[R13]-5]
>         "@5\n",
>         "D=A\n",
>         "@R13\n",
>         "A=M-D\n",
>         "D=M\n",
>         "@R14\n",
>         "M=D\n",
>         // Memory[SP] -= 1
>         "@SP\n",
>         "M=M-1\n",
>         // Memory[Memory[ARG]] <- Memory[Memory[SP]]
>         "@SP\n",
>         "A=M\n",
>         "D=M\n",
>         "@ARG\n",
>         "A=M\n",
>         "M=D\n",
>         // Memory[SP] <- Memory[ARG] + 1
>         "@ARG\n",
>         "D=M+1\n",
>         "@SP\n",
>         "M=D\n",
>         // Memory[THAT] <- Memory[Memory[R13]-1]
>         "@1\n",
>         "D=A\n",
>         "@R13\n",
>         "A=M-D\n",
>         "D=M\n",
>         "@THAT\n",
>         "M=D\n",
>         // Memory[THIS] <- Memory[Memory[R13]-2]
>         "@2\n",
>         "D=A\n",
>         "@R13\n",
>         "A=M-D\n",
>         "D=M\n",
>         "@THIS\n",
>         "M=D\n",
>         // Memory[ARG] <- Memory[Memory[R13]-3]
>         "@3\n",
>         "D=A\n",
>         "@R13\n",
>         "A=M-D\n",
>         "D=M\n",
>         "@ARG\n",
>         "M=D\n",
>         // Memory[LCL] <- Memory[Memory[R13]-4]
>         "@4\n",
>         "D=A\n",
>         "@R13\n",
>         "A=M-D\n",
>         "D=M\n",
>         "@LCL\n",
>         "M=D\n",
>         // goto Memory[R14]
>         "@R14\n",
>         "A=M\n",
>         "0;JMP\n",
>         NULL
>     );
> }
> 
> void CodeWriter_writeFunction(CodeWriter thisObject, char *functionName, int numLocals)
> {
>     char numLocalsString[255];
>     sprintf(numLocalsString, "%d", numLocals);
> 
>     fputslist(
>         thisObject->fpAsm,
>         "// function ", functionName, " ", numLocalsString, "\n",
>         "(", functionName, ")\n",
>         NULL
>     );
>     for (int i = 0; i < numLocals; i++) {
>         writePushConstant(thisObject->fpAsm, 0);
>     }
> }
> 
$ diff -w -r 08/VMtranslator3/CodeWriterPrivate.h 08/VMtranslator4/CodeWriterPrivate.h
$ diff -w -r 08/VMtranslator3/CodeWriterPrivate.c 08/VMtranslator4/CodeWriterPrivate.c

関数呼び出しコマンド(完全版)

ソースコード08/VMtranslator5/です。

ここでは下記のコマンドに対応しました。また、ブートストラップコードに対応したので.vmファイルには必ずSys.init関数が必要です。

コマンド 概要
call f m 各種レジスタ保存, goto f

下記で使えます。

test08.sh:L66-L82

cp -r ./nand2tetris/projects/08/FunctionCalls/FibonacciElement 08/VMtranslator5/

# ...(省略)...

cd 08/VMtranslator5/

clang --std=c11 -Wall -Wextra -o VMtranslator main.c Parser.c ParserPrivate.c CodeWriter.c CodeWriterPrivate.c

# ...(省略)...
./VMtranslator FibonacciElement

main.c

callおよび複数vmファイルに対応しました。

$ diff -w -r 08/VMtranslator4/main.c 08/VMtranslator5/main.c 
80a81
>     CodeWriter_writeInit(codeWriter);
114,115d114
< 
<         break;
163c162
< 
---
>     CodeWriter_writeInit(codeWriter);
247a247,250
>         case PARSER_COMMAND_TYPE_C_CALL:
>             Parser_arg1(parser, segment);
>             CodeWriter_writeCall(codeWriter, segment, Parser_arg2(parser));
>             break;

Parserモジュール

callに対応しました。

$ diff -w -r 08/VMtranslator4/Parser.h 08/VMtranslator5/Parser.h 
19c19,20
<     PARSER_COMMAND_TYPE_C_RETURN
---
>     PARSER_COMMAND_TYPE_C_RETURN,
>     PARSER_COMMAND_TYPE_C_CALL
$ diff -w -r 08/VMtranslator4/Parser.c 08/VMtranslator5/Parser.c
42a43
>     case PARSER_COMMAND_TYPE_C_CALL:
82a84
>     IF_CMP_RET(thisObject->command,     "call", PARSER_COMMAND_TYPE_C_CALL);
100c102,103
<         Parser_commandType(thisObject) == PARSER_COMMAND_TYPE_C_FUNCTION) {
---
>         Parser_commandType(thisObject) == PARSER_COMMAND_TYPE_C_FUNCTION ||
>         Parser_commandType(thisObject) == PARSER_COMMAND_TYPE_C_CALL) {
$ diff -w -r 08/VMtranslator4/ParserPrivate.h 08/VMtranslator5/ParserPrivate.h
$ diff -w -r 08/VMtranslator4/ParserPrivate.c 08/VMtranslator5/ParserPrivate.c

CodeWriterモジュール

callおよび複数vmファイルに対応しました。

$ diff -w -r 08/VMtranslator4/CodeWriter.h 08/VMtranslator5/CodeWriter.h 
12a13
> void CodeWriter_writeInit(CodeWriter thisObject);
22a24
> void CodeWriter_writeCall(CodeWriter thisObject, char *functionName, int numArgs);
$ diff -w -r 08/VMtranslator4/CodeWriter.c 08/VMtranslator5/CodeWriter.c
10a11
> void writePushRegisterByName(FILE* fpAsm, char *registerName);
18a20
>     int callCount;
26a29
>     thisObject.callCount = 0;
38a42,56
> void CodeWriter_writeInit(CodeWriter thisObject)
> {
>     fputslist(
>         thisObject->fpAsm,
>         // Memory[SP] <- 256
>         "@256\n",
>         "D=A\n",
>         "@SP\n",
>         "M=D\n",
>         NULL
>     );
>     // call Sys.init 0
>     CodeWriter_writeCall(thisObject, "Sys.init", 0);
> }
> 
129a148,203
> void CodeWriter_writeCall(CodeWriter thisObject, char *functionName, int numArgs)
> {
>     char numArgsString[255];
>     sprintf(numArgsString, "%d", numArgs);
> 
>     char returnLabel[255];
>     sprintf(returnLabel, "%s$%d", functionName, thisObject->callCount);
> 
>     fputslist(
>         thisObject->fpAsm,
>         "// call ", functionName, " ", numArgsString, "\n",
>         // Memory[Memory[SP]] <- return-address
>         "@", returnLabel, "\n",
>         "D=A\n",
>         "@SP\n",
>         "A=M\n",
>         "M=D\n",
>         // Memory[SP] += 1
>         "@SP\n",
>         "M=M+1\n",
>         NULL
>     );
> 
>     // push LCL, ARG, THIS, THAT
>     writePushRegisterByName(thisObject->fpAsm, "LCL");
>     writePushRegisterByName(thisObject->fpAsm, "ARG");
>     writePushRegisterByName(thisObject->fpAsm, "THIS");
>     writePushRegisterByName(thisObject->fpAsm, "THAT");
> 
>     fputslist(
>         thisObject->fpAsm,
>         // Memory[ARG] <- Memory[SP]-numArgsString-5
>         "@SP\n",
>         "D=M\n",
>         "@", numArgsString, "\n",
>         "D=D-A\n",
>         "@5\n",
>         "D=D-A\n",
>         "@ARG\n",
>         "M=D\n",
>         // Memory[LCL] <- Memory[SP]
>         "@SP\n",
>         "D=M\n",
>         "@LCL\n",
>         "M=D\n",
>         // goto function
>         "@", functionName, "\n",
>         "0;JMP\n",
>         // (return-address) <- {thisObject->vmFileName}${thisObject->callCount}
>         "(", returnLabel, ")\n",
>         NULL
>     );
> 
>     thisObject->callCount++;
> }
> 
246a321,337
> 
> void writePushRegisterByName(FILE* fpAsm, char *registerName)
> {
>     fputslist(
>         fpAsm,
>         // Memory[Memory[SP]] <- Memory[registerName]
>         "@", registerName, "\n",
>         "D=M\n",
>         "@SP\n",
>         "A=M\n",
>         "M=D\n",
>         // Memory[SP] += 1
>         "@SP\n",
>         "M=M+1\n",
>         NULL
>     );
> }
$ diff -w -r 08/VMtranslator4/CodeWriterPrivate.h 08/VMtranslator5/CodeWriterPrivate.h
$ diff -w -r 08/VMtranslator4/CodeWriterPrivate.c 08/VMtranslator5/CodeWriterPrivate.c

まとめ

なんとなくは知っていたはずのバーチャルマシンも実際に実装してみようと思うと大変でした。特にコマンドに対応するアセンブラを考えるのは頭の体操になりました。また相変わらずC言語ディレクトリ、ファイル、文字列操作など大変と感じました。色々怪しい実装部分は残っていますがとりあえず動かせたのはよかったです。

コンピュータシステムの理論と実装の6章のアセンブラを実装しました

前回の続きです。今回はコンピュータシステムの理論と実装(以下、nand2tetris本)の6章のアセンブラC言語*1で実装してみました。

今回のコード

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

github.com

下記で動かせます。

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

概要

今回、実装したのはASMファイル(アセンブリコード)を入力として受け取りHACKファイル(バイナリコード)を生成するコマンドです。

f:id:nihma:20200506160824p:plain

ASMファイル(アセンブリコード)には下記の要素が含まれます。このうちの命令を対応するバイナリコードに翻訳していきます。

  • スキップするもの
    • 空白
    • コメント
    • 改行(EOL)
    • EOF
  • 命令
    • A命令: @value
      • value
        • アドレス(数値)
        • シンボル(数値以外から始まる)
          • 定義済みシンボル
          • ラベルシンボル
          • 変数シンボル
    • C命令: dest=comp;jump
      • destが省略の場合は=も省略
      • jumpが省略の場合は;も省略
  • ラベルシンボル: (Xxx)

下記はASMファイル(アセンブリコード)の例です。

04/mult/mult.asm

// Multiplies R0 and R1 and stores the result in R2.
// (R0, R1, R2 refer to RAM[0], RAM[1], and RAM[2], respectively.)

        @R1
        D=M
        @n
        M=D
        @R2
        M=0
(LOOP)
        @n
        D=M
        @END
        D;JEQ
        @R0
        D=M
        @R2
        M=D+M
        @n
        M=M-1
        @LOOP
        0;JMP
(END)
        @END
        0;JMP

生成するHACKファイル(バイナリコード)は次の形式です。

  • テキスト形式
  • 16ビットの機械語命令が0or1のASCII文字列として16文字並ぶ
  • 機械語命令の後ろに改行文字が入る

下記はHACKファイル(バイナリコード)の例です。

04/mult/mult.asmのバイナリコード

0000000000000001
1111110000010000
0000000000010000
1110001100001000
0000000000000010
1110101010001000
0000000000010000
1111110000010000
0000000000010010
1110001100000010
0000000000000000
1111110000010000
0000000000000010
1111000010001000
0000000000010000
1111110010001000
0000000000000110
1110101010000111
0000000000010010
1110101010000111

なお、今回は書籍で提示された設計にできるだけ従うようにしてみました。*2またASMファイル(アセンブリコード)にエラーが含まれていない前提としています。そして、実行時の例外に対応する処理もだいぶ省いています。*3

シンボルを含まないプログラムのためのアセンブラ

書籍ではまず下記の要素が含まれない前提のアセンブラを実装します。

  • 命令
    • A命令: @value
      • value
        • シンボル(数値以外から始まる)
          • 定義済みシンボル
          • ラベルシンボル
          • 変数シンボル
  • ラベルシンボル: (Xxx)

下記のように実装を行いました。コードは06/AssemblerL/です。

f:id:nihma:20200506175405p:plain

下記で使えます。

test.sh:L53-L84

cp ./nand2tetris/projects/06/max/MaxL.asm 06/AssemblerL/

# ...(省略)...

cd 06/AssemblerL/

clang --std=c11 -Wall -Wextra -o AssemblerL main.c Parser.c Code.c

echo "MaxL"
./AssemblerL MaxL.asm

Parserモジュール

ASMファイル(アセンブリコード)をパースするためのモジュールです。
main.cで利用する関数はParser.hで下記のように定義しました。parser構造体はtypedefして定義はParser.c内に隠蔽するようにしてオブジェクトとして使うようにしました。それぞれの実装はParser.cで行いました。

06/AssemblerL/Parser.h:L19-L28

typedef struct parser * Parser;

Parser Parser_init(FILE *fpAsm);
bool Parser_hasMoreCommands(Parser thisObject);
void Parser_advance(Parser thisObject);
Parser_CommandType Parser_commandType(Parser thisObject);
void Parser_symbol(Parser thisObject, char *symbol);
void Parser_dest(Parser thisObject, char *dest);
void Parser_comp(Parser thisObject, char *comp);
void Parser_jump(Parser thisObject, char *jump);

上記の関数の中で使う関数はParser.c内で下記のように定義しました。ASMファイルストリーム(FILE *fpAsm)に対するfgetcおよびungetcは下記で行うようにしています。

06/AssemblerL/Parser.c:L15-L23

bool isSpace(FILE *fpAsm);
bool isComment(FILE *fpAsm);
bool isEndOfFile(FILE *fpAsm);
bool isEndOfLine(FILE *fpAsm);
bool isAdvance(FILE *fpAsm);
void skipSpaces(FILE *fpAsm);
void skipEndOFLines(FILE *fpAsm);
void skipComment(FILE *fpAsm);
void moveNextAdvance(FILE *fpAsm);

Codeモジュール

C命令のニーモニックとバイナリのマッピングするためのモジュールです。
main.cで利用する関数はCode.hで下記のように定義しました。それぞれの実装はCode.cで行いました。

06/AssemblerL/Code.h:L4-L6

void Code_dest(char *mnemonic, char *dest);
void Code_comp(char *mnemonic, char *comp);
void Code_jump(char *mnemonic, char *jump);

それぞれの関数はC命令のニーモニックとバイナリのマッピングを行いますが可読性を向上させるためCode.cに下記の関数マクロを定義して使いました。

06/AssemblerL/Code.c:L4

#define IF_CMP_CPY(condVar, condStr, destVar, destStr) if (strcmp(condVar, condStr) == 0) strcpy(destVar, destStr)

それぞれのマッピングは下記の通りです。

06/AssemblerL/Code.c:L6-L50

void Code_dest(char *mnemonic, char *dest)
{
    IF_CMP_CPY(mnemonic,    "", dest, "000");
    IF_CMP_CPY(mnemonic,   "M", dest, "001");
    IF_CMP_CPY(mnemonic,   "D", dest, "010");
    IF_CMP_CPY(mnemonic,  "MD", dest, "011");
    IF_CMP_CPY(mnemonic,   "A", dest, "100");
    IF_CMP_CPY(mnemonic,  "AM", dest, "101");
    IF_CMP_CPY(mnemonic,  "AD", dest, "110");
    IF_CMP_CPY(mnemonic, "AMD", dest, "111");
}

void Code_comp(char *mnemonic, char *comp)
{
    IF_CMP_CPY(mnemonic,   "0", comp, "0101010");
    IF_CMP_CPY(mnemonic,   "1", comp, "0111111");
    IF_CMP_CPY(mnemonic,  "-1", comp, "0111010");
    IF_CMP_CPY(mnemonic,   "D", comp, "0001100");
    IF_CMP_CPY(mnemonic,   "A", comp, "0110000"); IF_CMP_CPY(mnemonic,   "M", comp, "1110000");
    IF_CMP_CPY(mnemonic,  "!D", comp, "0001101");
    IF_CMP_CPY(mnemonic,  "!A", comp, "0110001"); IF_CMP_CPY(mnemonic,  "!M", comp, "1110001");
    IF_CMP_CPY(mnemonic,  "-D", comp, "0001111");
    IF_CMP_CPY(mnemonic,  "-A", comp, "0110011"); IF_CMP_CPY(mnemonic,  "-M", comp, "1110011");
    IF_CMP_CPY(mnemonic, "D+1", comp, "0011111");
    IF_CMP_CPY(mnemonic, "A+1", comp, "0110111"); IF_CMP_CPY(mnemonic, "M+1", comp, "1110111");
    IF_CMP_CPY(mnemonic, "D-1", comp, "0001110");
    IF_CMP_CPY(mnemonic, "A-1", comp, "0110010"); IF_CMP_CPY(mnemonic, "M-1", comp, "1110010");
    IF_CMP_CPY(mnemonic, "D+A", comp, "0000010"); IF_CMP_CPY(mnemonic, "D+M", comp, "1000010");
    IF_CMP_CPY(mnemonic, "D-A", comp, "0010011"); IF_CMP_CPY(mnemonic, "D-M", comp, "1010011");
    IF_CMP_CPY(mnemonic, "A-D", comp, "0000111"); IF_CMP_CPY(mnemonic, "M-D", comp, "1000111");
    IF_CMP_CPY(mnemonic, "D&A", comp, "0000000"); IF_CMP_CPY(mnemonic, "D&M", comp, "1000000");
    IF_CMP_CPY(mnemonic, "D|A", comp, "0010101"); IF_CMP_CPY(mnemonic, "D|M", comp, "1010101");
}

void Code_jump(char *mnemonic, char *jump)
{
    IF_CMP_CPY(mnemonic,    "", jump, "000");
    IF_CMP_CPY(mnemonic, "JGT", jump, "001");
    IF_CMP_CPY(mnemonic, "JEQ", jump, "010");
    IF_CMP_CPY(mnemonic, "JGE", jump, "011");
    IF_CMP_CPY(mnemonic, "JLT", jump, "100");
    IF_CMP_CPY(mnemonic, "JNE", jump, "101");
    IF_CMP_CPY(mnemonic, "JLE", jump, "110");
    IF_CMP_CPY(mnemonic, "JMP", jump, "111");
}

main.c

アセンブラのエントリポイントです。
main.cではコマンド引数の解析、ParserモジュールおよびCodeモジュールを用いたアセンブル処理を行います。main.cの中で使う関数はmain.c内で下記のように定義しました。

06/AssemblerL/main.c:L16-L20

bool getHackFileName(char *asmFileName, char *hackFileName);
void assemble(FILE *fpAsm, FILE *fpHack);
void assembleACommand(Parser parser, FILE *fpHack);
void assembleCCommand(Parser parser, FILE *fpHack);
void getACommandValueString(int valueNumber, char *valueString);

アセンブル処理の実装は下記の通りです。ASMファイルとHACKファイルのファイルポインタを受け取りアセンブル出来次第、HACKファイルにfputsでバイナリコードを追記しています。シンボルを含まない前提のためA命令は数値の前提で処理しています。

06/AssemblerL/main.c:L94-L148

void assemble(FILE *fpAsm, FILE *fpHack)
{
    Parser parser = Parser_init(fpAsm);
    while (Parser_hasMoreCommands(parser)) {
        Parser_advance(parser);
        switch (Parser_commandType(parser)) {
        case PARSER_COMMAND_TYPE_A_COMMAND:
            assembleACommand(parser, fpHack);
            break;
        case PARSER_COMMAND_TYPE_C_COMMAND:
            assembleCCommand(parser, fpHack);
            break;
        default:
            break;
        }
    }
}

void assembleACommand(Parser parser, FILE *fpHack)
{
    char symbol[PARSER_SYMBOL_MAX_LENGTH + 1];
    int valueNumber;
    char value[A_COMMAND_VALUE_LENGTH + 1];

    Parser_symbol(parser, symbol);
    sscanf(symbol, "%d", &valueNumber);
    getACommandValueString(valueNumber, value);

    // 0 value
    fputs("0", fpHack);
    fputs(value, fpHack);
    fputs("\n", fpHack);
}

void assembleCCommand(Parser parser, FILE *fpHack)
{
    char mnemonic[PARSER_MNEMONIC_MAX_LENGTH + 1];
    char dest[PARSER_DEST_LENGTH + 1], comp[PARSER_COMP_LENGTH + 1], jump[PARSER_JUMP_LENGTH + 1];

    Parser_dest(parser, mnemonic);
    Code_dest(mnemonic, dest);

    Parser_comp(parser, mnemonic);
    Code_comp(mnemonic, comp);

    Parser_jump(parser, mnemonic);
    Code_jump(mnemonic, jump);

    // 111 comp dest jump
    fputs("111", fpHack);
    fputs(comp, fpHack);
    fputs(dest, fpHack);
    fputs(jump, fpHack);
    fputs("\n", fpHack);
}

シンボルを含むプログラムのためのアセンブラ

下記のように実装を行いました。コードは06/Assembler/です。

f:id:nihma:20200506175436p:plain

下記で使えます。

test.sh:L86-L126

cp ./nand2tetris/projects/06/add/Add.asm 06/Assembler/

# ...(省略)...

cd 06/Assembler/

clang --std=c11 -Wall -Wextra -o Assembler main.c Parser.c Code.c SymbolTable.c

echo "Add"
./Assembler Add.asm

SymbolTableモジュール

シンボルとアドレスの対応を記録するためのモジュールです。
main.cで利用する関数はSymbolTable.hで下記のように定義しました。symbol_table構造体はtypedefして定義はSymbolTable.c内に隠蔽するようにしオブジェクトとして使うようにしました。後処理が必要となるため書籍と違いSymbolTable_deleteがあります。それぞれの実装はSymbolTable.cで行いました。

06/Assembler/SymbolTable.h:L6-L12

typedef struct symbol_table * SymbolTable;

SymbolTable SymbolTable_init(void);
void SymbolTable_addEntry(SymbolTable thisObject, char *symbol, int address);
bool SymbolTable_contains(SymbolTable thisObject, char *symbol);
int SymbolTable_getAddress(SymbolTable thisObject, char *symbol);
void SymbolTable_delete(SymbolTable thisObject);

今回は単純な単方向連結リストで実装しました。

06/Assembler/SymbolTable.c:L7-L18

typedef struct entry Entry;
struct entry
{
    char symbol[PARSER_SYMBOL_MAX_LENGTH + 1];
    int address;
    Entry *nextEntry;
};

struct symbol_table
{
    Entry *table;
};

main.c

下記が新規および変更した関数です。A命令のアセンブルを行うassembleACommand関数はSymbolTableへの変数シンボル登録に対応するために引数にSymbolTable symbolTableint ramAddressを追加してramAddressを返却するよう変更しました。

06/Assembler/main.c:20-L23

int assembleACommand(Parser parser, SymbolTable symbolTable, int ramAddress, FILE *fpHack);
void setDefinedSymbol(SymbolTable symbolTable);
void setLabelSymbol(SymbolTable symbolTable, Parser parser);

まず、定義済みシンボルをSymbolTableへ登録する関数です。

06/Assembler/main.c:175-L201

void setDefinedSymbol(SymbolTable symbolTable)
{
    // LABEL, RAM Address
    SymbolTable_addEntry(symbolTable, "SP",         0);
    SymbolTable_addEntry(symbolTable, "LCL",        1);
    SymbolTable_addEntry(symbolTable, "ARG",        2);
    SymbolTable_addEntry(symbolTable, "THIS",       3);
    SymbolTable_addEntry(symbolTable, "THAT",       4);
    SymbolTable_addEntry(symbolTable, "R0",         0);
    SymbolTable_addEntry(symbolTable, "R1",         1);
    SymbolTable_addEntry(symbolTable, "R2",         2);
    SymbolTable_addEntry(symbolTable, "R3",         3);
    SymbolTable_addEntry(symbolTable, "R4",         4);
    SymbolTable_addEntry(symbolTable, "R5",         5);
    SymbolTable_addEntry(symbolTable, "R6",         6);
    SymbolTable_addEntry(symbolTable, "R7",         7);
    SymbolTable_addEntry(symbolTable, "R8",         8);
    SymbolTable_addEntry(symbolTable, "R9",         9);
    SymbolTable_addEntry(symbolTable, "R10",       10);
    SymbolTable_addEntry(symbolTable, "R11",       11);
    SymbolTable_addEntry(symbolTable, "R12",       12);
    SymbolTable_addEntry(symbolTable, "R13",       13);
    SymbolTable_addEntry(symbolTable, "R14",       14);
    SymbolTable_addEntry(symbolTable, "R15",       15);
    SymbolTable_addEntry(symbolTable, "SCREEN", 16384);
    SymbolTable_addEntry(symbolTable, "KBD",    24576);
}

そして、ラベルシンボルをSymbolTableへ登録する関数です。書籍に1回目のパスと記されている処理です。

06/Assembler/main.c:203-L223

void setLabelSymbol(SymbolTable symbolTable, Parser parser)
{
    int romAddress = 0;
    char symbol[PARSER_SYMBOL_MAX_LENGTH + 1];

    while (Parser_hasMoreCommands(parser)) {
        Parser_advance(parser);
        switch (Parser_commandType(parser)) {
        case PARSER_COMMAND_TYPE_A_COMMAND:
        case PARSER_COMMAND_TYPE_C_COMMAND:
            romAddress++;
            break;
        case PARSER_COMMAND_TYPE_L_COMMAND:
            Parser_symbol(parser, symbol);
            SymbolTable_addEntry(symbolTable, symbol, romAddress);
            break;
        default:
            break;
        }
    }
}

最後がアセンブル処理です。シンボルに関する処理が追加されています。書籍に2回目のパスと記されている処理です。assembleCCommand関数は変更ありませんので省略しました。

06/Assembler/main.c:98-L151

void assemble(FILE *fpAsm, FILE *fpHack)
{
    Parser parser = Parser_init(fpAsm);
    int ramAddress = VARIABLE_SYMBOL_RAM_ADDRESS_START;
    SymbolTable symbolTable = SymbolTable_init();

    setDefinedSymbol(symbolTable);
    setLabelSymbol(symbolTable, parser);

    parser = Parser_init(fpAsm);
    while (Parser_hasMoreCommands(parser)) {
        Parser_advance(parser);
        switch (Parser_commandType(parser)) {
        case PARSER_COMMAND_TYPE_A_COMMAND:
            ramAddress = assembleACommand(parser, symbolTable, ramAddress, fpHack);
            break;
        case PARSER_COMMAND_TYPE_C_COMMAND:
            assembleCCommand(parser, fpHack);
            break;
        default:
            break;
        }
    }

    SymbolTable_delete(symbolTable);
}

int assembleACommand(Parser parser, SymbolTable symbolTable, int ramAddress, FILE *fpHack)
{
    char symbol[PARSER_SYMBOL_MAX_LENGTH + 1];
    int valueNumber;
    char value[A_COMMAND_VALUE_LENGTH + 1];

    Parser_symbol(parser, symbol);
    if (! isdigit(symbol[0])) {  // symbol is /^[^\d].*/
        if (SymbolTable_contains(symbolTable, symbol)) {
            valueNumber = SymbolTable_getAddress(symbolTable, symbol);
        } else {
            SymbolTable_addEntry(symbolTable, symbol, ramAddress);
            valueNumber = ramAddress;
            ramAddress++;
        }
    } else {
        sscanf(symbol, "%d", &valueNumber);
    }
    getACommandValueString(valueNumber, value);

    // 0 value
    fputs("0", fpHack);
    fputs(value, fpHack);
    fputs("\n", fpHack);

    return ramAddress;
}

まとめ

前回から間が空いてしまいましたがようやくアセンブラの実装ができました。7章以降もできれば進めたいです。C言語が大変だった。。

*1:久しぶりすぎてだいぶ忘れている。。環境はApple LLVM version 10.0.0 (clang-1000.11.45.5)です。

*2:モジュールを表現するのに抽象データ型にしてみたりとかとか。モジュール化してる割にはあまりカプセル化できてない設計だったりで気になりましたけど

*3:mallocなんかの戻り値もチェックしてなかったり

CloudFront/WAF/API GatewayのアクセスログをS3保存するようにしてAthenaで確認できるようにしてみた

関連記事で実装しているサーバレスWebアプリのサンプルのアクセスログ確認をAthenaでお手軽にしたいと思いました。そこでCloudFront/WAF/API Gatewayアクセスログをデータレイクとして用意したS3バケットへ保存するようにしてみました。

今回のコード

それぞれ記事時点のコードにタグを打ってあります。

アクセスログ保存の設定概要

全体構成は下記です。

f:id:nihma:20191026195205p:plain

データレイクとして作成するS3バケットは下記です。

  • CloudFront(API):${var.resource_prefix}-cloudfront-logs-api-01
  • CloudFront(SPA):${var.resource_prefix}-cloudfront-logs-web-01
  • WAF(API):${var.resource_prefix}-waf-logs-api-01
  • WAF(SPA):${var.resource_prefix}-waf-logs-web-01
  • API Gateway${var.resource_prefix}-apigw-logs-01

CloudFront

CloudFrontのアクセスログをS3バケットに保存するには下記の対応が必要です。*1

  1. ログ保存用のS3バケットを用意する
  2. CloudFrontのログ出力先に上記のS3バケットドメイン名を指定する

プルリクは下記です。

ログ保存用のS3バケット

まずAPIのS3バケットです。

aws-sls-spa-sample-terraform/environments/service/base/after_api/main.tf:L95-L99

module "s3_bucket_cloudfront_log_api" {
  source            = "../../../../modules/s3/bucket/cloudfront_log_api"
  resource_prefix   = "${local.resource_prefix}"
  logging_bucket_id = "${local.s3_bucket_audit_log_id}"
}

そしてSPAのS3バケットです。

aws-sls-spa-sample-terraform/environments/service/base/pre/main.tf:L219-L223

module "s3_bucket_cloudfront_log_web" {
  source            = "../../../../modules/s3/bucket/cloudfront_log_web"
  resource_prefix   = "${local.resource_prefix}"
  logging_bucket_id = "${var.s3_bucket_audit_log_id}"
}

CloudFrontのログ出力先

まずAPIのCloudFrontです。s3_bucket_log_domain_nameにS3バケットドメイン名を指定します。

aws-sls-spa-sample-terraform/environments/service/base/after_api/main.tf:L101-L108

module "cloudfront_api" {
  source                    = "../../../../modules/cloudfront/api"
  resource_prefix           = "${local.resource_prefix}"
  stage                     = "${var.stage}"
  apigw_api_domain_name     = "${var.apigw_api_id}.execute-api.ap-northeast-1.amazonaws.com"
  s3_bucket_log_domain_name = "${module.s3_bucket_cloudfront_log_api.bucket_domain_name}"
  waf_acl_id                = "${data.terraform_remote_state.service_base_pre.outputs.waf_acl_api_id}"
}

モジュールの中は下記です。aws_cloudfront_distributionリソースのlogging_configにS3バケットドメイン名を指定します。

aws-sls-spa-sample-terraform/modules/cloudfront/api/main.tf:L71-L73

resource "aws_cloudfront_distribution" "api" {
  # ...(省略)...
  logging_config {
    bucket = "${var.s3_bucket_log_domain_name}"
  }

そしてSPAのCloudFrontです。こちらもs3_bucket_log_domain_nameにS3バケットドメイン名を指定します。

aws-sls-spa-sample-terraform/environments/service/base/pre/main.tf:L231-L238

module "cloudfront_web" {
  source                    = "../../../../modules/cloudfront/web"
  resource_prefix           = "${local.resource_prefix}"
  s3_bucket_log_domain_name = "${module.s3_bucket_cloudfront_log_web.bucket_domain_name}"
  s3_bucket_web_id          = "${module.s3_bucket_web.id}"
  s3_bucket_web_domain_name = "${module.s3_bucket_web.domain_name}"
  waf_acl_id                = "${module.waf_acl_web.id}"
}

モジュールの中は下記です。こちらもaws_cloudfront_distributionリソースのlogging_configにS3バケットドメイン名を指定します。

aws-sls-spa-sample-terraform/modules/cloudfront/web/main.tf:L25-L28

resource "aws_cloudfront_distribution" "web" {
  # ...(省略)...
  logging_config {
    include_cookies = false
    bucket          = "${var.s3_bucket_log_domain_name}"
  }

WAF

WAFのアクセスログをS3バケットに保存するには下記の対応が必要です。*2

  1. ログ保存用のS3バケットを用意する
  2. Kinesis Firehoseを用意して出力先に上記のS3バケットARNを指定する
  3. WAFのログ出力先に上記のKinesis FirehoseのARNを指定する

プルリクは下記です。

ログ保存用のS3バケット

まずAPIのS3バケットです。

aws-sls-spa-sample-terraform/environments/service/base/pre/main.tf:L106-L110

module "s3_bucket_waf_log_api" {
  source            = "../../../../modules/s3/bucket/waf_log_api"
  resource_prefix   = "${local.resource_prefix}"
  logging_bucket_id = "${var.s3_bucket_audit_log_id}"
}

そしてSPAのS3バケットです。

aws-sls-spa-sample-terraform/environments/service/base/pre/main.tf:L142-L146

module "s3_bucket_waf_log_web" {
  source            = "../../../../modules/s3/bucket/waf_log_web"
  resource_prefix   = "${local.resource_prefix}"
  logging_bucket_id = "${var.s3_bucket_audit_log_id}"
}

Kinesis Firehose

用意するKinesis Firehoseにはいくつか注意点があります。*3*4

  • 作成するリージョンをus-east-1にする必要がある
  • 名称のプレフィックスaws-waf-logs-にする必要がある
  • ログファイルをGZIP形式にする必要がある

まずAPIKinesis Firehoseです。aws_kinesis_firehose_delivery_streamリソースのs3_configurationにS3バケットARNを指定します。

aws-sls-spa-sample-terraform/environments/service/base/pre/main.tf:L112-L129

module "iam_role_waf_log_api_firehose_to_s3" {
  source          = "../../../../modules/iam/waf_log_api_firehose_to_s3"
  path            = "../../../../modules/iam/waf_log_api_firehose_to_s3"
  resource_prefix = "${local.resource_prefix}"
  s3_bucket_arn   = "${module.s3_bucket_waf_log_api.arn}"
}

resource "aws_kinesis_firehose_delivery_stream" "waf_log_api" {
  provider    = aws.useast1
  name        = "aws-waf-logs-${local.resource_prefix}-api"
  destination = "s3"

  s3_configuration {
    role_arn           = "${module.iam_role_waf_log_api_firehose_to_s3.arn}"
    bucket_arn         = "${module.s3_bucket_waf_log_api.arn}"
    compression_format = "GZIP"
  }
}

名称プレフィックスGZIPは注意点の通りです。リージョンはaws.useast1というus-east-1providerを新たに用意して指定しました。aws.useast1は下記になっています。

aws-sls-spa-sample-terraform/environments/service/base/pre/main.tf:L11-L13

provider "aws" {
  alias   = "useast1"
  version = ">= 2.24"
  region  = "us-east-1"
}

そしてSPAのKinesis Firehoseです。こちらもaws_kinesis_firehose_delivery_streamリソースのs3_configurationにS3バケットARNを指定します。

aws-sls-spa-sample-terraform/environments/service/base/pre/main.tf:L148-L165

module "iam_role_waf_log_web_firehose_to_s3" {
  source          = "../../../../modules/iam/waf_log_web_firehose_to_s3"
  path            = "../../../../modules/iam/waf_log_web_firehose_to_s3"
  resource_prefix = "${local.resource_prefix}"
  s3_bucket_arn   = "${module.s3_bucket_waf_log_web.arn}"
}

resource "aws_kinesis_firehose_delivery_stream" "waf_log_web" {
  provider    = aws.useast1
  name        = "aws-waf-logs-${local.resource_prefix}-web"
  destination = "s3"

  s3_configuration {
    role_arn           = "${module.iam_role_waf_log_web_firehose_to_s3.arn}"
    bucket_arn         = "${module.s3_bucket_waf_log_web.arn}"
    compression_format = "GZIP"
  }
}

こちらもリージョン、名称プレフィックスGZIPは注意点の通りです。

WAFのログ出力先

まずAPIのWAFです。firehose_arnKinesis FirehoseのARNを指定します。

aws-sls-spa-sample-terraform/environments/service/base/pre/main.tf:L131-L138

module "waf_acl_api" {
  source                      = "../../../../modules/waf/api"
  resource_prefix             = "${local.resource_prefix}"
  firehose_arn                = "${aws_kinesis_firehose_delivery_stream.waf_log_api.arn}"
  rule_size_constraint_id     = "${module.waf_rule.rule_size_constraint_id}"
  rule_sql_injection_match_id = "${module.waf_rule.rule_sql_injection_match_id}"
  rule_xss_match_id           = "${module.waf_rule.rule_xss_match_id}"
}

モジュールの中は下記です。aws_waf_web_aclリソースのlogging_configurationKinesis FirehoseのARNを指定します。

aws-sls-spa-sample-terraform/modules/waf/api/main.tf:L42-L44

resource "aws_waf_web_acl" "api" {
  # ...(省略)...
  logging_configuration {
    log_destination = "${var.firehose_arn}"
  }

そしてSPAのWAFです。こちらもfirehose_arnKinesis FirehoseのARNを指定します。

aws-sls-spa-sample-terraform/environments/service/base/pre/main.tf:L167-L174

module "waf_acl_web" {
  source                      = "../../../../modules/waf/web"
  resource_prefix             = "${local.resource_prefix}"
  firehose_arn                = "${aws_kinesis_firehose_delivery_stream.waf_log_web.arn}"
  rule_size_constraint_id     = "${module.waf_rule.rule_size_constraint_id}"
  rule_sql_injection_match_id = "${module.waf_rule.rule_sql_injection_match_id}"
  rule_xss_match_id           = "${module.waf_rule.rule_xss_match_id}"
}

モジュールの中は下記です。こちらもaws_waf_web_aclリソースのlogging_configurationKinesis FirehoseのARNを指定します。

aws-sls-spa-sample-terraform/modules/waf/web/main.tf:L42-L44

resource "aws_waf_web_acl" "web" {
  # ...(省略)...
  logging_configuration {
    log_destination = "${var.firehose_arn}"
  }

API Gateway

API GatewayアクセスログをS3バケットに保存するには下記の対応が必要です。*5*6*7*8*9

  1. API GatewayのCloudWatch Logsへのアクセスログ保存を有効にする*10
  2. ログ保存用のS3バケットを用意する
  3. ログフォーマットをAthena用に変換するLambdaを用意する
  4. Kinesis Firehoseを用意して出力先に2.のS3バケットARN、ログ変換Lambdaに3のLambdaのARNを指定する
  5. CloudWatch Logsのサブスクリプションフィルタを用意してロググループに1.のロググループ名、出力先にKinesis FirehoseのARNを指定する

プルリクは下記です。

API GatewayのCloudWatch Logsへのアクセスログ保存

serverless.ymlrestApiを追加しました。*11*12Athenaで操作しやすくするためにJSONフォーマットです。*13

aws-sls-spa-sample-api/serverless.yml:L11-L25

provider:
  name: aws
  logs:
    restApi:
      format:
        '{
          "request_id":"$context.requestId",
          "ip": "$context.identity.sourceIp",
          "caller": "$context.identity.caller",
          "user": "$context.identity.user",
          "request_time": "$context.requestTime",
          "http_method": "$context.httpMethod",
          "resource_path": "$context.resourcePath",
          "status": "$context.status",
          "protocol": "$context.protocol",
          "response_length": "$context.responseLength"
        }'

これで/aws/api-gateway/${local.cloudformation_api_stack}というロググループにアクセスログが保存されるようになります。

ログ保存用のS3バケット

aws-sls-spa-sample-terraform/environments/service/base/pre/main.tf:L41-L45

module "s3_bucket_apigw_log" {
  source            = "../../../../modules/s3/bucket/apigw_log"
  resource_prefix   = "${local.resource_prefix}"
  logging_bucket_id = "${local.s3_bucket_audit_log_id}"
}

ログフォーマット変換Lambda

amazon-kinesis-firehose-cloudwatch-logs-processorを使いました。*14めんどくさかったので今回はindex.jsをダウンロードしてserverless frameworkでLambdaデプロイして使うようにしました。

まず、serverless frameworkのプロジェクトです。amazon-kinesis-firehose-cloudwatch-logs-processorindex.jsはCodeBuildのタイミングで取得するためbuildspec.ymlcurlしました。

aws-sls-spa-sample-terraform/serverless/buildspec.yml:L6-L10

    commands:
      - cd serverless
      - npm install -g serverless@1.49.0
      - COMMIT="ec522aa8c09df0eafbfe286cd1275ca5eb418e98"
      - curl -s -qL -o index.js "https://raw.githubusercontent.com/tmakota/amazon-kinesis-firehose-cloudwatch-logs-processor/${COMMIT}/index.js"

次にCodeBuildプロジェクトの作成です。

aws-sls-spa-sample-terraform/environments/service/base/pre/main.tf:L6-L10

## tool

module "iam_role_build_tool" {
  source                    = "../../../../modules/iam/build_tool"
  path                      = "../../../../modules/iam/build_tool"
  aws_account_id            = "${data.aws_caller_identity.current.account_id}"
  resource_prefix           = "${local.resource_prefix}"
  cloudformation_tool_stack = "${local.cloudformation_tool_stack}"
}

module "s3_bucket_build_tool" {
  source            = "../../../../modules/s3/bucket/build_tool"
  resource_prefix   = "${local.resource_prefix}"
  logging_bucket_id = "${var.s3_bucket_audit_log_id}"
}

module "iam_role_exec_tool" {
  source                    = "../../../../modules/iam/exec_tool"
  path                      = "../../../../modules/iam/exec_tool"
  aws_account_id            = "${data.aws_caller_identity.current.account_id}"
  resource_prefix           = "${local.resource_prefix}"
  cloudformation_tool_stack = "${local.cloudformation_tool_stack}"
}

module "codebuild_tool" {
  source                  = "../../../../modules/codebuild/tool"
  codecommit_repository   = "${data.terraform_remote_state.setup.outputs.codecommit_infra_repository}"
  iam_role_build_tool_arn = "${module.iam_role_build_tool.arn}"
  s3_bucket_build_tool_id = "${module.s3_bucket_build_tool.id}"
  resource_prefix         = "${var.resource_prefix}"
  stage                   = "${var.stage}"
  iam_role_exec_tool_arn  = "${module.iam_role_exec_tool.arn}"
  service_name            = "${local.service_name}"
}

最後にCodeBuildプロジェクトを実行してLambdaのデプロイです。

aws-sls-spa-sample-terraform/bin/create_development_environment.sh:L52-L56

##
echo "START: base..."
##
# ...(省略)...
cd environments/service/base/pre/ || exit 99

codebuild_name=$(terraform output codebuild_tool_name)

cd - || exit 99

./bin/exec_codebuild.sh "${codebuild_name}" master

staging/productionも同様なbashですが割愛します。

Kinesis Firehose

aws_kinesis_firehose_delivery_streamリソースのextended_s3_configurationにS3バケットARNとLambdaのARNを指定します。

aws-sls-spa-sample-terraform/environments/service/base/pre/main.tf:L47-L78

module "iam_role_apigw_firehose_to_s3" {
  source          = "../../../../modules/iam/apigw_firehose_to_s3"
  path            = "../../../../modules/iam/apigw_firehose_to_s3"
  resource_prefix = "${local.resource_prefix}"
  s3_bucket_arn   = "${module.s3_bucket_apigw_log.arn}"
  aws_account_id            = "${data.aws_caller_identity.current.account_id}"
  cloudformation_tool_stack = "${local.cloudformation_tool_stack}"
}

resource "aws_kinesis_firehose_delivery_stream" "apigw" {
  name        = "${local.resource_prefix}-apigw-cwl-to-s3-stream"
  destination = "extended_s3"

  extended_s3_configuration {
    role_arn           = "${module.iam_role_apigw_firehose_to_s3.arn}"
    bucket_arn         = "${module.s3_bucket_apigw_log.arn}"
    compression_format = "GZIP"

    processing_configuration {
      enabled = "true"

      processors {
        type = "Lambda"

        parameters {
          parameter_name  = "LambdaArn"
          parameter_value = "arn:aws:lambda:ap-northeast-1:${data.aws_caller_identity.current.account_id}:function:${local.cloudformation_tool_stack}-logsProcessor:$LATEST"
        }
      }
    }
  }
}

CloudWatch Logsのサブスクリプションフィルタ

aws_cloudwatch_log_subscription_filterリソースにロググループ名とKinesis FirehoseのARNを指定します。

aws-sls-spa-sample-terraform/environments/service/base/pre/main.tf:L80-L93

module "iam_role_apigw_cloudwatchlogs_to_s3_policy" {
  source          = "../../../../modules/iam/apigw_coudwatchlogs_to_s3_policy"
  path            = "../../../../modules/iam/apigw_coudwatchlogs_to_s3_policy"
  aws_account_id  = "${data.aws_caller_identity.current.account_id}"
  resource_prefix = "${local.resource_prefix}"
}

resource "aws_cloudwatch_log_subscription_filter" "apigw_logfilter" {
  name            = "${local.resource_prefix}-apigw_logfilter"
  role_arn        = "${module.iam_role_apigw_cloudwatchlogs_to_s3_policy.arn}"
  log_group_name  = "/aws/api-gateway/${local.cloudformation_api_stack}"
  filter_pattern  = ""
  destination_arn = "${aws_kinesis_firehose_delivery_stream.apigw.arn}"
}

Athenaで確認

SPAで色々と操作をしてしばらく経つとS3バケットアクセスログファイルが溜まってきます。

f:id:nihma:20191026190302p:plain

とりあえず今回は凝ったことをせずテーブル作ってSELECTするところまでしました。*15*16*17

CloudFront

まずはテーブルを定義します。*18*19

S3バケット名はAPI${var.resource_prefix}-cloudfront-logs-api-01、SPAが${var.resource_prefix}-cloudfront-logs-web-01です。

CREATE EXTERNAL TABLE IF NOT EXISTS `cloudfront_logs`(
  `date` date, 
  `time` string, 
  `location` string, 
  `bytes` bigint, 
  `request_ip` string, 
  `method` string, 
  `host` string, 
  `uri` string, 
  `status` int, 
  `referrer` string, 
  `user_agent` string, 
  `query_string` string, 
  `cookie` string, 
  `result_type` string, 
  `request_id` string, 
  `host_header` string, 
  `request_protocol` string, 
  `request_bytes` bigint, 
  `time_taken` float, 
  `xforwarded_for` string, 
  `ssl_protocol` string, 
  `ssl_cipher` string, 
  `response_result_type` string, 
  `http_version` string, 
  `fle_status` string, 
  `fle_encrypted_fields` int)
ROW FORMAT DELIMITED 
  FIELDS TERMINATED BY '\t' 
STORED AS INPUTFORMAT 
  'org.apache.hadoop.mapred.TextInputFormat' 
OUTPUTFORMAT 
  'org.apache.hadoop.hive.ql.io.HiveIgnoreKeyTextOutputFormat'
LOCATION
  's3://[S3バケット名]/'
TBLPROPERTIES (
  'skip.header.line.count'='2');

テーブルができたので検索できるようになりました。

SELECT * FROM "default"."cloudfront_logs" limit 10;

WAF

まずはテーブルを定義します。*20*21

S3バケット名はAPI${var.resource_prefix}-waf-logs-api-01、SPAが${var.resource_prefix}-waf-logs-web-01です。

CREATE EXTERNAL TABLE IF NOT EXISTS `waf_logs`(
  `timestamp` bigint, 
  `formatversion` int, 
  `webaclid` string, 
  `terminatingruleid` string, 
  `terminatingruletype` string, 
  `action` string, 
  `httpsourcename` string, 
  `httpsourceid` string, 
  `rulegrouplist` array<
                    struct<
                      rulegroupid: string,
                      terminatingrule: string,
                      nonterminatingmatchingrules: array< struct< action: string, ruleid: string > >,
                      excludedrules: array< struct< exclusiontype: string, ruleid: string > > > >, 
  `ratebasedrulelist` array< struct< ratebasedruleid: string, limitkey: string, maxrateallowed: int > >, 
  `nonterminatingmatchingrules` array< struct< action: string, ruleid: string > >, 
  `httprequest` struct<
                  clientip: string,
                  country: string,
                  headers: array< struct< name: string, value: string > >,
                  uri: string,
                  args: string,
                  httpversion: string,
                  httpmethod: string,
                  requestid: string>)
ROW FORMAT SERDE 
  'org.openx.data.jsonserde.JsonSerDe' 
STORED AS INPUTFORMAT 
  'org.apache.hadoop.mapred.TextInputFormat' 
OUTPUTFORMAT 
  'org.apache.hadoop.hive.ql.io.IgnoreKeyTextOutputFormat'
LOCATION
  's3://[S3バケット名]/';

テーブルができたので検索できるようになりました。

SELECT * FROM "default"."waf_logs" limit 10;

API Gateway

まずはテーブルを定義します。CREATE 文はserverless.ymlrestApiに指定したJSONフォーマットから作りました。

S3バケット名は${var.resource_prefix}-apigw-logs-01です。

CREATE EXTERNAL TABLE IF NOT EXISTS `apigw_logs`(
  `request_id` string, 
  `ip` string, 
  `caller` string, 
  `user` string, 
  `request_time` string, 
  `http_method` string, 
  `resource_path` string, 
  `status` string, 
  `protocol` string, 
  `response_length` string)
ROW FORMAT SERDE 
  'org.openx.data.jsonserde.JsonSerDe' 
WITH SERDEPROPERTIES ( 
  'ignore.malformed.json'='true') 
STORED AS INPUTFORMAT 
  'org.apache.hadoop.mapred.TextInputFormat' 
OUTPUTFORMAT 
  'org.apache.hadoop.hive.ql.io.IgnoreKeyTextOutputFormat'
LOCATION
  's3://[S3バケット名]/'
TBLPROPERTIES (
  'has_encrypted_data'='false');

テーブルができたので検索できるようになりました。

SELECT * FROM "default"."apigw_logs" limit 10;

まとめ

今回はCloudFront/WAF/API GatewayアクセスログをS3に保存しデータレイクとしてAthenaで確認できるようにしてみました。

  • DynamoDBの情報もGlueなどでS3データレイクに同期するようにしても良いかも。そうすればAthenaでSQL使えるし分析のためにRCUを消費してサービスに影響するということもないし。
  • Cognitoの情報もS3データレイクに同期するようにしても良いかも。ただお手軽に同期する手段がないのでCognitoトリガーで一旦DynamoDBに同期してからのGlueなどでの同期になるかも。
  • LambdaのログもS3データレイクに同期するようにしても良いかも。

関連記事

*1:CloudFrontのアクセスログの設定および使用:https://docs.aws.amazon.com/ja_jp/AmazonCloudFront/latest/DeveloperGuide/AccessLogs.html

*2:ウェブ ACL トラフィック情報のログ記録:https://docs.aws.amazon.com/ja_jp/waf/latest/developerguide/logging.html

*3:ウェブ ACL でログ記録を有効にするには:https://docs.aws.amazon.com/ja_jp/waf/latest/developerguide/logging.html#logging-procedure

*4:Athena圧縮形式:https://docs.aws.amazon.com/ja_jp/athena/latest/ug/compression-formats.html

*5:API Gateway CloudWatch の API ログ作成をセットアップする:https://docs.aws.amazon.com/ja_jp/apigateway/latest/developerguide/set-up-logging.html

*6:CloudWatch Logs サブスクリプションフィルタの使用:https://docs.aws.amazon.com/ja_jp/AmazonCloudWatch/latest/logs/SubscriptionFilters.html#FirehoseExample

*7:Amazon Kinesis Data Firehose のデータ変換:https://docs.aws.amazon.com/ja_jp/firehose/latest/dev/data-transformation.html

*8:AWS CloudWatch Logs に貯めこんだログをどうにかしようとしてハマった話:https://tech.actindi.net/2019/05/29/105748

*9:AWS Black Belt Online Seminar「Amazon Athena」の資料およびQA公開:https://aws.typepad.com/sajp/2017/03/aws-black-belt-online-seminaramazon-athena_slides_and_qa.html ... Q8にAmazon Kinesis FirehoseのData Transformationの必要性

*10:Firehoseを直接指定できるようになったので手順は変えた方が良いかも → Amazon API GatewayAmazon Kinesis Data Firehose へのアクセスログ記録をサポート開始:https://aws.amazon.com/jp/about-aws/whats-new/2019/10/amazon-api-gateway-now-supports-access-logging-to-amazon-kinesis-data-firehose/

*11:serverless/API Gateway REST API logs:https://serverless.com/blog/framework-release-v142/#api-gateway-rest-api-logs

*12:serverless/API Gateway REST API logshttps://serverless.com/framework/docs/providers/aws/events/apigateway/#logs

*13:API Gateway マッピングテンプレートとアクセスのログ記録の変数リファレンス:https://docs.aws.amazon.com/ja_jp/apigateway/latest/developerguide/api-gateway-mapping-template-reference.html

*14:Lambda設計図のKinesis Data Firehose CloudWatch Logs Processor (Kinesis Data Firehose CloudWatch ログプロセッサ) と同じ?

*15:S3のデータをAmazon Athenaを使って分析する:https://aws.amazon.com/jp/blogs/news/analyzing-data-in-s3-using-amazon-athena/

*16:CREATE TABLE:https://docs.aws.amazon.com/ja_jp/athena/latest/ug/create-table.html

*17:SELECT:https://docs.aws.amazon.com/ja_jp/athena/latest/ug/select.html

*18:Amazon CloudFront ログのクエリ:https://docs.aws.amazon.com/ja_jp/athena/latest/ug/cloudfront-logs.html

*19:CloudFrontログ形式:https://docs.aws.amazon.com/ja_jp/AmazonCloudFront/latest/DeveloperGuide/AccessLogs.html#LogFileFormat

*20:AWS WAFのフルログをAthenaで分析できるようにしてみた:https://dev.classmethod.jp/cloud/aws/query-aws-waf-full-log-by-athena/

*21:ログの例:https://docs.aws.amazon.com/ja_jp/waf/latest/developerguide/logging.html

SPA/サーバレスAPIのCodePipelineにlint/ユニットテスト/E2Eテストを加えてみた

関連記事で実装していたサーバレスWebアプリのサンプル向けのSPA/APIのCodePipelineに対して、lint/ユニットテストを行うステージとStaging構築ステージのE2Eテストを行うアクションを追加して自動でテストが実施されるようにしてみました。

関連記事

今回のコード

それぞれ記事時点のコードにタグを打ってあります。

環境構成

下記のAddの部分を追加しました。

f:id:nihma:20190814110305p:plain

E2Eテストを行う環境は新たに用意しようか迷いましたが今回はStaging環境を使うことにしました。

変更概要

API: lint/ユニットテストを行うステージ

npm run docker-test-allを実施するようにしました。これは元々CircleCI向けtslintmochaのチェックができるよう用意していたコマンドです。

まずAPI側にCodeBuildから実行するtestspec.ymlを用意しました。CodeBuild環境でのdocker-compose execはTTYを無効にする必要があるようだったのでその対応もしました。

github.com

そしてTerraformでIAMロール/CodeBuildの用意とCodePipelineへのstage追加を行うようにしました。

github.com

SPA: lint/ユニットテストを行うステージ

こちらもnpm run docker-test-allを実施するようにしました。これも元々CircleCI向けtslintのチェックができるよう用意していたコマンドです。

まずSPA側にCodeBuildから実行するtestspec.ymlを用意しました。これもdocker-compose execのTTYを無効にする対応を行いました。

github.com

そしてTerraformでIAMロール/CodeBuildの用意とCodePipelineへのstage追加を行うようにしました。

github.com

SPA: E2Eテストを行うアクション

AngularなのでProtractorでE2Eテストするようにしてみました。

まずはE2Eテストが動くように修正しました。*1それからCodeBuildから実行するe2espec.ymlを用意しました。CodeBuildではProtractorをHeadless Chromeで動かすようにしました。*2

github.com

そしてTerraformでIAMロール/CodeBuildの用意とCodePipelineへのaction追加を行うようにしました。

github.com

下記のリンクは参考にしました。

medium.com

stackoverflow.com

まとめ

今回はlint/ユニットテストを行うステージとStaging構築ステージのE2Eテストを行うアクションを追加しました。

  • CodePipelineの処理に時間がかかっているのは改善したいです。一度buildしたものを使い回すなどできたら少しは改善するかも
  • E2Eテストはもう少し拡充したいです。その場合、E2Eテスト前にCognitoやDynamoDBの初期化なども必要になってるかも

*1:今回はトップページの要素を確認するテストだけしか用意してませんmm

*2:Protractorのアクセス先であるbaseUrlはprotractor.conf.jsに定義する必要があります。ここをCodeBuildの環境変数からSPAのCloudFrontのURLを動的に指定したかったのですが方法が分からなかったためbashでcustom_protractor.conf.jsを生成して使う方法にしました。もっと良い方法があれば知りたいです...

EC2/Laravel+Code4兄弟による継続的デプロイ環境のCloudFormationをAWS CDKに置き換えてみました

AWS CDKGAになったので前回記事で構築したEC2/Laravel+Code4兄弟による継続的デプロイ環境をAWS CDK化して試してみました。

今回のコード

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

github.com

CloudFormation環境も残しておきたかったので前回のリポジトリとは別にしています。言語は普段使いで型の恩恵が受けられるTypeScriptを選択しました。

環境構成

前回の記事の「環境構成」と同じなので省略します。

コードのディレクトリ構成は下記です。

.
├── Dockerfile_ecr
├── appspec.yml
├── aws_deploy.sh
├── buildspec.yml
├── buildspec_ecr.yml
├── infra
│   ├── bin
│   │   └── laravel-ec2-cdk-sample.ts ... エントリポイント
│   ├── cdk.json
│   ├── lib
│   │   ├── build-env-stack.ts        ... BuildEnvスタック
│   │   ├── code-store-stack.ts       ... CodeStoreスタック
│   │   ├── deploy-pipeline-stack.ts  ... DeployPipelineスタック
│   │   ├── ec2-stack.ts              ... EC2スタック
│   │   └── network-stack.ts          ... Networkスタック
│   ├── package-lock.json
│   ├── package.json
│   ├── setup_ec2.yml
│   ├── templates
│   │   ├── laravel.env.j2
│   │   └── nginx.conf.j2
│   └── tsconfig.json
└── laravel

基本的には下記などを参照したり cdk synth して infra/cdk.out/ にできたCloudFormationテンプレートファイルを確認しながら置き換え作業をしていきました。

docs.aws.amazon.com

docs.aws.amazon.com

github.com

構築手順

README.mdの通りです

CodeCommitを構築

前回の記事の「CodeCommitを構築」です。

コード管理の場所を用意してGitHubから取り込みます。

git clone https://github.com/nihemak/laravel-ec2-cdk-sample.git
cd laravel-ec2-cdk-sample/infra
npm install
npm run build
./node_modules/aws-cdk/bin/cdk deploy CodeStore --require-approval never
git push ssh://git-codecommit.ap-northeast-1.amazonaws.com/v1/repos/laravel-ec2-sample --all

Laravelプロジェクトのビルドに必要なECR環境を構築

前回の記事の「Laravelプロジェクトのビルドに必要なECR環境を構築」です。

Laravelプロジェクトのビルドで使用するEC2インスタンスと同じ環境のdockerイメージが登録されたECRリポジトリを用意します。

./node_modules/aws-cdk/bin/cdk deploy BuildEnv --require-approval never
CODEBUILD_ID=$(aws codebuild start-build --project-name laravel-ec2-sample-ecr --source-version master | tr -d "\n" | jq -r '.build.id')
echo "started.. id is ${CODEBUILD_ID}"
while true
do
  sleep 10s
  STATUS=$(aws codebuild batch-get-builds --ids "${CODEBUILD_ID}" | tr -d "\n" | jq -r '.builds[].buildStatus')
  echo "..status is ${STATUS}."
  if [ "${STATUS}" != "IN_PROGRESS" ]; then
    if [ "${STATUS}" != "SUCCEEDED" ]; then
      echo "faild."
    fi
    echo "done."
    break
  fi
done

VPC/サブネット環境とECインスタンスを構築

前回の記事の「VPC/サブネット環境とECインスタンスを構築」です。

まずEC2インスタンスへのSSHアクセスの為にキーペア/pemを作成します。

key_pair=$(aws ec2 create-key-pair --key-name test-laravel)
echo $key_pair | jq -r ".KeyMaterial" > test-laravel.pem
chmod 400 test-laravel.pem

そしてVPC/サブネット環境とLaravelプロジェクトを動かすECインスタンスを用意します。

./node_modules/aws-cdk/bin/cdk deploy Network --require-approval never
./node_modules/aws-cdk/bin/cdk deploy EC2 --require-approval never

デプロイのパイプラインを構築

前回の記事の「デプロイのパイプラインを構築」です。

CodePipelineおよびCodeBuildとCodeDeploy、CodeCommitを監視してCodePipelineを実行するCloudWatch Eventsを用意します。

./node_modules/aws-cdk/bin/cdk deploy DeployPipeline --require-approval never

使い方

README.mdの通りです。前回の記事の「使い方」と同じなので省略します。

まとめ

今回はAWS CDKを試してみました。

  • プログラミング言語で構成を定義できるので共通化などを使えるのは利点だと思います。反面、あまり凝りすぎると分かりづらくなってインフラ構成の仕様としての利点が薄れる気がします。そのため、構成定義ファイルと割り切ったある程度の冗長な書き方にして後から構成仕様がすぐわかるようにしておくことが大切だと感じました。*1
  • 構成がブラックボックスのままプロビジョニングするのは事故につながるので生成されるCloudFormationテンプレートファイルがどうなるか注意して使う必要があると感じます。そう考えると意外と導入の敷居は高いかもと思いました。*2

*1:この辺はユニットテストコードとかと同じと思いますが

*2:逆にCloudFormationテンプレートファイルに慣れているプログラマならすんなり使えるかも