nand2tetris6章のアセンブラをRustで書いた

nand2tetris6章のアセンブラをRustで書いた
TaKO8Ki
May 1, 2020

こんにちは、TaKO8Kiです。

最近、「コンピュータシステムの理論と実装 ―モダンなコンピュータの作り方」を始めたのですが、6章のアセンブラをRustで実装してみたので、ここに記しておきます。

...
コンピュータシステムの理論と実装

https://www.amazon.co.jp/gp/product/4873117127

そもそも「コンピュータシステムの理論と実装」とは？

nand回路から各種論理回路をassemblyで実装していき、アセンプリ・コンパイラ・OSなどを段階的に作っていくことができます。 割と重めの内容でかつ実装を伴うので、個人的には早くて一ヶ月でから2ヶ月くらいかかりそうな予感がしています。

実装したもの

作ったアセンブラ自体はここに置いてあります。
https://github.com/TaKO8Ki/nand2assembler

細かいアセンブラの仕様は、実際に本を読んでもらえればいいと思うのですが、基本的にやりたいことは、下記の三つです。

  1. .asmファイルをいい感じにparseする
  2. parseしたものに対してloopを回して、16bitのバイナリに変換
  3. 変換したものを上から順に.hackファイルに書き込む

Parserモジュール

少しでもLexer（字句解析器）に触れたことある方にとっては分かりやすいと思いますが、 このモジュールでやることとしては非常に単純で、下記のようなHoge.asmを一行ずつparseして、「どの命令に当てはまるのか？」・ 「変数が使われているのか？」を見るだけです。

.asmファイルの例

@2
D=A
@3
D=D+A
@0
M=D

parser.rs

pub struct Parser {
    pub stream: BufReader<std::fs::File>,
    pub now_line: String,
    pub command_type: Option<u32>,
}

impl Parser {
      pub fn new(f: BufReader<std::fs::File>) -> Parser {
        Parser {
            // read onlyなFileのstruct
            stream: f,
            now_line: "".to_string(),
            command_type: None,
        }
    }

    pub fn advance(&mut self) -> usize {
        // 行を次に進める
    }

    pub fn has_more_commands(&self) -> bool {
        // 行がコマンドを持っているかどうか？
    }

    pub fn command_type(&mut self) -> Option<u32> {
        // Parser structのcommand_typeを詰める
        // command_typeは下にあるa_command, c_command, l_commandで判別する
    }

    pub fn symbol(&self) -> Option<String> {
        // a_commandもしくは、l_commandの時にsymbolを返す
    }

    pub fn dest(&self) -> Option<String> {
        // destのmnemonicを返す
    }

    pub fn comp(&self) -> Option<String> {
        // compのmnemonicを返す
    }

    pub fn jump(&self) -> Option<String> {
        // jumpのmnemonicを返す
    }

    pub fn a_command(&self) -> bool {
        // a_commandかどうかの判別をする
    }

    pub fn c_command(&self) -> bool {
        // c_commandかどうかの判別をする
    }

    pub fn l_command(&self) -> bool {
        // l_commandかどうかの判別をする
    }
}

Codeモジュール

続いてこのモジュールでは、c_commandの三つの領域dest・comp・jumpのmnemonicを返します。 この三つの領域にくる要素はあらかじめ決められているものしかないので、それらをHashMapに定義しておいてそこから取り出すようにすればいいです。

code.rs

lazy_static! {
    static ref COMP_MAP: HashMap<&'static str, &'static str> = {
        let mut m = HashMap::new();
        // mnemonicとバイナリの対応を詰める
        m.insert("D|M", "1010101");
        m
    };
    static ref DEST_MAP: HashMap<&'static str, &'static str> = {
        // mnemonicとバイナリの対応を詰める
        let mut m = HashMap::new();
        m.insert("null", "000");
        m
    };
    static ref JUMP_MAP: HashMap<&'static str, &'static str> = {
        // mnemonicとバイナリの対応を詰める
        let mut m = HashMap::new();
        m.insert("null", "000");
        m
    };
}

