NFAで文字列比較する関数を書きました

『精霊の箱上: チューリングマシンをめぐる冒険』が元ネタです。parser書いて、次みたいな感じで動くようにしたいですが、まだできてません。

src = <<-END
100->1
111->1
1 0<-3
200->2
211->1
2 1<-3
END

m = Machine.compile(src)
puts m.exec("100101011 ", 3)

本の中の設計図を正規表現に変形して、カッコの扱いが面倒なのでポストフィックス記法にしたコードを手で作ります(ポストフィックス記法への変換はツール使ってます)。そのソースをコンパイルして実行ということをしています。下のコードのa, b, c…は本を読めば分かると思います。これだけ書いて、なんとできることは文字列の比較だけなんです。文字列が等しければXXXX,XXXXのような出力になります。違えばnilが返ってきます。

#!/usr/bin/env ruby
require './nfa.rb'
require 'minitest/autorun'

class MainTest < MiniTest::Test
  def test_cmp_str
   a = "XX->"
   b = "0X->"
   c = "1X->"
   d = "00->"
   e = "11->"
   f = ",,->"
   g = "0X<-"
   h = "00<-"
   i = "11<-"
   j = ",,<-"
   k = "XX<-"
   l = "  ->"
   m = "1X->"
   n = "  <-"
   o = "1X<-"
   s = compile("#{a}#{l}|#{b}#{d}#{e}|*.#{f}.#{a}*.#{g}.#{c}#{d}#{e}|*.#{f}.#{a}*.#{o}.|#{h}#{i}#{j}#{k}|||*.#{l}.|*#{f}.#{a}*.#{n}.")
   m = Machine.new(s)
   assert !m.exec(" 0,1 ")
   assert !m.exec(" 1,0 ")
   assert_equal " X,X ", m.exec(" 1,1 ")
   assert_equal " XXXXXXXXXX,XXXXXXXXXX ", m.exec(" 1010001111,1010001111 ")
  end
end

#./nfa.rb
class Machine
  def initialize(state)
    @init  = state
  end
  def step(str)
    state_lists = []
    is = []
    strs = []
    @state_lists.each.with_index do|states, j|
      pos = @is[j]
      str = @strs[j]
      states.each do|s|
        if s.b == str[pos]
          new_str = str.dup
          s.exec(pos, new_str)
          strs << new_str
          is << pos + s.steps
          state_lists << next_states(s.out1)
        end
      end
    end
    @is = is
    @strs = strs
    state_lists
  end
  def isMatch
    v = nil
    i = 0
    @state_lists.each do |states|
      if (states.find{|s| s.type == :end})
         v = i
         break
      end
      i += 1
    end
    v
  end
  def exec(str)
    @state_lists = [next_states(@init)]
    @strs = [str]
    @is = [0]
    l = str.length
    while !isMatch && @state_lists.size > 0 do
      @state_lists = step(str)
    end
    (i = isMatch) ? @strs[i] : nil
  end
  def next_states(state)
    nstates = []
    return [] if !state
    case state.type
    when :split
       nstates << next_states(state.out1)
       nstates << next_states(state.out2)
    else
       nstates << state
    end
    nstates.flatten.compact
  end
end

class Frag
  attr_accessor :start, :out
  def initialize(start, out)
    @start = start
    @out = out
  end
  def patch(other)
    @out.each do |state|
      state.out1 = other
    end
  end
end

class StateList
   include Enumerable
   attr_accessor :head, :next
   def initialize(head)
     @head = head
   end
   def append(l)
    e = self
    while e.next do
      e = e.next
    end
    e.next = l
    self
   end
   def each
     e = self
     while e && e.head do
       yield e.head
       e = e.next
     end
   end
end

class State
  attr_reader :b, :steps, :type, :a
  attr_accessor :out1, :out2
  def initialize(type, b, a, steps)
    @type = type
    @b = b
    @a = a
    @steps = steps
  end
  def inspect
    "S(#{@type}, #{@b.inspect}, #{@a.inspect})"
  end
  def to_s
    "S(#{@type},#{@b},#{@a}, #{@steps})"
  end
  def exec(i, str)
    str[i] = @a
    #puts "(#{self.to_s}).exec(#{i}, #{str})"
  end
end

def compile(source)
  stack = []
  l = source.length
  i = 0
  while i < l do
    c = source[i]
    case c
    when '*'
      e = stack.pop
      s = State.new(:split, nil, nil, nil)
      s.out2 = e.start
      e.patch(s)
      stack.push(Frag.new(s, StateList.new(s)))
      i+=1
    when '.'
      e2 = stack.pop
      e1 = stack.pop
      e1.patch(e2.start)
      stack.push(Frag.new(e1.start, e2.out))
      i+=1
    when '|'
      e2 = stack.pop
      e1 = stack.pop
      s = State.new(:split, nil, nil, nil)
      s.out2 = e1.start
      s.out1 = e2.start
      stack.push(Frag.new(s, e1.out.append(e2.out)))
      i+=1
    else
      s = State.new(:value, source[i, 1], source[i + 1, 1], ('->' == source[i + 2, 2])? 1 : -1)
      i+= 4
      stack.push(Frag.new(s, StateList.new(s)))
    end
  end
  e = stack.pop
  e.patch(State.new(:end, nil, nil, nil))
  e.start
end