2012年5月4日金曜日

bf処理系 (python non-eval)

このエントリーをブックマークに追加 このエントリーを含むはてなブックマーク
んで、文字列のリスト化を踏まえてbrainf**kの処理系をかけとのお題が...

pythonを用いたnon-eval version。結構苦戦した。「ブロック」の扱いを正しく理解していなかった。

from sys import stdout


debug = True
class BF:
  '''
  see http://en.wikipedia.org/wiki/Brainfuck
  >>> tape = "++++++++++[>+++++++>++++++++++>+++>+<<<<-]>++.>+.+++++++..+++.>++.<<+++++++++++++++.>.+++.------.--------.>+.>."
  >>> bf = BF(tape)
  >>> bf.run()
  Hello,World!

  >>> 
  '''
  ops = {
    '>': 'incp',
    '<': 'decp',
    '+': 'incd',
    '-': 'decd',
    '.': 'putc',
    ',': 'readc',
    '[': 'blockstart',
    ']': 'blockend',
  }
  
  def __init__(self, xs, data=None, ptr=None, dryrun=None, parent=None):
    self.parent = parent
    self.terminate = False
    self.orig = str(xs)
    self.xs = str(xs)
    if dryrun is None or not dryrun :
      self.dryrun=False
    else:
      self.dryrun=True
    if debug:
      print self, self.parent, self.dryrun

    if ptr is None:
      self.ptr = 0
    else:
      self.ptr = ptr
    if data is None:
      # assuming ptr is of type unsigned char* and has been initialized to point
      # to an array of zeroed bytes:
      self.data = [0 for i in range(30000)]
    else:
      self.data = data
    self.sub = None

  def run(self):
    while self.xs and not self.terminate:
      x = self.xs[0]
      self.xs = self.xs[1:]
      if debug:
        print self.ptr, self.data[:5], self.xs
        print x, self.dryrun, self.parent
      name = self.ops[x]
      if self.dryrun:
        if name not in ("blockstart",  "blockend"):
          name = 'null'
      handler = getattr(self, 'handle_' + name )
      handler() 
      
  def handle_null(self):
    pass
    
  def handle_incp(self):
    '>'
    self.ptr += 1
    
  def handle_decp(self):
    '<'
    self.ptr -= 1
    
  def handle_incd(self):
    '+'
    self.data[self.ptr] += 1
    
  def handle_decd(self):
    '-'
    self.data[self.ptr] -= 1
    
  def handle_putc(self):
    '.'
    #print self.data[self.ptr]
    stdout.write(chr(self.data[self.ptr]))
    stdout.flush()
    
  def handle_readc(self):
    ','
    # not used in Hello,World!
    pass
    
  def handle_blockstart(self):
    '['
    '''
      if the byte at the data pointer is zero, then instead of moving the
      instruction pointer forward to the next command, jump it forward to the
      command after the matching ] command*.
    '''
    if self.data[self.ptr] and not self.dryrun:
      # go into block
      dryrun = False 
    else:
      # skip until matching ']'
      dryrun = True 

    self.sub = BF(self.xs, self.data, self.ptr, dryrun, self)
    self.sub.run()
    if debug:
      print 'leaving', self.sub
   
    #write back child state
    self.data = self.sub.data #not needed. 
    self.ptr = self.sub.ptr
    self.xs = self.sub.xs

  def handle_blockend(self):
    '''
      if the byte at the data pointer is nonzero, then instead of moving the
      instruction pointer forward to the next command, jump it back to the command
      after the matching [ command*.
    '''
    ']'
    if self.data[self.ptr] and not self.dryrun:
      #jump back by rewind
      self.xs = '[' + self.orig 
    else:
      #step out 
      pass
    self.terminate = True


if __name__ == "__main__":
  #import doctest
  #doctest.testmod()
  #tape = "++++++++++[>+++++++>++++++++++>+++>+<<<<-]>++.>+.+++++++..+++.>++.<<+++++++++++++++.>.+++.------.--------.>+.>."
  #tape = "[][]" 
  tape ='''+++[>+++++<-]>[>+>+++>+>++>+++++>++<[++<]>---]>->-.[>++>+<<--]>--.--.+.>>>++.<<'''\
      + '''.<------.+.+++++.>>-.<++++.<--.>>>.<<---.<.-->-.>+.[+++++.---<]>>[.--->]<<.<+.+'''\
      + '''+.++>+++[.<][.]<++.'''
  #tape = "[[]]" 
  print tape
  debug =False


  bf = BF(tape)
  bf.run()
    

0 件のコメント: