Brainfuck解释器[on python]

阿婆主脑容量不够，ぜんぜん不能在大脑中运行 Brainfuck 程序，而且发现连运行过程都想不出来啊， 然而就这么几个字符完全可以自己写解释器嘛，并且可以打印出运行过程，而且可以试试看做成playground 的形式呢，想想还是挺有趣的。

项目地址： Code CSDN

Git地址： Git on CSDN

Brainfuck

Brainfuck是一种图灵完备的语言，他可以做到任何事情，他的编译器是世界上最小的，他共有8个操作符：

基本就是对内存直接操作的语言，他的『Hello World!』是这样的：

“++++++++[>++++[>++>+++>+++>+««-]>+>+>-»+[<]<-]».>—.+++++++..+++.».<-.<.+++.——.——–.»+.>++.”

WTF!!!!!!

需求点

• 1、基本功能

  • 解释裸BF程序
  • 打印内存信息
  • 分开输出以及集体输出

• 2、调试功能

  • 设置断点
  • 单步执行
  • 查看内存

• 3、playground功能

  • 做命令行模式（加参数可选）
  • 窗口分割
  • 实时解释

基本功能实现

Brainfuck基本解释使用class BF()来实现

数据部分

class BF()中数据由两部分组成：

• Brainfuck程序
• 内存

BF直接对内存进行操作，所以这边可以很简单的用list模拟出来，这样我们就有了一个无限长的内存，并用BF.position来指明正在操作的内存，相当于一个指针（实际是list index）。另外一个就是代码存储区，代码由string类型的BF.code保存，同样有个代码指针BF.codePosition指明目前正在解释的操作符.

def __init__(self):
	self.codeInit()
	self.ifRuntime = True
	
def memoryInit(self):
	self.dirty = False     # if memory have been wroten
	self.memory = [0]      # memory
	self.position = 0      # pointer to memory which byte now operating
	self.codePosition = 0  # pointer to code which operator now parsing
	self.result = ''       # store whole program output
	
def codeInit(self, code = None):
	if None == code:       # for object init without BF code
	    self.code = ''
	
	self.code = code
	self.memoryInit()

操作符动作

操作符没有一点难度,按照wiki来解释。

def getChar(self):
    return self.memory[self.position]

'''operators'''
def printChar(self):
    print "echo: ",
    print chr(self.memory[self.position])    # turn to ASCII char
    self.result += chr(self.memory[self.position])  # store output
def inputChar(self):
    print "put in: ",
    self.memory[self.position] = ord(sys.stdin.read(1))
def increment(self):
    self.memory[self.position] += 1
def decrement(self):
    self.memory[self.position] -= 1
def next(self):
    self.position += 1
    if len(self.memory) <= self.position:
        self.memory.append(0)
def previous(self):
    self.position -= 1
    if 0 > self.position:
        print 'error: position is %d'%self.position
        print printMemory()

循环实现

循环实现比较麻烦，本来只简单地想到一对括号的情况，后面发现了多对括号的问题，就先使用direction来保存括号在代码中的位子。并且用stack来先记录左括号。

首先在loopParser()中记录成对的括号位置，同时意味着循环开始结束地址也被记录了下来。在这个函数中，首先使用stack来登记未配对左括号地址，并在出现右括号时，弹出一个左括号地址，与右括号地址配对，写入loopMap这个direction**中，同样这个地址配对记录需要返回给主解析流程的。

在主流程中，通过loopParser()获得loopMap后,就开始对整个BF代码进行解释。此时根据wiki中的操作符作用，遇到**[**时检查当前指针内容是否为0，为0则不进入循环，直接跳到对应的**]**地址上，遇到**]**时，当前指针内容不为0，则跳回到对应**[**代码地址，继续循环。

def loopParser(self, code):
    '''parse loop operator, recode the position of code'''
    loopMap = {}
    leftStack = []
    codePosition = 0
    leftNum = 0
    rightNum = 0
    for operator in code:
        if operator == '[':
            leftStack.append(codePosition)
            leftNum += 1
        elif operator == ']':
            leftPosition = leftStack.pop()
            rightPosition = codePosition
            loopMap[leftPosition] = rightPosition
            loopMap[rightPosition] = leftPosition
            rightNum += 1
        codePosition += 1

    if 0 != len(leftStack):
        print "error: there are %d '[' but %d ']'"
        loopMap = None

    return loopMap


def parser(self, code = None):
    '''parse code'''
    if None == code:
        code = self.code
        self.memoryInit()

    loopMap = self.loopParser(code)
    if None == loopMap:
        return

    if None == code:
        code = self.code

    while self.codePosition < len(code):
        operator = code[self.codePosition]
        if operator == ">":
            self.next()
        elif operator == "<":
            self.previous()
        elif operator == "+":
            self.increment()
        elif operator == "-":
            self.decrement()
        elif operator == ".":
            self.printChar()
        elif operator == ",":
            self.inputChar()
        elif operator == "[" and self.getChar() == 0:
            self.codePosition = loopMap[self.codePosition]
        elif operator == "]" and self.getChar() != 0:
            self.codePosition = loopMap[self.codePosition]
        self.runtime()
        self.codePosition += 1

打印runtime

做这个解释器的主要原因就是，看不懂Brainfuck每一步为什么要这样做，所以解释器的重点就在于打印每一步的数据内存和代码内存，并且标出目前运行到哪里了。

Global function:

	def printChar(char, point = False):
		if point:
		    char = '\033[31m%s\033[0m' %char  # print red chars on Unix
		
		sys.stdout.write(char + ' ')


BF() method:

    def printData(self, data, position):
        '''print linear data and point the position now point'''
        point = False
        for nowPosition in xrange(0, len(data)):
            if nowPosition == position:
                point = True

            printChar(str(data[nowPosition]), point)
            point = False
        print ""                 # printChar don't print '\n'

    def runtime(self):
        '''print runtime memory and code'''
        if self.ifRuntime:
            self.printData(self.code, self.codePosition)
            self.printData(self.memory, self.position)

基本功能运行结果

未完待续。。。或者。。。