前回の続きです。今回はコンピュータシステムの理論と実装(以下、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ファイル
を生成するコマンドです。
バーチャルマシンはスタックベースです。長くなってしまうためここでは細かい仕様の説明は省略します。気になる場合はコンピュータシステムの理論と実装の7章と8章に詳しく記載されています。この記事の目的は自分が後から思い出すためのとっかかりを残すことであるため実装してみた内容の概要の記述にとどめます。
なお、実装は書籍が用意したテストプログラムに対応する形でインクリメンタルに進めました。そのため、次の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) {
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-
void writeArithmethicAdd(FILE* fpAsm) { writeArithmethicBinaryOperation(fpAsm, "D+M"); }
void writeArithmethicBinaryOperation(FILE* fpAsm, char *comp)
{
fputslist(
fpAsm,
"// BinaryOperation ", comp, "\n",
"@SP\n",
"M=M-1\n",
"A=M\n",
"D=M\n",
"@SP\n",
"M=M-1\n",
"A=M\n",
"M=", comp, "\n",
"@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以外のpush
とpop
に対応しました。
$ 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言語はディレクトリ、ファイル、文字列操作など大変と感じました。色々怪しい実装部分は残っていますがとりあえず動かせたのはよかったです。