VM Translator for nand2tetris project 7 -- written in Rust.

BasicTest.asm

// Example output for VM Translator for nand2tetris project 7 -- written in Rust.
// CC BY-SA 4.0 -- https://creativecommons.org/licenses/by-sa/4.0/

// Initialize stack pointer
@256
D=A
@SP
M=D

// Push 10 onto the stack
@10
D=A
@SP
A=M
M=D
@SP
M=M+1

// Pop the stack into LCL[0]
@0
D=A
@LCL
D=M+D
@R13
M=D
@SP
AM=M-1
D=M
@R13
A=M
M=D

// Push 21 onto the stack
@21
D=A
@SP
A=M
M=D
@SP
M=M+1

// Push 22 onto the stack
@22
D=A
@SP
A=M
M=D
@SP
M=M+1

// Pop the stack into ARG[2]
@2
D=A
@ARG
D=M+D
@R13
M=D
@SP
AM=M-1
D=M
@R13
A=M
M=D

// Pop the stack into ARG[1]
@1
D=A
@ARG
D=M+D
@R13
M=D
@SP
AM=M-1
D=M
@R13
A=M
M=D

// Push 36 onto the stack
@36
D=A
@SP
A=M
M=D
@SP
M=M+1

// Pop the stack into THIS[6]
@6
D=A
@THIS
D=M+D
@R13
M=D
@SP
AM=M-1
D=M
@R13
A=M
M=D

// Push 42 onto the stack
@42
D=A
@SP
A=M
M=D
@SP
M=M+1

// Push 45 onto the stack
@45
D=A
@SP
A=M
M=D
@SP
M=M+1

// Pop the stack into THAT[5]
@5
D=A
@THAT
D=M+D
@R13
M=D
@SP
AM=M-1
D=M
@R13
A=M
M=D

// Pop the stack into THAT[2]
@2
D=A
@THAT
D=M+D
@R13
M=D
@SP
AM=M-1
D=M
@R13
A=M
M=D

// Push 510 onto the stack
@510
D=A
@SP
A=M
M=D
@SP
M=M+1

// Pop the stack into TEMP[6]
@6
D=A
@5
D=D+A
@R13
M=D
@SP
AM=M-1
D=M
@R13
A=M
M=D

// Push LCL[0] onto the stack
@0
D=A
@LCL
A=M+D
D=M
@SP
A=M
M=D
@SP
M=M+1

// Push THAT[5] onto the stack
@5
D=A
@THAT
A=M+D
D=M
@SP
A=M
M=D
@SP
M=M+1

// Pop 2 from the stack, add, and put result on the stack.
@SP
AM=M-1
D=M
@SP
A=M-1
M=D+M

// Push ARG[1] onto the stack
@1
D=A
@ARG
A=M+D
D=M
@SP
A=M
M=D
@SP
M=M+1

// Pop 2 from the stack, subtract, and put result on the stack.
@SP
AM=M-1
D=M
@SP
A=M-1
M=M-D

// Push THIS[6] onto the stack
@6
D=A
@THIS
A=M+D
D=M
@SP
A=M
M=D
@SP
M=M+1

// Push THIS[6] onto the stack
@6
D=A
@THIS
A=M+D
D=M
@SP
A=M
M=D
@SP
M=M+1

// Pop 2 from the stack, add, and put result on the stack.
@SP
AM=M-1
D=M
@SP
A=M-1
M=D+M

// Pop 2 from the stack, subtract, and put result on the stack.
@SP
AM=M-1
D=M
@SP
A=M-1
M=M-D

// Push TEMP[6] onto the stack
@6
D=A
@5
A=D+A
D=M
@SP
A=M
M=D
@SP
M=M+1

// Pop 2 from the stack, add, and put result on the stack.
@SP
AM=M-1
D=M
@SP
A=M-1
M=D+M

// End of program
(end)
@end
0;JMP

main.rs

// VM Translator for nand2tetris project 7 -- written in Rust.
// CC BY-SA 4.0 -- https://creativecommons.org/licenses/by-sa/4.0/
use std::env;
use std::fs::File;
use std::io;
use std::io::{BufRead, BufReader, BufWriter, Read, Write};
use std::path::Path;

fn main() {
    let args: Vec<String> = env::args().collect();
    match args.len() {
        2 => {
            let in_name = &args[1];        
            let out_path = Path::new(in_name).with_extension("asm");
            let out_name = out_path.to_str().unwrap();
            let parser = Parser::new(in_name).unwrap();
            let mut writer = Writer::new(&out_name).unwrap();
            writer.write_prelude().unwrap();
            for element in parser {
                writer.write(element).unwrap();
            }   
            writer.write_terminator().unwrap();         
        }
        _ => {
            println!("Usage: vm-to-hack input_file");
        }
    }
}

// The implementation below somewhat follows the "proposed" VM translator implementation
// from the nand2tetris book, although this is possibly not idiomatic Rust.
// See: http://nand2tetris.org/lectures/PDF/lecture%2007%20virtual%20machine%20I.pdf

#[derive(Debug)]
enum ArithmeticCommand {
    // These commands pop off the stack, compute, and then push the result back onto the stack.
    Add,    // x + y
    Sub,    // x - y
    Neg,    // -y
    Eq,     // x == y
    Gt,     // x > y
    Lt,     // x < y
    And,    // x & y
    Or,     // x | y
    Not,    // !y
}

#[derive(Debug)]
enum MemorySegment {
    Local,
    Argument,
    This,
    That,
    Pointer,
    Temp,
    Constant,
    Static,
}

#[derive(Debug)]
enum Command {
    Arithmetic(ArithmeticCommand),
    Push(MemorySegment, i32),
    Pop(MemorySegment, i32),
    // Other symbols to be handled in later chapters.    
}

struct Parser<R: Read> {
    reader: BufReader<R>
}

impl Parser<File> {
    fn new(in_name: &str) -> io::Result<Self>  {
        let in_file = try!(File::open(in_name));
        let reader = BufReader::new(in_file);

        Ok(Parser {reader: reader})
    } 
}

impl<R: Read> Iterator for Parser<R> {
    type Item = Command;

    fn next(&mut self) -> Option<Command> {
        let mut line = String::new();   // NOTE: Inefficient -- should reuse this for each iteration.
            
        loop {      
            line.clear();

            match self.reader.read_line(&mut line) {
                Ok(len) => {
                    if len == 0 {
                        // We've hit EOF.
                        return None;
                    }                    
                    let line = get_trimmed_line(&line);                    
                    if line.is_empty() {
                        // Skip this line.                       
                        continue;
                    }

                    let mut split = line.split_whitespace(); 
                    let command = split.next().unwrap();

                    if command == "push" {
                        let segment = memory_segment(split.next().unwrap());
                        let value = split.next().unwrap().parse::<i32>().unwrap();
                        return Some(Command::Push(segment, value))
                    } else if command == "pop" {
                        let segment = memory_segment(split.next().unwrap());
                        let value = split.next().unwrap().parse::<i32>().unwrap();
                        return Some(Command::Pop(segment, value))
                    } else if command == "add" {
                        return Some(Command::Arithmetic(ArithmeticCommand::Add))
                    } else if command == "sub" {
                        return Some(Command::Arithmetic(ArithmeticCommand::Sub))
                    } else if command == "neg" {
                        return Some(Command::Arithmetic(ArithmeticCommand::Neg))
                    } else if command == "eq" {
                        return Some(Command::Arithmetic(ArithmeticCommand::Eq))
                    } else if command == "gt" {
                        return Some(Command::Arithmetic(ArithmeticCommand::Gt))
                    } else if command == "lt" {
                        return Some(Command::Arithmetic(ArithmeticCommand::Lt))
                    } else if command == "and" {
                        return Some(Command::Arithmetic(ArithmeticCommand::And))
                    } else if command == "or" {
                        return Some(Command::Arithmetic(ArithmeticCommand::Or))
                    } else if command == "not" {
                        return Some(Command::Arithmetic(ArithmeticCommand::Not))
                    } else {
                        panic!("Invalid command: {:?}", command);
                    }                    
                },
                Err(_) => return None
            }            
        }
    }
}

// http://nand2tetris.org/07.php
// http://www1.idc.ac.il/tecs/book/chapter07.pdf
// http://www.shimonschocken.com/nand2tetris/lectures/PDF/lecture%2007%20virtual%20machine%20I.pdf

fn memory_segment(string: &str) -> MemorySegment {
    if string == "local" {
        return MemorySegment::Local
    } else if string == "argument" {
        return MemorySegment::Argument
    } else if string == "this" {
        return MemorySegment::This
    } else if string == "that" {
        return MemorySegment::That
    } else if string == "pointer" {
        return MemorySegment::Pointer
    } else if string == "temp" {
        return MemorySegment::Temp
    } else if string == "constant" {
        return MemorySegment::Constant
    } else if string == "static" {
        return MemorySegment::Static
    } else {
        panic!("Invalid memory segment: {:?}", string);
    }
}

