Gcodeへのコンパイルと(正格な)評価器
Compiling to Gcode - 趣味的にっきの続きです。
G-machine COSC406 Compiler Implementation Techniques p.18までソースからGcodeへのコンパイルと(正格な)評価器を実装してみました。
require 'pp' class ApNode def initialize(left, right) @left, @right = left, right end attr_reader :left, :right def inspect @left.inspect + '@' + @right.inspect end end class OpCode def initialize(arg = nil) @arg = arg end def inspect self.class.to_s.sub(/OpCode/, '') + (@arg ? ' ' + @arg.inspect : '') end end class OpCodePush < OpCode def evaluate(stack) stack.push(stack[-2 - @arg].right) end end class OpCodePushInt < OpCode def evaluate(stack) stack.push(@arg) end end class OpCodePushGlobal < OpCodePushInt end class OpCodeMkap < OpCode def evaluate(stack) f = stack.pop g = stack.pop stack.push(ApNode.new(f, g)) end end class OpCodeSlide < OpCode def evaluate(stack) @arg.times { stack.shift } end end class OpCodeUnwind < OpCode def evaluate(stack) while stack.last.is_a?(ApNode) stack.push(stack.last.left) end end end def comp_sc(f, xs, e) # p [:comp_sc, f, xs, e] xs1 = xs.inject([{}, 0]) {|(h, i), x| h[x] = i; [h, i + 1] }.first comp_r(e, xs1, xs.size) end def comp_r(e, q, d) # p [:comp_r, e, q, d] comp_c(e, q) + [OpCodeSlide.new(d + 1), OpCodeUnwind.new()] end def comp_c(e, q) # p [:comp_c, e, q] case e when Symbol if e.to_s =~ /\A[A-Z]/ [OpCodePushGlobal.new(e)] else [OpCodePush.new(q[e])] end when Integer [OpCodePushInt.new(e)] when Array case e.size when 0 [] when 1 comp_c(e.first, q) else e0, e1 = e[0 .. -2], e[-1] q1 = q.inject({}) {|h, (k, v)| h[k] = v + 1; h } comp_c(e1, q) + comp_c(e0, q1) + [OpCodeMkap.new] end else raise 'invalid e.' end end def evaluate(codes, stack) while stack.last.is_a?(Symbol) # pp stack.last codes[stack.last].each do |op| pp [op, stack] op.evaluate(stack) end end stack end if $0 == __FILE__ src = [ [:S, [:f, :g, :x], [:f, :x, [:g, :x]]], [:K, [:x, :y ], [:x ]], [:I, [:x ], [:x ]], [:MAIN, [ ], [:S, :K, :I, 3 ]] ] codes = src.inject({}) do |cs, (f, xs, e)| cs[f] = comp_sc(f, xs, e) cs end # pp codes pp evaluate(codes, [:MAIN]) # => [3] end