正規表現利用間に合わせパーサ

正規表現を利用した、ちょこっとまにあわせパーサができた。

使い方だが、まず、スキャナーの字句解析ルールを設定した配列を引数にして、Lex クラスのオブジェクトを作る。lex.buf = "(1 + 2) + 3" のように、Lex オブジェクトのバッファに、解析したい文字列を入れると、lex.get を実行するたびに、戻り値としてトークンと値が帰ってくる。

字句解析ルールは[ 正規表現によるパターン, トークン名(英字一文字), 値を戻すときの処理]という配列の配列だ。値を戻すときの処理は、たとえば数値データなどで文字列を数値にするときなどに使う。トークン名を英字一文字にしたことによってパーサのデータの処理が正規表現を使ってできる。

次にパーサのルールを設定するが、パーサのルールは、[トークンのパターン, パターンが一致して縮約するときのトークン, パターンが一致したときの値の処理] という配列の配列だ。これを引数にして、Parse オブジェクトを作る。パーサのデータは parser.set(token, value) で取り込む。lex.get の戻り値の種類と一致しているので、そのまま、parser.set の引数することができる。

パーサのデータの入力が終わったら、parser.parse でパタンマッチが行われる。パターンがマッチしたら true が、マッチしなければ false が帰ってくる。

最大の特徴はルールを設定するだけですぐにパーサが使えるようになること。ちょっと改造すればルールを動的に変更することも可能だ。ちょこっと間に合わせのパーサを作るという目的は一応達成できた。

パーサは正規表現を利用しているので、厳密な構文解析ではなくパターンマッチで行われる。それでも、演算の優先順位や括弧の動作を解析できるように工夫できる、たとえば、1+2 のような優先順位の低い計算は、前後の演算子のタイプをチェックすることによって、先に計算されないようにパターンを設計できる。

下のプログラムは、簡単な正の整数の演算プログラムだ。単項演算子がないので負の数は直接には記述できない。(0 - 5 のように入力すれば負の数も使える。)

正規表現利用間に合わせパーサ quickparse.rb

class Lex
  def initialize(rule)
    @rule = rule
    @buf = ""
  end
  attr_accessor :buf
  def get
    @rule.each do |rule, token, action|
      if @buf =~ rule
        @buf = $'
        return token, action.call($&)
      end
    end
    return nil,nil
  end
end

class Parse
  def initialize(rule)
    @rule = rule
    @tokens = ""
    @values = []
  end
  attr_accessor :tokens, :values

  def set(token, value)
    @tokens += token
    @values.push(value)
  end

  def parse
    @rule.each do |rule, to, action|
      if ind = (rule =~ @tokens)
        @tokens.sub!(rule, to)
        action.call(ind, @values)
        return true
      end
    end
    return false
  end

  def clear
    @tokens = ""
    @values = []
  end
end

lex_rule = [[/exit/, 'e', Proc.new{|val| exit}],
            [/^\(/, 'l', Proc.new{|val| val}],
            [/^\)/, 'r', Proc.new{|val| val}],
            [/^\d+/, 'N', Proc.new{|val| val.to_i}],
            [/^\+/, 'o', Proc.new{|val| '+'}],
            [/^\-/, 'o', Proc.new{|val| '-'}],
            [/^\*/, 'O', Proc.new{|val| '*'}],
            [/^\//, 'O', Proc.new{|val| '/'}],
            [/^\s+/, 's', Proc.new{|val| val}]]

lex = Lex.new(lex_rule)

parse_rule = [[/s/, '', Proc.new{|ind, values| values.delete_at(ind)}],
  [/NON/, 'N', Proc.new{|ind, values| operator(ind, values)}],
  [/([ol])NoN([or])/, '\1N\2', Proc.new{|ind, values| operator(ind+1, values)}],
  [/^NoN$/, 'N', Proc.new{|ind, values| operator(ind, values)}],
  [/^NoNo/, 'No', Proc.new{|ind, values| operator(ind, values)}],
  [/lNr/, 'N', Proc.new{|ind, values| values.delete_at(ind); values.delete_at(ind+1)}]]

def operator(ind, values)
  val_1 = values[ind]
  op = values[ind+1]
  val_2 = values[ind+2]
  values.delete_at(ind)
  values.delete_at(ind)
  case op
  when '+'
    values[ind] = val_1 + val_2
  when '-'
    values[ind] = val_1 - val_2
  when '*'
    values[ind] = val_1 * val_2
  when '/'
    values[ind] = val_1 / val_2
  end
end

parser = Parse.new(parse_rule)

while true
  print '> '
  lex.buf = gets.chomp

  t, v = lex.get
  while (t)
    parser.set(t, v)
    t, v = lex.get
  end

  while(parser.parse)
    p parser.tokens
    p parser.values
  end

  puts parser.values.pop
  parser.clear
end

実行結果

C:\Users\tomokiyo\Documents\Ruby>ruby quickparse.rb
> 1 + 2 * 3
"NosNsOsN"
[1, "+", " ", 2, " ", "*", " ", 3]
"NoNsOsN"
[1, "+", 2, " ", "*", " ", 3]
"NoNOsN"
[1, "+", 2, "*", " ", 3]
"NoNON"
[1, "+", 2, "*", 3]
"NoN"
[1, "+", 6]
"N"
[7]
7
> exit
[PR]
by tnomura9 | 2008-04-07 20:01 | Ruby | Comments(0)
<< 改良型QアンドAプログラム トークン列の正規表現 その2 >>