Racc で Brainf*ck 、構文木

Ruby esoteric

取り敢えずルールはこんな感じかな。

program : expression

expression :
           | expression bracket
           | expression TERM

bracket : '[' expression ']'

終端記号は、「TERM」テープの扱いや入出力と括弧 '['、']'。一方「program」はまあ、最終的な左辺値として全体を代表する。それと同じものなのに更に「expression」を作ってるのは、「'['」「']'」で挟まれるものに「program」は無いだろうという思いもある。その「expression」は空を含む「bracket」と「TERM」の列。「bracket」はその「expression」を囲むもの。
その「bracket」のだけど

  1. 「[」ポインタ位置の数値が 0 以外なら何もしない、0 なら対応する「]」まで行き、その「]」の次からまた始める
  2. 「]」ポインタ位置の数値が 0 なら何もしない、0 以外なら対応する「[」まで戻り、その「[」の次からまた始める

対応する処理を考えると要するに while ループ(0 以外なら繰り返しを続ける) なわけだ。それが分かっているから次のようになる。だが、対応する括弧を行き来する気分が無くなってしまうのだけど。

class BrainF_ckParser
rule# class BrainF_ckParser

program : expression
  { result = RootNode.new val[0] }

expression :
  { result = NullNode.new }
           | expression bracket
  { result = ExpressionNode.new val[0], val[1] }
           | expression TERMINAL
  { result = ExpressionNode.new val[0], TerminalNode.new(val[1]) }

bracket : '[' expression ']'
  { result = BracketNode.new val[1] }

end # class BrainF_ckParser

---- inner
  def initialize(source)
    @source = source
    @tape = []
    @pointer = 0
  end # def initialize(source)

  def parse(opts = nil)
    @yydebug = opts.yydebug if opts.respond_to? :yydebug
    yyparse self, :scan
  end # def parse(opts = nil)

  private
  def scan
    @source.each_char do |c|
      case c
        when '>' then yield [:TERMINAL, :right]
        when '<' then yield [:TERMINAL, :left]
        when '+' then yield [:TERMINAL, :plus]
        when '-' then yield [:TERMINAL, :minus]
        when '.' then yield [:TERMINAL, :put]
        when ',' then yield [:TERMINAL, :get]
        when '[' then yield ['[', nil]
        when ']' then yield [']', nil]
      end # case c
    end # @source.each_char do |c|
    yield nil
  end # def scan

---- header
# -*- coding: utf-8; -*-
Version = '$Id: brainf_ck.y 3300 2009-03-07 05:29:42Z hs9587 $'
# $Date: 2009-03-07 14:29:42 +0900 (土, 07 3 2009) $

---- footer
require 'singleton'

class Tape
  include Singleton

  def initialize
    @tape = []
    @pointer = 0
  end # def initialize

  def value
    @tape[@pointer] ||= 0
  end # def value

  def right
    @pointer += 1
  end # def right

  def left
    @pointer -= 1
  end # def left

  def plus
    @tape[@pointer] = value + 1
  end # def plus

  def minus
    @tape[@pointer] = value - 1
  end # def minus

  def put
    $stdout.print value.chr
  end # def put

  def get
    c = $stdin.getc
    @tape[@pointer] = c.respond_to?(:ord) ? c.ord : c
  end # def get
end # class Tape

class Node
  def initialize(*args)
  end # def initialize(*args)

  def evaluate(opts, *args)
    $stderr.puts Tape.instance.inspect if opts.yydebug
  end # def evaluate(opts, *args)
end # class Node

class NullNode < Node; end

class RootNode < Node
  def initialize(expression)
    super
    @expression = expression
  end # def initialize

  def evaluate(opts, *args)
    super
    @expression.evaluate(opts, *args).flatten
  end # def evaluate(opts, *args)
end # class RootNode < Node

class ExpressionNode < Node
  def initialize(expression, other_expression)
    super
    @expression = expression
    @other_expression = other_expression
  end # def initialize(expression, otherexpression)

  def evaluate(opts, *args)
    super
    [@expression.evaluate(opts, *args), @other_expression.evaluate(opts, *args)]
  end # def evaluate(opts, *args)
end # class ExpressionNode < Node

class TerminalNode < Node
  def initialize(term)
    super
    @term = term
  end # def initialize(term)

  def evaluate(opts, *args)
    super
    Tape.instance.send @term
  end # def evaluate(opts, *args)
end # class TerminalNode < Node

class BracketNode < Node
  def initialize(expression)
    super
    @expression = expression
  end # def initialize(expression, other_expression)

  def evaluate(opts, *args)
    super
    while Tape.instance.value != 0 do
      @expression.evaluate(opts, *args)
    end # while Tape.instance.value != 0 do
  end # def evaluate(opts, *args)
end # class BracketNode < Node

require 'optparse'
require 'ostruct'
opts = OpenStruct.new
opts.yydebug = false

ARGV.options do |opt|
  opt.on('--[no-]yydebug', 'debug mode (from racc -t) on/off'){ |v| 
opts.yydebug = v }
  opt.release = 'Node tree'
  opt.banner += "\n\tBrainf*ck interpreter.\nOptions:"
  opt.parse!
end # ARGV.options do |opt|

BrainF_ckParser.new((ARGV.size > 0 ? ARGF : $stdin).read).parse(opts) \
  .tap{ |tree| tree.inspect.display $stderr if opts.yydebug }.evaluate(opts)

Nodeクラスの定義群が入ってきて、そろそろファイルの分割を考えたくなってきた。そしてこれだけクラス定義をするとなると、テストやスペックを書きたくもなって来る。
それから、Singleton を使って Tape を抽象化してみた。

さらに命名について。Node類が出てきたので、パーサにも Parser と接尾辞をつけよう。各 Node(継承)クラス名は各記号の名前文字列に対応したものにしているが、RootNode だけは ProgramNode では気分がでないのでそうした。また、NullNode は作らないで単に何もしないでよかったかも知れないが、一応作ってみた。