fn get_trimmed_line(line: &str) -> &str {
    let mut line = line.trim();

    // Strip any comments
    if let Some(idx_comment) = line.find("//") {
        line = &line[0..idx_comment].trim();
    }

    return line;
}

struct Writer<W: Write> {
    writer: BufWriter<W>,
    jump_label_index: u16,
}

impl Writer<File> {
    fn new(out_name: &str) -> io::Result<Self>  {
        let out_file = try!(File::create(out_name));
        let writer = BufWriter::new(out_file);

        Ok(Writer {writer: writer, jump_label_index: 0})
    }    
}

impl<W: Write> Writer<W> {
    fn writeln(&mut self, string: &str) -> io::Result<()> {
        try!(self.writer.write(format!("{}\n", string).as_bytes()));

        Ok(())
    }

    fn write_prelude(&mut self) -> io::Result<()> {
        // Initialize stack pointer
        try!(self.writeln("// Initialize stack pointer"));
        try!(self.writeln("@256"));
        try!(self.writeln("D=A"));
        try!(self.writeln("@SP"));
        try!(self.writeln("M=D"));
        try!(self.writeln(""));

        Ok(())
    } 

    fn write(&mut self, command: Command) -> io::Result<()> {
        match command {
            Command::Push(memory_segment, value) => {
                match memory_segment {
                    MemorySegment::Constant => {
                        try!(self.writeln(&format!("// Push {} onto the stack", value)));
                        try!(self.load_value_into_d(value));
                        try!(self.write_push_d_onto_stack());
                    },
                    MemorySegment::Local => {
                        try!(self.writeln(&format!("// Push LCL[{}] onto the stack", value)));
                                                
                        try!(self.load_value_into_d(value));                        
                        try!(self.load_value_offset_by_d("LCL"));                        
                        try!(self.write_push_d_onto_stack());                        
                    },
                    MemorySegment::Argument => {
                        try!(self.writeln(&format!("// Push ARG[{}] onto the stack", value)));
                                                
                        try!(self.load_value_into_d(value));                        
                        try!(self.load_value_offset_by_d("ARG"));                        
                        try!(self.write_push_d_onto_stack());                        
                    },
                    MemorySegment::This => {
                        try!(self.writeln(&format!("// Push THIS[{}] onto the stack", value)));
                                                
                        try!(self.load_value_into_d(value));                        
                        try!(self.load_value_offset_by_d("THIS"));                        
                        try!(self.write_push_d_onto_stack());                        
                    },
                    MemorySegment::That => {
                        try!(self.writeln(&format!("// Push THAT[{}] onto the stack", value)));
                                                
                        try!(self.load_value_into_d(value));                        
                        try!(self.load_value_offset_by_d("THAT"));                        
                        try!(self.write_push_d_onto_stack());                        
                    },
                    MemorySegment::Pointer => {
                        try!(self.writeln(&format!("// Push POINTER[{}] onto the stack", value)));
                                                
                        try!(self.load_value_into_d(value));
                        try!(self.write_load_memory_with_base_into_d(3));
                        try!(self.write_push_d_onto_stack());                        
                    },
                    MemorySegment::Temp => {
                        try!(self.writeln(&format!("// Push TEMP[{}] onto the stack", value)));
                                                
                        try!(self.load_value_into_d(value));
                        try!(self.write_load_memory_with_base_into_d(5));                        
                        try!(self.write_push_d_onto_stack());                        
                    },
                    MemorySegment::Static => {
                        try!(self.writeln(&format!("// Push STATIC[{}] onto the stack", value)));

                        // For statics, we handle by emitting symbols.                        
                        try!(self.writeln(&format!("@static.{}", value)));      
                        try!(self.writeln("D=M"));
                        try!(self.write_push_d_onto_stack());                        
                    },
                }
            },
            Command::Pop(memory_segment, value) => { 
                match memory_segment {
                    MemorySegment::Constant => {
                        panic!("Can't pop into the constant segment -- that doesn't make sense.");
                    },
                    MemorySegment::Local => {  
                        try!(self.writeln(&format!("// Pop the stack into LCL[{}]", value)));
                        try!(self.write_pop_stack_to_segment("LCL", value));                                         
                    },
                    MemorySegment::Argument => {  
                        try!(self.writeln(&format!("// Pop the stack into ARG[{}]", value)));
                        try!(self.write_pop_stack_to_segment("ARG", value));                                         
                    },
                    MemorySegment::This => {  
                        try!(self.writeln(&format!("// Pop the stack into THIS[{}]", value)));
                        try!(self.write_pop_stack_to_segment("THIS", value));                                         
                    },
                    MemorySegment::That => {  
                        try!(self.writeln(&format!("// Pop the stack into THAT[{}]", value)));
                        try!(self.write_pop_stack_to_segment("THAT", value));                                         
                    },
                    MemorySegment::Pointer => {  
                        try!(self.writeln(&format!("// Pop the stack into POINTER[{}]", value)));                                                
                        try!(self.write_offset_from_base_into_d(3, value));                     
                        try!(self.write_pop_stack_to_d_as_addr());
                    },
                    MemorySegment::Temp => {  
                        try!(self.writeln(&format!("// Pop the stack into TEMP[{}]", value)));                                                
                        try!(self.write_offset_from_base_into_d(5, value));
                        try!(self.write_pop_stack_to_d_as_addr());
                    },
                    MemorySegment::Static => {  
                        try!(self.writeln(&format!("// Pop the stack into STATIC[{}]", value)));                                                

                        // For statics, we handle by emitting symbols. 
                        try!(self.writeln(&format!("@static.{}", value)));      
                        try!(self.writeln("D=A"));                       
                        try!(self.write_pop_stack_to_d_as_addr());
                    },
                }
             },
            Command::Arithmetic(arithmetic_command) => {
                match arithmetic_command {
                    ArithmeticCommand::Add => {
                        try!(self.writeln("// Pop 2 operands from the stack, add, and put result on the stack."));
                        try!(self.write_prelude_for_binary_arithmetic());
                        try!(self.writeln("M=D+M"));
                    },
                    ArithmeticCommand::Sub => {
                        try!(self.writeln("// Pop 2 operands from the stack, subtract, and put result on the stack."));
                        try!(self.write_prelude_for_binary_arithmetic());
                        try!(self.writeln("M=M-D"));
                    },
                    ArithmeticCommand::Neg => {
                        try!(self.writeln("// Pop 1 operand from the stack, negate, and put result on the stack."));
                        try!(self.write_prelude_for_unary_arithmetic());
                        try!(self.writeln("M=-M"));
                    },
                    ArithmeticCommand::Eq => {
                        try!(self.writeln("// Pop 2 operands from the stack, compare equality, and put result on the stack."));
                        try!(self.write_prelude_for_binary_arithmetic());
                        try!(self.write_compare_op("JEQ"));
                    },
                    ArithmeticCommand::Gt => {
                        try!(self.writeln("// Pop 2 operands from the stack, compare greater than, and put result on the stack."));
                        try!(self.write_prelude_for_binary_arithmetic());
                        try!(self.write_compare_op("JGT"));
                    },
                    ArithmeticCommand::Lt => {
                        try!(self.writeln("// Pop 2 operands from the stack, compare less than, and put result on the stack."));
                        try!(self.write_prelude_for_binary_arithmetic());
                        try!(self.write_compare_op("JLT"));
                    },
                    ArithmeticCommand::And => {
                        try!(self.writeln("// Pop 2 operands from the stack, AND them together, and put result on the stack."));
                        try!(self.write_prelude_for_binary_arithmetic());
                        try!(self.writeln("M=D&M"));
                    },
                    ArithmeticCommand::Or => {
                        try!(self.writeln("// Pop 2 operands from the stack, OR them together, and put result on the stack."));
                        try!(self.write_prelude_for_binary_arithmetic());
                        try!(self.writeln("M=D|M"));
                    },
                    ArithmeticCommand::Not => {
                        try!(self.writeln("// Pop 1 operand from the stack, NOT it, and put result on the stack."));
                        try!(self.write_prelude_for_unary_arithmetic());
                        try!(self.writeln("M=!M"));
                    },
                }                
            },
        }

        try!(self.writeln(""));
        Ok(())
    }

    fn write_prelude_for_unary_arithmetic(&mut self) -> io::Result<()> {
        // Load mem[sp - 1] into D.  We don't decrement SP because we'll be writing right back to it.
        try!(self.writeln("@SP"));
        try!(self.writeln("A=M-1"));                
        // M holds the operand we need to operate on.
        Ok(())
    }

    fn write_prelude_for_binary_arithmetic(&mut self) -> io::Result<()> {
        // Load mem[sp - 1] into D and decrement SP
        try!(self.writeln("@SP"));
        try!(self.writeln("AM=M-1"));        
        try!(self.writeln("D=M"));

        // Set address to mem[(original sp) - 2]. We don't decrement SP again because we'll be writing right back to it.
        try!(self.writeln("@SP"));
        try!(self.writeln("A=M-1"));
        
        // Now D and M hold the two operands we need to operate on, and the current address is set to the current location of the stack pointer.        
        Ok(())
    }

    fn load_value_into_d(&mut self, value: i32) -> io::Result<()> {
        // Load constant or offset into D
        try!(self.writeln(&format!("@{}", value)));
        try!(self.writeln("D=A"));    

        Ok(())
    }

    fn load_value_offset_by_d(&mut self, segment: &str) -> io::Result<()> {        
        try!(self.writeln(&format!("@{}", segment)));
        try!(self.writeln("A=M+D"));
        try!(self.writeln("D=M"));

        Ok(())
    }

