2016年2月15日月曜日

開発環境

  • OS X El Capitan - Apple (OS)
  • Emacs(Text Editor)
  • Java (実行環境)
  • Python 3.5(プログラミング言語)

コンピュータシステムの理論と実装 (Noam Nisan (著)、Shimon Schocken (著)、斎藤 康毅(翻訳)、オライリージャパン)の8章(バーチャルマシン#2 : プログラム制御)、8.5(プロジェクト)を取り組んでみる。

8.5(プロジェクト)

コード(Emacs)

VMTranslator.py

#!/usr/bin/env python3
# -*- coding: utf-8 -*-

import os
import sys
import glob


class Parser:

    def nextLine(self):
        for line in self.file:
            i = line.find('//')
            if i != -1:
                line = line[:i]
            line = line.strip()
            if line != '':
                self.next = line
                break
        else:
            self.next = ''

    def __init__(self, file):
        self.file = file
        self.cur = None
        self.nextLine()

    def hasMoreCommands(self):
        return self.next != ''

    def advance(self):
        self.cur = self.next
        self.nextLine()

    def commandType(self):
        cmd = self.cur.split()[0]
        if cmd == 'add' or cmd == 'sub' or cmd == 'neg' or cmd == 'eq' or \
           cmd == 'gt' or cmd == 'lt' or cmd == 'and' or cmd == 'or' or \
           cmd == 'not':
            return 'C_ARITHMETIC'
        if cmd == 'push':
            return 'C_PUSH'
        if cmd == 'pop':
            return 'C_POP'
        if cmd == 'label':
            return 'C_LABEL'
        if cmd == 'goto':
            return 'C_GOTO'
        if cmd == 'if-goto':
            return 'C_IF'
        if cmd == 'function':
            return 'C_FUNCTION'
        if cmd == 'return':
            return 'C_RETURN'
        if cmd == 'call':
            return 'C_CALL'

    def arg1(self):
        if self.commandType() == 'C_ARITHMETIC':
            return self.cur.split()[0]
        if self.commandType() != 'C_RETURN':
            return self.cur.split()[1]

    def arg2(self):
        cmd_type = self.commandType()
        if cmd_type == 'C_PUSH' or cmd_type == 'C_POP' or \
           cmd_type == 'C_FUNCTION' or cmd_type == 'C_CALL':
            return int(self.cur.split()[2])


class CodeWriter:
    label_i = 0

    def makeLabel():
        label = 'label{0}'.format(CodeWriter.label_i)
        CodeWriter.label_i += 1
        return label

    def __init__(self, fileName):
        self.setFileName(fileName)
        self.cur_func = ''
        self.writeInit()
        self.static_file = ''

    def setFileName(self, fileName):
        self.file = open(fileName, 'w')

    def writeInit(self):
        print('@256',
              'D=A',
              '@SP',
              'M=D', sep='\n', file=self.file)
        self.writeCall('Sys.init', 0)

    def writeArithmetic(self, command):
        if command == 'add':
            print('@SP',
                  'M=M-1',
                  'A=M',
                  'D=M',
                  'A=A-1',
                  'M=D+M', sep='\n', file=self.file)
        elif command == 'sub':
            print('@SP',
                  'M=M-1',
                  'A=M',
                  'D=M',
                  'A=A-1',
                  'M=M-D', sep='\n', file=self.file)
        elif command == 'neg':
            print('@SP',
                  'A=M-1',
                  'M=-M', sep='\n', file=self.file)
        elif command == 'eq':
            label_true = CodeWriter.makeLabel()
            label_end = CodeWriter.makeLabel()
            print('@SP',
                  'M=M-1',
                  'A=M',
                  'D=M',
                  'A=A-1',
                  'D=M-D',
                  '@{0}'.format(label_true),
                  'D;JEQ',
                  'D=0',
                  '@{0}'.format(label_end),
                  '0;JMP',
                  '({0})'.format(label_true),
                  'D=-1',
                  '({0})'.format(label_end),
                  '@SP',
                  'A=M-1',
                  'M=D', sep='\n', file=self.file)
        elif command == 'gt':
            label_true = CodeWriter.makeLabel()
            label_end = CodeWriter.makeLabel()
            print('@SP',
                  'M=M-1',
                  'A=M',
                  'D=M',
                  'A=A-1',
                  'D=M-D',
                  '@{0}'.format(label_true),
                  'D;JGT',
                  'D=0',
                  '@{0}'.format(label_end),
                  '0;JMP',
                  '({0})'.format(label_true),
                  'D=-1',
                  '({0})'.format(label_end),
                  '@SP',
                  'A=M-1',
                  'M=D', sep='\n', file=self.file)
        elif command == 'lt':
            label_true = CodeWriter.makeLabel()
            label_end = CodeWriter.makeLabel()
            print('@SP',
                  'M=M-1',
                  'A=M',
                  'D=M',
                  'A=A-1',
                  'D=M-D',
                  '@{0}'.format(label_true),
                  'D;JLT',
                  'D=0',
                  '@{0}'.format(label_end),
                  '0;JMP',
                  '({0})'.format(label_true),
                  'D=-1',
                  '({0})'.format(label_end),
                  '@SP',
                  'A=M-1',
                  'M=D', sep='\n', file=self.file)
        elif command == 'and':
            print('@SP',
                  'M=M-1',
                  'A=M',
                  'D=M',
                  'A=A-1',
                  'M=D&M', sep='\n', file=self.file)
        elif command == 'or':
            print('@SP',
                  'M=M-1',
                  'A=M',
                  'D=M',
                  'A=A-1',
                  'M=D|M', sep='\n', file=self.file)
        elif command == 'not':
            print('@SP',
                  'A=M-1',
                  'M=!M', sep='\n', file=self.file)

    def writePushPop(self, command, segment, index):
        if command == 'C_PUSH':
            if segment == 'argument':
                print('@ARG',
                      'A=M', sep='\n', file=self.file)
                for _ in range(index):
                    print('A=A+1', file=self.file)
                print('D=M',
                      '@SP',
                      'A=M',
                      'M=D',
                      '@SP',
                      'M=M+1', sep='\n', file=self.file)
            elif segment == 'local':
                print('@LCL',
                      'A=M', sep='\n', file=self.file)
                for _ in range(index):
                    print('A=A+1', file=self.file)
                print('D=M',
                      '@SP',
                      'A=M',
                      'M=D',
                      '@SP',
                      'M=M+1', sep='\n', file=self.file)
            elif segment == 'static':
                if self.static_file != '':
                    s = os.path.basename(self.static_file).replace('.vm', '')
                else:
                    s = os.path.basename(self.file.name).replace('.asm', '')
                print('@{0}.{1}'.format(s, index),
                      'D=M',
                      '@SP',
                      'A=M',
                      'M=D',
                      '@SP',
                      'M=M+1', sep='\n', file=self.file)
            elif segment == 'constant':
                print('@{0}'.format(index),
                      'D=A',
                      '@SP',
                      'A=M',
                      'M=D',
                      '@SP',
                      'M=M+1', sep='\n', file=self.file)
            elif segment == 'this':
                print('@THIS',
                      'A=M', sep='\n', file=self.file)
                for _ in range(index):
                    print('A=A+1', file=self.file)
                print('D=M',
                      '@SP',
                      'A=M',
                      'M=D',
                      '@SP',
                      'M=M+1', sep='\n', file=self.file)
            elif segment == 'that':
                print('@THAT',
                      'A=M', sep='\n', file=self.file)
                for _ in range(index):
                    print('A=A+1', file=self.file)
                print('D=M',
                      '@SP',
                      'A=M',
                      'M=D',
                      '@SP',
                      'M=M+1', sep='\n', file=self.file)
            elif segment == 'pointer':
                if index == 0:
                    print('@THIS',
                          'D=M',
                          '@SP',
                          'A=M',
                          'M=D',
                          '@SP',
                          'M=M+1', sep='\n', file=self.file)
                elif index == 1:
                    print('@THAT',
                          'D=M',
                          '@SP',
                          'A=M',
                          'M=D',
                          '@SP',
                          'M=M+1', sep='\n', file=self.file)
            elif segment == 'temp':
                i = 5 + index
                print('@{0}'.format(i),
                      'D=M',
                      '@SP',
                      'A=M',
                      'M=D',
                      '@SP',
                      'M=M+1', sep='\n', file=self.file)
        elif command == 'C_POP':
            if segment == 'argument':
                print('@SP',
                      'M=M-1',
                      'A=M',
                      'D=M',
                      '@ARG',
                      'A=M', sep='\n', file=self.file)
                for _ in range(index):
                    print('A=A+1', file=self.file)
                print('M=D', file=self.file)
            elif segment == 'local':
                print('@SP',
                      'M=M-1',
                      'A=M',
                      'D=M',
                      '@LCL',
                      'A=M', sep='\n', file=self.file)
                for _ in range(index):
                    print('A=A+1', file=self.file)
                print('M=D', file=self.file)
            elif segment == 'static':
                if self.static_file != '':
                    s = os.path.basename(self.static_file).replace('.vm', '')
                else:
                    s = os.path.basename(self.file.name).replace('.asm', '')
                print('@SP',
                      'M=M-1',
                      'A=M',
                      'D=M',
                      '@{0}.{1}'.format(s, index),
                      'M=D', sep='\n', file=self.file)
            elif segment == 'this':
                print('@SP',
                      'M=M-1',
                      'A=M',
                      'D=M',
                      '@THIS',
                      'A=M', sep='\n', file=self.file)
                for _ in range(index):
                    print('A=A+1', file=self.file)
                print('M=D', file=self.file)
            elif segment == 'that':
                print('@SP',
                      'M=M-1',
                      'A=M',
                      'D=M',
                      '@THAT',
                      'A=M', sep='\n', file=self.file)
                for _ in range(index):
                    print('A=A+1', file=self.file)
                print('M=D', file=self.file)
            elif segment == 'pointer':
                if index == 0:
                    print('@SP',
                          'M=M-1',
                          'A=M',
                          'D=M',
                          '@THIS',
                          'M=D', sep='\n', file=self.file)
                elif index == 1:
                    print('@SP',
                          'M=M-1',
                          'A=M',
                          'D=M',
                          '@THAT',
                          'M=D', sep='\n', file=self.file)
            elif segment == 'temp':
                i = 5 + index
                print('@SP',
                      'M=M-1',
                      'A=M',
                      'D=M',
                      '@{0}'.format(i),
                      'M=D', sep='\n', file=self.file)

    def writeLabel(self, label):
        print('({0}${1})'.format(self.cur_func, label), file=self.file)

    def writeGoto(self, label):
        print('@{0}${1} // goto'.format(self.cur_func, label),
              '0;JMP    // goto end', sep='\n', file=self.file)

    def writeIf(self, label):
        print('@SP // if-goto',
              'M=M-1',
              'A=M',
              'D=M',
              '@{0}${1}'.format(self.cur_func, label),
              'D;JNE // if-goto end', sep='\n', file=self.file)

    def writeFunction(self, functionName, numLocals):
        self.cur_func = functionName
        print('({0}) // function'.format(functionName), file=self.file)
        for _ in range(numLocals):
            self.writePushPop('C_PUSH', 'constant', 0)

    def writeReturn(self):
        print('@LCL // return',
              'D=M',
              '@R13',
              'M=D',
              '@5',
              'A=D-A',
              'D=M',
              '@R14',
              'M=D', sep='\n', file=self.file)
        self.writePushPop('C_POP', 'argument', 0)
        print('@ARG',
              'A=M',
              'D=A+1',
              '@SP',
              'M=D',
              '@R13',
              'A=M-1',
              'D=M',
              '@THAT',
              'M=D',
              '@R13',
              'A=M-1',
              'A=A-1',
              'D=M',
              '@THIS',
              'M=D',
              '@R13',
              'A=M-1',
              'A=A-1',
              'A=A-1',
              'D=M',
              '@ARG',
              'M=D',
              '@R13',
              'A=M-1',
              'A=A-1',
              'A=A-1',
              'A=A-1',
              'D=M',
              '@LCL',
              'M=D',
              '@R14',
              'A=M',
              '0;JMP', sep='\n', file=self.file)

    def writeCall(self, functionName, numArgs):
        label = '{0}${1}'.format(self.cur_func, CodeWriter.makeLabel())
        print('@{0} // call'.format(label),
              'D=A',
              '@SP',
              'A=M',
              'M=D',
              '@SP',
              'M=M+1',
              '@LCL',
              'D=M',
              '@SP',
              'A=M',
              'M=D',
              '@SP',
              'M=M+1',
              '@ARG',
              'D=M',
              '@SP',
              'A=M',
              'M=D',
              '@SP',
              'M=M+1',
              '@THIS',
              'D=M',
              '@SP',
              'A=M',
              'M=D',
              '@SP',
              'M=M+1',
              '@THAT',
              'D=M',
              '@SP',
              'A=M',
              'M=D',
              '@SP',
              'M=M+1',
              '@SP',
              'D=M',
              '@{0}'.format(numArgs),
              'D=D-A',
              '@5',
              'D=D-A',
              '@ARG',
              'M=D',
              '@SP',
              'D=M',
              '@LCL',
              'M=D',
              '@{0}'.format(functionName),
              '0;JMP',
              '({0})'.format(label), sep='\n', file=self.file)

        # self.writeGoto(functionName)

    def close(self):
        self.file.close()

if __name__ == '__main__':
    filename = sys.argv[1]
    if os.path.isfile(filename):
        outfilename = filename.replace('.vm', '.asm')
        files = [filename]
    elif os.path.isdir(filename):
        outfilename = '{0}{1}{2}.asm'.format(
            filename, os.path.sep, os.path.basename(filename))
        files = glob.glob('{0}/*.vm'.format(filename))

    codeWriter = CodeWriter(outfilename)
    for file in files:
        codeWriter.static_file = os.path.basename(file)
        with open(file) as f:
            parser = Parser(f)
            while parser.hasMoreCommands():
                parser.advance()
                cmd_type = parser.commandType()
                if cmd_type == 'C_ARITHMETIC':
                    codeWriter.writeArithmetic(parser.arg1())
                elif cmd_type == 'C_PUSH' or cmd_type == 'C_POP':
                    codeWriter.writePushPop(cmd_type, parser.arg1(),
                                            parser.arg2())
                elif cmd_type == 'C_LABEL':
                    codeWriter.writeLabel(parser.arg1())
                elif cmd_type == 'C_GOTO':
                    codeWriter.writeGoto(parser.arg1())
                elif cmd_type == 'C_IF':
                    codeWriter.writeIf(parser.arg1())
                elif cmd_type == 'C_FUNCTION':
                    codeWriter.writeFunction(parser.arg1(), parser.arg2())
                elif cmd_type == 'C_RETURN':
                    codeWriter.writeReturn()
                elif cmd_type == 'C_CALL':
                    codeWriter.writeCall(parser.arg1(), parser.arg2())
                else:
                    print("error: command type: '{0}'".format(cmd_type),
                          file=sys.stderr)
                    sys.exit(1)

入出力結果(Terminal, IPython)

$ ./VMTranslator.py ProgramFlow/BasicLoop/BasicLoop.vm
$ ./VMTranslator.py ProgramFlow/FibonacciSeries/FibonacciSeries.vm
$ ./VMTranslator.py FunctionCalls/SimpleFunction/SimpleFunction.vm
$ ./VMTranslator.py FunctionCalls/FibonacciElement
$ ./VMTranslator.py FunctionCalls/StaticsTest
$ ./VMTranslator.py FunctionCalls/NestedCall
$ 

0 コメント:

コメントを投稿

Comments on Google+: