transitive.info

treetop を使う

構文解析に慣れていないのと、 サンプルがあまり見当たらないのでけっこうはまった。

文字列を空白で分割する

treetop で、まずは文字列を空白で分割して配列にするパーサを記述してみる。 ただ、「"」で囲まれた文字列は空白があっても一つとする。 ダブルクォーテーションとスラッシュについては、スラッシュでエスケープするようにする。 つまり、「"」そのものは「\"」とし、「\」そのものは「\\」とする。

split_word.rb

grammar SplitWord
  rule words
    word " "+ words {
      def value
	elements[2].value.unshift(elements[0].value)
      end
    }
    /
    word {
      def value
	[super]
      end
    }    
  end

  rule word
    '"' ('\\\\' / '\\"' / (!'"' .))* '"' {
      def value
        text_value[1...-1]
      end
    }
    /
    [^ ]+ {
      def value
        text_value
      end
    }
  end
end

test.rb

require 'treetop'

Treetop.load "split_word"

parser = SplitWordParser.new

inputs = ['one', '1 2 3', 'hello   world', '"1 2" 3', '"a\\" b"', '"a\\\\" b"']

inputs.each do |input|
  if result = parser.parse(input)
    p result.value
  else
    puts "Can not parse"
  end
end

実行

split_word.rb と test.rb を同じディレクトリにおいて実行すると

$ ruby test.rb
["one"]
["1", "2", "3"]
["hello", "world"]
["1 2", "3"]
["a\\\" b"]
["a\\\\", "b\""]

となる。

GMail の検索っぽい解析

GMail のような検索文字列の解析をやってみた。

  • 「”」で囲むと特殊な文字も文字列として扱う
  • 「 」で AND
  • 「OR」で OR
  • 「-」を先頭につけると NOT
  • 「(」と「)」囲うとグループにする
  • 「before:」と「after:」で時間を指定できる

query.rb

結果は :and や :or などのシンボルと値を順に配列に入れることにした。

grammar Query
  rule queries
    query " "+ "OR" " "+ queries {
      def value
        [:or, elements[0].value, elements[4].value]
      end
    }
    /
    query " "+ queries {
      def value
        [:and, elements[0].value, elements[2].value]
      end
    }
    /
    query
  end

  rule query
    word " "+ "OR" " "+ queries {
      def value
        [:or, elements[0].value, elements[4].value]
      end
    }
    /
    word " "+ queries {
      def value
        [:and, elements[0].value, elements[2].value]
      end
    }
    /
    "(" query ")" {
      def value
        elements[1].value
      end
    }
    /
    word
  end

  rule word
    "before:" (quoted_word / word_without_special_characters) {
      def value
        [:before, elements[1].value]
      end
    }
    /
    "after:" (quoted_word / word_without_special_characters) {
      def value
        [:after, elements[1].value]
      end
    }
    /
    "-" (quoted_word / word_without_special_characters) {
      def value
        [:not, elements[1].value]
      end
    }
    /
    quoted_word
    /
    !"(" [^() ]* {
      def value
        elements[1].text_value
      end
    }
  end

  rule quoted_word
    '"' ('\\\\' / '\\"' / (!'"' .))* '"' {
      def value
        text_value[1...-1]
      end
    }
  end

  rule word_without_special_characters
    [^ ()]* {
      def value
        text_value
      end
    }
  end
end

test.rb

require 'treetop'

Treetop.load "query"

parser = QueryParser.new

inputs = ['hello   world', '"1 2" 3', '" OR "', '"a OR b"',
          'a (b c)', '((a))', '(a b)    OR   (c d)', '((a b)) OR (c d)',
          '(a OR b)  (c d)', '(a OR (b c) OR d)  (c d)',
          '"a\\" b" "a\\\\" b"', "hello OR world", '(ABC "(1, 2)")',
          '"-hi" -hello', '-hi OR -hello', '(-hi)', '(-hi OR -hello)', '(-hi -hello)', 'HELLO (-hi OR -hello)',
          'before:2011-09-03', 'after:2011-09-03', "(after:2011-09-03 before:2011-09-04)"]

inputs.each do |input|
  if result = parser.parse(input)
    p result.value
  else
    puts "Can not parse: #{input}"
  end
end

実行

$ ruby test.rb
[:and, "hello", "world"]
[:and, "1 2", "3"]
" OR "
"a OR b"
[:and, "a", [:and, "b", "c"]]
"a"
[:or, [:and, "a", "b"], [:and, "c", "d"]]
[:or, [:and, "a", "b"], [:and, "c", "d"]]
[:and, [:or, "a", "b"], [:and, "c", "d"]]
[:and, [:or, "a", [:or, [:and, "b", "c"], "d"]], [:and, "c", "d"]]
[:and, "a\\\" b", [:and, "a\\\\", "b\""]]
[:or, "hello", "world"]
[:and, "ABC", "(1, 2)"]
[:and, "-hi", [:not, "hello"]]
[:or, [:not, "hi"], [:not, "hello"]]
[:not, "hi"]
[:or, [:not, "hi"], [:not, "hello"]]
[:and, [:not, "hi"], [:not, "hello"]]
[:and, "HELLO", [:or, [:not, "hi"], [:not, "hello"]]]
[:before, "2011-09-03"]
[:after, "2011-09-03"]
[:and, [:after, "2011-09-03"], [:before, "2011-09-04"]]

変換する

上では treetop のファイルの拡張子を .rb にしていたが、ここでは .treetop にしておく。 そして、次のような Rakefile

task :default => :treetop

desc "Recompile treetop files."
task :treetop do |t|
  Dir.glob("**/*.treetop").each do |path|
    sh "tt #{path}"
  end
end

を作っておき

rake treetop

としておくと treetop のファイルが普通の ruby のファイルに変換される。

参考

Tags of current page

, ,