Rubyによる正規表現コンパイラ(その1)

llvmrubyのサンプルで何か作りたいなと思い、正規表現コンパイラを作ろうと思い立ちました。
調べてみたらomoさんがllvmで正規表現コンパイラを作っていましたhttp://www.dodgson.org/omo/t/?date=20071215。これをllvmrubyに移植しようと思ったのですが、コードを読んでも全然わからない。
昔のオートマトンの講義(確か単位落としたような気がする)を思い出して自分で作ってみました。何か、就職できなくて自分で会社を作ったのび太のような気分です。

正規表現は必要最低限のものだけです

 *           0回以上の繰り返し
 .           任意の文字
 \文字       エスケープ(文字列で表すので実際には\\と入力する必要があります。)

llvmにコンパイルする版を作る前に、Rubyにgotoを入れたRuby66にコンパイルするようにしてみました。

例えば、

".*cc\\*dd*a"

は次のようにコンパイルされます。

i = -1
0:
i = i + 1
if i > maxlen then return false
if ch[i] == 'c' then goto 1
goto 0
1:
i = i + 1
if i > maxlen then return false
if ch[i] == 'c' then goto 2
goto 0
2:
i = i + 1
if i > maxlen then return false
if ch[i] == '*' then goto 3
goto 0
3:
i = i + 1
if i > maxlen then return false
if ch[i] == 'd' then goto 4
goto 0
4:
i = i + 1
if i > maxlen then return false
if ch[i] == 'a' then goto 5
if ch[i] == 'd' then goto 4
goto 0
5:
return true

ソースコードです。次はllvmに落とす版を作ります。

追記
バグがありました。/.*ruby/というパターンで"rruby"が失敗してました。今あるのは修正版です。

続く

#!/bin/env ruby
# -*- coding: utf-8 -*-
# Reguler Expression Compiler

class StateMan
  def initialize
    @nstate = 0
    @state = []
    @state[0] = {}
    @loopf = false
  end

  attr :state

  def add_edge(ch, fm, to, loopf)
    if @state[fm][ch] then
      if @loopf then
        @state[fm][ch] = @nstate
        @state[@nstate] = @state[fm].dup
      else
        @state[@nstate] = @state[fm].dup
        @state[fm][ch] = @nstate
      end

      @loopf = loopf
    else
      @state[fm][ch] = fm
      @loopf = loopf
    end
  end

  def new_state
    @nstate += 1
    @state[@nstate] = {}
    @nstate
  end

  def get_next_state(cstate, ch)
    ret = @state[cstate][ch]
    if ret == @nstate then
      ret = true
    end

    ret
  end

  def inspect
    res = ""
    @state.each_with_index do |ele, i|
      res += "\nState #{i}\n"
      defval = ele[256]
      ele.each do |key, val|
        if val != defval then
          res += "'#{key.chr}' => #{val}\n"
        end
      end
      res += "... => #{defval}\n"
    end

    res
  end
end

def chr_range(ch)
  case ch
  when '.'
    0..256

  else
    [ch.ord]
  end
end

def reexp_comp(restr)
  stm = StateMan.new
  cst = 0
  nst = 0

  inx = 0
  ed = restr.size
  while inx < ed do
    inx += 1
    if restr[inx - 1] == '\\' then
      nst = stm.new_state
      stm.add_edge(restr[inx].ord, cst, nst, false)
      cst = nst
      inx += 1
      next
    end

    case restr[inx]
    when '*'
      chr_range(restr[inx - 1]).each do |i|
        stm.add_edge(i, cst, cst, true)
      end
      inx += 1
      next
      
    else
      nst = stm.new_state
      chr_range(restr[inx - 1]).each do |i|
        stm.add_edge(i, cst, nst, false)
      end
      cst = nst
      next
    end
  end

  stm
end

def match(stm, str)
  state = 0
  str.each_byte do |ch|
    state = stm.get_next_state(state, ch)
    if state == nil then
      return false
    end

    if state == true then
      return true
    end
  end
  false
end


def matcher_compile_ruby66(stm)
  res = "i = -1\n"
  starray = stm.state
  starray.each_with_index do |elest, stn|
    res += "#{stn}:\n"

    if stn == starray.size - 1 then
      res += "return true"
    else
      res += "i = i + 1\n"
      res += "if i > maxlen then return false\n"
      defstat = elest[256]
      elest.each do |key, val|
        if val != defstat then
          res += "if ch[i] == '#{key.chr}' then goto #{val}\n"
        end
      end
      if defstat then
        res += "goto #{defstat}\n"
      else
        res += "return false\n"
      end
    end
  end

  res
end

stm = reexp_comp(".*cc\\*dd*a")
p ".*cc\\*dd*a"
#p stm
#p match(stm, "fffcccddddafff")
#p match(stm, "nnncccaaaa")
#p match(stm, "kkkdcc*dddannnn")
print matcher_compile_ruby66(stm)