構文解析(1)

最近，構文解析が流行っているらしい．rakeっぽく作ればいけるかも？と適当に作ってみた．

まったく理解していないけど一応動くものは出来たっぽい？中国語の部屋状態．

四則演算はるびまのsyntax.rbそっくりになってしまった．そして判りにくい．こんなんならraccのままでいいや．

お約束の四則演算

include Parse

#rep(:int_p => ['0','1','2','3','4','5','6','7','8','9']) {|v| v.join().to_i }
#rep(:int_p => ['0'..'9']) {|v| v.join().to_i }
sel(:int_p => /\A\d+/) {|v| v.to_i }

seq(:group => ['(', :expression, ')']) {|v| v[1]}

sel :factor => [:int_p, :group]

seq(:term => [:factor, rep0(
  seq('*', :factor),
  seq('/', :factor)
 )]) {|v|
  c = v[0]
  v[1].each {|x|
    case x[0]
    when '*'; c *= x[1]
    when '/'; c /= x[1]
    end
  }
  c
}

seq(:expression => [:term, rep0(
  seq('+', :term),
  seq('-', :term)
 )]) {|v|
  c = v[0]
  v[1].each {|x|
    case x[0]
    when '+'; c += x[1]
    when '-'; c -= x[1]
    end
  }
  c
}

seq :target => :expression

csvファイル

include Parse

# 新しいルールを作る。同じ規則を作っても内部的には別の規則にされる
def other(*args,&block)
  all( neg( *args), /\A./, &block)
end

def get2nd(a,b)
  seq(a, b){|v|v[1]}
end

sel :space_p => [' ', "\t"]
rep0 :space_opt => :space_p


rep(:csv => 
  seq([:value, rep0(get2nd(',', :value)), "\n"]) {|v| [v[0],*v[1]] }
)
sel :value => [
    seq( :space_opt, '"', :quoted_value, '"', :space_opt) {|v| v[2]},
    :naked_value
  ]
rep0(:quoted_value => [ seq('""'){'"'}, other('"') ]) {|v| v.join }
rep0(:naked_value => other(',','"',"\n")) {|v| v.join }

かなりいい加減な本体．

module Parse

  #-------------------------------------------------------------------
  # private:

  class Rule
    def initialize(type,args,params,&block)
      @type,@args,@params,@act = type, args, params, block
    end
    # 実際には読むだけだと思うが…
    attr_accessor :type
    attr_accessor :args
    attr_accessor :params
    attr_accessor :act
  end

  @@gen = 0
  @@rules = {}

  # 無名の規則用の名前を提供する
  # to generate a name for anonymous rules(なぜ英語?)
  def gen
    @@gen += 1
    :"_rule#{@@gen}"
  end

  def _to_array( args)
    (args.kind_of?(Array))? args: [args]
  end

  def _to_unarray( args)
    # seq(a,b,c,d)とseq([a,b,c,d])を等価に扱うための処理
    (args.kind_of?(Array) and args.size==1)? args[0]: args
  end

  def _to_hash( args)
    (args.kind_of?(Hash))? args: Hash[gen(),args]
  end

  def _rule( type, args, params, &block)
    k = nil
    _to_hash( _to_unarray(args)).each {|k,v|
      @@rules[k] ||= []
      @@rules[k] << Rule.new(type, _to_array(v), params, &block)
    }
    k # 複数のハッシュを一度に登録すると返るキーが不定になる…
  end

  # sequence
  def _check_seq(r, pos, lv, params, str)
    m_type, m_len, work = nil, 0, []
    r.each{|y|
      m, l, w = _parse( y, pos+m_len, lv+1, str)
      unless m
        m_type, m_len, work = nil, 0, []
        break
      end
      m_len += l
      m_type = :SEQ
      work << w
    }
    return m_type, m_len, work
  end

  # 先読み
  # look ahead
  def _check_lah(r, pos, lv, params, str)
    # 読み込んでも前に進まない．
    m_type, m_len, work = _check_sel(r, pos, lv, params, str)
    m_len = 0
    return m_type, m_len, work
  end

  # repeat
  def _check_rep(r, pos, lv, params, str)

    # c_min回以上、c_max回までの繰り返し
    # c_maxが-1なら無限に繰り返す

    c_min, c_max = params[0], params[1]
    c = 0
    m_len = 0
    work = []

    while true
      m, l, w = _parse( r, pos+m_len, lv+1, str)
      break unless m
      m_len += l
      work << w
      c += 1
      break if c==c_max
    end
    return :REP, m_len, work if c_min<=c
    return nil, 0, []
  end

  # alteration
  def _check_sel( r, pos, lv, params, str)

    # 一番長くマッチしたものを返す。
    # 同じ長さがある場合は最初に見つかったもの。
    # /\Aabc\b/のように区切り文字込みで検索するなら，
    # 最初に見つかったものを返せばいいが、
    # "abc"で検索する場合、"abcd"に対して、"ab"も"abc"もヒットしてしまう

    m_type, m_len, work = nil, -1, []
    r.each{|x|
      m, l, w = _parse( x, pos, lv, str)
      m_type,m_len,work = m,l,w if m and m_len<l
    }
    return m_type, m_len, work
  end

  def _check_neg( r, pos, lv, params, str)
    m_type, m_len, work = _check_sel( r, pos, lv, params, str)
    return :NEG, 0, [] unless m_type
    # 1つでも一致したらfalse
    return nil, 0, []
  end

  def _check_and( r, pos, lv, params, str)
    m_type, m_len, work = nil, -1, []
    r.each{|x|
      m, l, w = _parse( x, pos, lv, str)
      unless m
        m_type = nil
        break
      end
      m_type,m_len,work = m,l,w if m and m_len<l
        # 長い方を優先
    }
    return m_type, m_len, work
  end

  def _parse( r, pos, lv, str)
    # いまはループする文法を余裕で書ける
    # return nil, 0, [] if lv>32
      # 四則演算程度でもすぐにスタックが深くなる…
 
    m_type, m_len, work = nil, 0, []
    act = nil

    case r
    when Rule
      m_type, m_len, work = send( r.type, r.args, pos, lv, r.params, str)
      act = r.act
    when Array
      m_type, m_len, work = _check_sel( r, pos, lv, [], str)
    when Symbol
      m_type, m_len, work = _parse( @@rules[r], pos, lv+1, str)

    when String
      m_type, m_len, work = :STRING, r.size, r if r==str[pos,r.size]
    when Regexp
      m_type, m_len, work = :STRING, $~[0].size, $~[0] if r =~ str[pos..-1]
    when Range
      x = r.find {|x| x==str[pos,x.size] }
      m_type, m_len, work = :STRING, x.size, x if x
    else
      # error
    end

    if m_type
      if act
        # 念のためにdupったのを送る
        tmp = act.call(work.dup) # (work,pos,m_len) を送る?
        work = tmp if tmp
          # nilを返しても無視される．
          # 無効にしたい場合は[]を返すか，:EMPTYのようなダミーを返す．
      end
      pos += m_len
    end

    return m_type, m_len, work
  end

  def _print_rule(k,v)
    v.each {|x|
      case x
      when Rule
        r = x
        if r.params.empty?
          p [k, r.type, r.args]
        else
          p [k, r.type, r.args, r.params]
        end
      else
        p [k, :_leaf, x]
      end
    }
  end

  #-------------------------------------------------------------------
  # public:

  def sel(*args, &block) _rule( :_check_sel, args, [], &block); end
  def seq(*args, &block) _rule( :_check_seq, args, [], &block); end
  def rep(*args, &block) _rule( :_check_rep, args, [1,-1], &block); end
  def rep0(*args, &block) _rule( :_check_rep, args, [0,-1], &block); end
  def opt(*args, &block) _rule( :_check_rep, args, [0,1], &block); end
  def pre(*args, &block) _rule( :_check_lah, args, [], &block); end

  def all(*args, &block) _rule( :_check_and, args, [], &block); end
  def neg(*args, &block) _rule( :_check_neg, args, [], &block); end
    # and, notが使えなかったのでall,negにした
    # all: 全部trueなら有効．1つでもfalseがあれば無効
    # neg: 全部falseなら有効．1つでもtrueがあれば無効

  def parse(str, target=:target)
    m_type, m_len, result = _parse( target, 0, 0, str)
    result = nil unless m_len == str.size
      # 文末まで到達していないのでエラー扱いにする
    result
  end

  def print_rules
    @@rules.each {|k,v| _print_rule(k,v) }
  end
end