天泣記

2011-02-02 (Wed)

#1

ついでに、subexp call も実装してみよう。

subexp call には、subexp を定義する要素と、呼び出す要素が必要である。それぞれ、[:subexp, name, r1, r2, ...] と [:call, name] と表現しよう。

定義するほうに、複数の正規表現を指定できるのはいちいち [:cat, r1, r2, ...] と書いて連結するのが面倒だからである。複数書いたら、連結したものを意味することにしよう。

同様に、繰り返しとキャプチャも [:rep, r1, r2, ...], [:cap, name, r1, r2, ...] と複数指定できるようにして、やはりこれも連結したものを意味することにしよう。

そうやって実装したのが以下である。

call を実現するには名前から正規表現を lookup する必要があるので、そのための辞書を事前に作る必要がある。また、ここではやっていないけれど、左再帰の検出も必要だし、Balancing Group Definition よりも手間がかかるといわれれば否定はできない。

def match(re, str, b=0)
  ary = str.split(//)
  try(re, ary, b, Hash.new([].freeze), collect_subexps(re)) {|e, cap|
    return [b...e, cap]
  }
  nil
end

def collect_subexps(re, subexps={})
  case re[0]
  when :lit
  when :cat; _, *rs = re; rs.each {|r| collect_subexps(r, subexps) }
  when :alt; _, *rs = re; rs.each {|r| collect_subexps(r, subexps) }
  when :rep; _, *rs = re; rs.each {|r| collect_subexps(r, subexps) }
  when :cap; _, n, *rs = re; rs.each {|r| collect_subexps(r, subexps) }
  when :subexp; _, n, *rs = re; rs.each {|r| collect_subexps(r, subexps) }
    subexps[n] = re
  when :call
  else raise "unexpected: #{re.inspect}"
  end
  subexps
end

def try(re, ary, pos, cap, subexps, &b)
  case re[0]
  when :lit; _, ch = re; try_lit(ch, ary, pos, cap, subexps, &b)
  when :cat; _, *rs = re; try_cat(rs, ary, pos, cap, subexps, &b)
  when :alt; _, *rs = re; try_alt(rs, ary, pos, cap, subexps, &b)
  when :rep; _, *rs = re; try_rep(rs, ary, pos, cap, subexps, &b)
  when :cap; _, n, *rs = re; try_cap(n, rs, ary, pos, cap, subexps, &b)
  when :subexp; _, n, *rs = re; try_subexp(n, rs, ary, pos, cap, subexps, &b)
  when :call; _, n = re; try_call(n, ary, pos, cap, subexps, &b)
  else raise "unexpected: #{re.inspect}"
  end
end

def try_lit(ch, ary, pos, cap, subexps)
  if pos < ary.length && ary[pos] == ch
    yield pos + 1, cap
  end
end

# r1 r2 ...
def try_cat(rs, ary, pos, cap, subexps, &block)
  if rs.empty?
    yield pos, cap
  else
    r, *rest = rs
    try(r, ary, pos, cap, subexps) {|pos2, cap2|
      try_cat(rest, ary, pos2, cap2, subexps, &block)
    }
  end
end

# r1 | r2 | ...
def try_alt(rs, ary, pos, cap, subexps, &block)
  rs.each {|r|
    try(r, ary, pos, cap, subexps, &block)
  }
end

# (r1 r2 ...)*
def try_rep(rs, ary, pos, cap, subexps, &block)
  try_cat(rs, ary, pos, cap, subexps) {|pos2, cap2|
    if pos < pos2
      try_rep(rs, ary, pos2, cap2, subexps, &block)
    end
  }
  yield pos, cap
end

# (?<n>r1 r2 ...)
def try_cap(n, rs, ary, pos, cap, subexps, &block)
  try_cat(rs, ary, pos, cap, subexps) {|pos2, cap2|
    cap3 = cap2.dup
    cap3[n] = cap3[n] + [pos...pos2]
    yield pos2, cap3
  }
end

# (?<n>r1 r2 ...) without capture
def try_subexp(n, rs, ary, pos, cap, subexps, &block)
  try_cat(rs, ary, pos, cap, subexps, &block)
end

# \g<n>
def try_call(n, ary, pos, cap, subexps, &block)
  r = subexps.fetch(n)
  try(r, ary, pos, cap, subexps, &block)
end

# balanced parentheses
re = [:subexp, :S, [:rep, [:lit, "("], [:call, :S], [:lit, ")"]]]

p match(re, "((()((())())(())))))")
#=> [0...18, {}]

2011-02-03 (Thu)

#1

さて、subexp call や Balancing Group Definition で括弧の対にマッチできるからといって、その木構造を取り出せないのではおもしろくない。

取り出せるようにしてみよう。

subexp call は、いってしまえば recursive decent parser なので、呼び出し関係にそった木を作ればいい。

[:tree, tag, r1, r2, ...] と [:leaf, r1, r2, ...] でやってみよう。前者で [tag, ...] というノードを作り、後者でマッチした場所をキャプチャした文字列を葉とする。

実装としてはスタックが必要だが、(.NET 式の配列な) キャプチャを使えばいいだろう。ひとつあればいいので、:T という名前のキャプチャを使うことにしよう。(いちおう、:tree と :leaf 以外で変にいじられないことは仮定しておこう)

require 'pp'

def match(re, str, b=0)
  ary = str.split(//)
  try(re, ary, b, Hash.new([].freeze), collect_subexps(re)) {|e, cap|
    return [get_substr(ary, b...e), cap]
  }
  nil
end

def collect_subexps(re, subexps={})
  case re[0]
  when :fail
  when :lit
  when :cat; _, *rs = re; rs.each {|r| collect_subexps(r, subexps) }
  when :alt; _, *rs = re; rs.each {|r| collect_subexps(r, subexps) }
  when :rep; _, *rs = re; rs.each {|r| collect_subexps(r, subexps) }
  when :repn; _, min, max, *rs = re; rs.each {|r| collect_subexps(r, subexps) }
  when :cap; _, n, *rs = re; rs.each {|r| collect_subexps(r, subexps) }
  when :subexp; _, n, *rs = re; rs.each {|r| collect_subexps(r, subexps) }
    subexps[n] = re
  when :call
  when :leaf; _, *rs = re; rs.each {|r| collect_subexps(r, subexps) }
  when :tree; _, tag, *rs = re; rs.each {|r| collect_subexps(r, subexps) }
  else raise "unexpected: #{re.inspect}"
  end
  subexps
end

def try(re, ary, pos, cap, subexps, &b)
  case re[0]
  when :fail
  when :lit; _, ch = re; try_lit(ch, ary, pos, cap, subexps, &b)
  when :cat; _, *rs = re; try_cat(rs, ary, pos, cap, subexps, &b)
  when :alt; _, *rs = re; try_alt(rs, ary, pos, cap, subexps, &b)
  when :rep; _, *rs = re; try_repn(0, nil, rs, ary, pos, cap, subexps, &b)
  when :repn; _, min, max, *rs = re; try_repn(min, max, rs, ary, pos, cap, subexps, &b)
  when :cap; _, n, *rs = re; try_cap(n, rs, ary, pos, cap, subexps, &b)
  when :subexp; _, n, *rs = re; try_subexp(n, rs, ary, pos, cap, subexps, &b)
  when :call; _, n = re; try_call(n, ary, pos, cap, subexps, &b)
  when :leaf; _, *rs = re; try_leaf(rs, ary, pos, cap, subexps, &b)
  when :tree; _, tag, *rs = re; try_tree(tag, rs, ary, pos, cap, subexps, &b)
  else raise "unexpected: #{re.inspect}"
  end
end

def try_lit(ch, ary, pos, cap, subexps)
  if pos < ary.length && ary[pos] == ch
    yield pos + 1, cap
  end
end

# r1 r2 ...
def try_cat(rs, ary, pos, cap, subexps, &block)
  if rs.empty?
    yield pos, cap
  else
    r, *rest = rs
    try(r, ary, pos, cap, subexps) {|pos2, cap2|
      try_cat(rest, ary, pos2, cap2, subexps, &block)
    }
  end
end

# r1 | r2 | ...
def try_alt(rs, ary, pos, cap, subexps, &block)
  rs.each {|r|
    try(r, ary, pos, cap, subexps, &block)
  }
end

# (r1 r2 ...)*          # min=0, max=nil
# (r1 r2 ...)+          # min=1, max=nil
# (r1 r2 ...){min,max}
def try_repn(min, max, rs, ary, pos, cap, subexps, &block)
  if max.nil? || 0 < max
    try_cat(rs, ary, pos, cap, subexps) {|pos2, cap2|
      if pos < pos2
        min2 = min == 0 ? 0 : (min-1)
        max2 = max ? (max-1) : nil
        try_repn(min2, max2, rs, ary, pos2, cap2, subexps, &block)
      end
    }
  end
  if min == 0
    yield pos, cap
  end
end

# (?<n>r1 r2 ...)
def try_cap(n, rs, ary, pos, cap, subexps, &block)
  try_cat(rs, ary, pos, cap, subexps) {|pos2, cap2|
    cap3 = cap2.dup
    cap3[n] = cap3[n] + [get_substr(ary, pos...pos2)]
    yield pos2, cap3
  }
end

# (?<n>r1 r2 ...) without capture
def try_subexp(n, rs, ary, pos, cap, subexps, &block)
  try_cat(rs, ary, pos, cap, subexps, &block)
end

# \g<n>
def try_call(n, ary, pos, cap, subexps, &block)
  r = subexps.fetch(n)
  try(r, ary, pos, cap, subexps, &block)
end

def try_leaf(rs, ary, pos, cap, subexps, &block)
  try_cap(:T, rs, ary, pos, cap, subexps, &block)
end

def try_tree(tag, rs, ary, pos, cap, subexps, &block)
  len = cap[:T].length
  try_cat(rs, ary, pos, cap, subexps) {|pos2, cap2|
    cap3 = cap2.dup
    cap3[:T] = cap3[:T][0,len] + [[tag, *cap3[:T][len..-1]]]
    yield pos2, cap3
  }
end

def get_substr(ary, range)
  s = ary[range].join('')
  s.instance_variable_set(:@pos, range)
  s
end

re = [:subexp, :S, [:rep, [:tree, :S, [:lit, "("], [:call, :S], [:lit, ")"]]]]
p match(re, "((())()))))")
#=> ["((())())", {:T=>[[:S, [:S, [:S]], [:S]]]}]

とりあえず対になった括弧をやってみると、((())()) が [:S, [:S, [:S]], [:S]] となり、ちゃんと parse できているようだ。

もうちょっと複雑なものとして、(基本的な) 正規表現を parse してみよう。

re = [:alt, [:cat, [:fail],
                   [:subexp, :R, [:alt, [:tree, :ALT, [:call, :T], [:repn, 1, nil, [:lit, "|"], [:call, :T]]],
                                        [:call, :T]]],
                   [:subexp, :T, [:alt, [:tree, :CAT, [:repn, 2, nil, [:call, :C]]],
                                        [:call, :C]]],
                   [:subexp, :C, [:alt, [:tree, :REP, [:cat, [:call, :V], [:lit, "*"]]],
                                        [:call, :V]]],
                   [:subexp, :V, [:alt, [:tree, :LIT, [:leaf, [:alt, [:lit, "a"],
                                                                     [:lit, "b"]]]],
                                        [:cat, [:lit, "("], [:call, :R], [:lit, ")"]]]]],
            [:call, :R]]
pp match(re, "a(bb(ab)*aa|a)*")
#=>
#["a(bb(ab)*aa|a)*",
# {:T=>
#   [[:CAT,
#     [:LIT, "a"],
#     [:REP,
#      [:ALT,
#       [:CAT,
#        [:LIT, "b"],
#        [:LIT, "b"],
#        [:REP, [:CAT, [:LIT, "a"], [:LIT, "b"]]],
#        [:LIT, "a"],
#        [:LIT, "a"]],
#       [:LIT, "a"]]]]]}]

ちゃんと parse できている。(混乱を防ぐため、parse 結果の木では tag を大文字にしてあるが、小文字にしてもよい)

recursive decent parser なので、あたりまえにできることができているだけのことではあるが。

#2

では、Balancing Group Definition で木を取り出せるか。

なかなか難しい?

とりあえずスタックを複数使えるため、自明な木構造が定義できないのは厄介だ。

ひとつ指定して使うと限定すれば?

2011-02-06 (Sun)

#1

[ruby-dev:43149] ささだ研の Ruby に関する研究の話をする会 にいった。

yugui さんに会ったので、Ruby 1.9.1 について尋ねて、boron でやっている chkbuild の 1.9.1 はもう止めていいということになった。

2011-02-20 (Sun)

#1

SQL の natural left outer join は associative か?

つまり、(t1 natural left outer join t2) natural left outer join t3 と t1 natural left outer join (t2 natural left outer join t3) と同じか?

なんか違う感じがする、というわけでしばらく考えて具体的な例を作ってみた。

% sqlite3 
SQLite version 3.5.9
Enter ".help" for instructions
sqlite> .mode column
sqlite> .header on
sqlite> create temp table t1 (id1, ab, ca);
sqlite> create temp table t2 (id2, ab, bc);
sqlite> create temp table t3 (id3, bc, ca);
sqlite> insert into t1 values("t1", 1, 1);
sqlite> insert into t2 values("t2", 1, 1);
sqlite> insert into t3 values("t3", 1, 2);
sqlite> select * from t1;
id1         ab          ca        
----------  ----------  ----------
t1          1           1         
sqlite> select * from t2;
id2         ab          bc        
----------  ----------  ----------
t2          1           1         
sqlite> select * from t3;
id3         bc          ca        
----------  ----------  ----------
t3          1           2         
sqlite> select * from (t1 natural left outer join t2) natural left outer join t3;
id1         ab          ca          id2         bc          id3       
----------  ----------  ----------  ----------  ----------  ----------
t1          1           1           t2          1                     
sqlite> select * from t1 natural left outer join (t2 natural left outer join t3);
id1         ab          ca          id2         bc          id3       
----------  ----------  ----------  ----------  ----------  ----------
t1          1           1                                             

つまり、かっこのつけかたによって、t2 の情報が残るか残らないかが変化する

ところで、かっこをつけないと、上の二つのどちらとも異なり、

sqlite> select * from t1 natural left outer join t2 natural left outer join t3;
id1         ab          ca          id2         bc          id3         ca        
----------  ----------  ----------  ----------  ----------  ----------  ----------
t1          1           1           t2          1           t3          2         

というように、ca がふたつでてくるのは変な気がする。

[latest]