Racc で Brainf*ck 、構文木
取り敢えずルールはこんな感じかな。
program : expression expression : | expression bracket | expression TERM bracket : '[' expression ']'
終端記号は、「TERM」テープの扱いや入出力と括弧 '['、']'。一方「program」はまあ、最終的な左辺値として全体を代表する。それと同じものなのに更に「expression」を作ってるのは、「'['」「']'」で挟まれるものに「program」は無いだろうという思いもある。その「expression」は空を含む「bracket」と「TERM」の列。「bracket」はその「expression」を囲むもの。
その「bracket」のだけど
- 「[」ポインタ位置の数値が 0 以外なら何もしない、0 なら対応する「]」まで行き、その「]」の次からまた始める
- 「]」ポインタ位置の数値が 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 は作らないで単に何もしないでよかったかも知れないが、一応作ってみた。