pub fn dest(mnemonic: Option<String>) -> String {
    // mnemonicを受け取って対応したバイナリを返す
}

pub fn comp(mnemonic: Option<String>) -> String {
    // mnemonicを受け取って対応したバイナリを返す
}

pub fn jump(mnemonic: Option<String>) -> String {
    // mnemonicを受け取って対応したバイナリを返す
}

SymbolTableモジュール

このモジュールでは、a_commandとl_commandでのsymbolを扱います。codeモジュールと同じように予めHashMapに定義されているものあるのですが、 今回は.asmファイルをparseしている途中で新しく出てきたsymbolをHashMapに詰める作業が必要になります。

symbol_table.rs

pub struct SymbolTable {
    pub l_variable_address: u32,
    pub symbol_addresses: HashMap<String, String>,
}

impl SymbolTable {
    pub fn new() -> SymbolTable {
        let mut m = HashMap::new();
        m.insert("SP".to_string(), "0000000000000000".to_string());

        SymbolTable {
            l_variable_address: 0,
            symbol_addresses: m,
        }
    }
    pub fn add_entry(&mut self, key: String, address: String) {
        // 定義済みでないシンボルを定義した時にsymbol_tableに追加する
    }

    pub fn contains(&self, key: String) -> bool {
        // 受け取ったkeyがsymbol_tableに含まれているかどうか？
    }

    pub fn get_address(&self, key: String) -> Option<String> {
        // 受け取ったkeyに対応するバイナリを返す
    }
}

上記のモジュールを組み合わせたもの

以上三つのモジュールを組み合わせて、下記のようにすれば完成です。 ループを二回回すのはl_commandのアドレスを確定させるためです。

main.rs

fn main() {
    const INPUT_FILE_REGEX: &str = r"^(.+)\.asm$";
    let args: Vec<String> = env::args().collect();
    let input_file_name = &args[1];

    let f = File::open(input_file_name).unwrap();
    let f = BufReader::new(f);

    let mut parser = parser::Parser::new(f);
    let mut symbol_table = symbol_table::SymbolTable::new();

    // 一度目のループ
    loop {
        // 一行進める
        let bytes = parser.advance();
        // EOFの時にループを終了する
        if bytes == 0 {
            break;
        }

        // コメントなどの時にループを進める
        if !parser.has_more_commands() {
            continue;
        }

        if let Some(symbol) = parser.symbol() {
            match symbol.clone().parse::<u32>() {
                // symbolを受け取ってl_commandかsymbol_tableに含まれてなかったらtableに追加する
            }
        }


        if parser.a_command() || parser.c_command() {
            symbol_table.l_variable_address += 1;
        }
    }

    // 省略

    // 二度目のループ
    loop {
        let bytes = parser.advance();
        if bytes == 0 {
            break;
        }

        if !parser.has_more_commands() {
            continue;
        }

        if let Some(symbol) = parser.symbol() {
            match symbol.clone().parse::<u32>() {
                // symbolが整数だったときはバイナリに変換して詰める
                // そうでないときは、symbol_tableから引っ張ってきたり、新たにsymbol_tableに詰めたりする    
            };
        }

        // c_commandの領域ごとにバイナリを取得する
        let dest = code::dest(parser.dest());
        let comp = code::comp(parser.comp());
        let jump = code::jump(parser.jump());

        if parser.c_command() {
            // c_commandのバイナリを合わせて詰める
        }
    }

    // 省略

    // ファイルの出力
    fs::write(
        format!("tmp/{}.hack", output_file_name),
        format!("{}\n", addresses.join("\n")),
    )
    .unwrap();
}

以上でざっくりとした説明終了です。 めちゃめちゃざっくり書いたので、細かい部分はこちらを見てください。

最後に

以前自作ブラウザを作ろうとして（まだWIP）HTML・CSS parserを作ったことがあったので、思っていたよりもすんなり実装することができました。 この本は全部で13章あるので、まだまだ先は長いですが、じっくりやっていこうと思います。大学がオンライン授業になったので、良い感じに時間が取れそうです。

Rust