    fn write_push_d_onto_stack(&mut self) -> io::Result<()> {
        // Push D onto the stack
        try!(self.writeln("@SP"));
        try!(self.writeln("A=M"));
        try!(self.writeln("M=D"));

        // Increment stack pointer
        try!(self.writeln("@SP"));
        try!(self.writeln("M=M+1"));          

        Ok(())
    }

    fn write_compare_op(&mut self, op: &str) -> io::Result<()> {
        // Prepare for comparison
        let current_jump_index = self.jump_label_index;

        try!(self.writeln("D=M-D"));
        try!(self.writeln(&format!("@j{}", current_jump_index)));
        try!(self.writeln(&format!("D;{}", op)));
        
        // Handle test failed
        try!(self.writeln("@SP"));
        try!(self.writeln("A=M-1"));
        try!(self.writeln("M=0"));
        try!(self.writeln(&format!("@j{}end", current_jump_index)));
        try!(self.writeln("0;JMP"));

        // Handle test passed        
        try!(self.writeln(&format!("(j{})", current_jump_index)));
        try!(self.writeln("@SP"));
        try!(self.writeln("A=M-1"));
        try!(self.writeln("M=-1"));

        // Terminating label
        try!(self.writeln(&format!("(j{}end)", current_jump_index)));
        self.jump_label_index = current_jump_index + 1;

        Ok(())
    }

    fn write_pop_stack_to_segment(&mut self, segment: &str, offset: i32) -> io::Result<()> {
        // Load offset into d and jump to segment + offset
        try!(self.writeln(&format!("@{}", offset)));                        
        try!(self.writeln("D=A"));
        try!(self.writeln(&format!("@{}", segment)));        
        try!(self.writeln("D=M+D"));                        

        try!(self.write_pop_stack_to_d_as_addr());

        Ok(())
    }

    fn write_pop_stack_to_d_as_addr(&mut self) -> io::Result<()> {
        // Stuff target address into R13
        try!(self.writeln("@R13"));
        try!(self.writeln("M=D"));

        // Pop stack into D and decrement stack pointer.                      
        try!(self.writeln("@SP"));
        try!(self.writeln("AM=M-1"));
        try!(self.writeln("D=M"));

        // Now go back to R13, jump to the target address and write D
        try!(self.writeln("@R13"));
        try!(self.writeln("A=M"));
        try!(self.writeln("M=D"));

        Ok(())
    }

    fn write_offset_from_base_into_d(&mut self, base: i32, offset: i32) -> io::Result<()> {                
        try!(self.writeln(&format!("@{}", offset)));                        
        try!(self.writeln("D=A"));
        // To adjust for POINTER or TEMP segments, need to offset by 3 or 5.
        try!(self.writeln(&format!("@{}", base)));                        
        try!(self.writeln("D=D+A"));  

        Ok(())
    }

    fn write_load_memory_with_base_into_d(&mut self, base: i32) -> io::Result<()> {
        // To adjust for POINTER or TEMP segments, need to offset by 3 or 5.
        try!(self.writeln(&format!("@{}", base)));      
        try!(self.writeln("A=D+A"));
        try!(self.writeln("D=M"));

        Ok(())
    }

    fn write_terminator(&mut self) -> io::Result<()> {
        try!(self.writeln("// End of program"));
        try!(self.writeln("(end)"));
        try!(self.writeln("@end"));
        try!(self.writeln("0;JMP"));

        Ok(())
    }   
}