人気ブログランキング | 話題のタグを見る

PEG Prioritized Choice 演算子

PEG (Parsign Expression Grammars) の特徴のひとつに、Prioritized Choice 演算子がある。たとえば次のようなルール A <- a b / a では、非終端記号 A は、a b か a のどちらかのパターンにマッチするが、マッチングの順序に優先順位があり、a b にマッチしていれば、a のマッチングは試されない。これも、次のように Ruby で簡単に実装できる。

ファイル名: peg_pc.rb

def a
  if $line =~ /^a/
    $line.sub!(/^a/, '')
    return true
  else
    return false
  end
end

def b
  if $line =~ /^b/
    $line.sub!(/^b/, '')
    return true
  else
    return false
  end
end

def ab_or_a
  line_back = $line.dup
  if (a and b)
    return true
  else
    $line = line_back
    if a
      return true
    else
      $line = line_back
      return false
    end
  end
end

$line = 'abcde'
puts $line
p ab_or_a
p $line
puts

$line = 'aacde'
puts $line
p ab_or_a
p $line
puts

$line = 'bacde'
puts $line
p ab_or_a
p $line

実行例

> ruby peg_pc.rb
abcde
true
"cde"

aacde
true
"acde"

bacde
false
"bacde"

PEG で定義したルールの通りを自然にプログラムしていくと構文解析ができてしまう。個々の関数の形もシンプルで定型的になるので難しいパーサを作っているのだという感じがしない。だんだん面白くなってきた。
by tnomura9 | 2008-04-21 19:23 | Ruby | Comments(0)
<< PEG 終端記号 PEG の rule >>