treetop

まず

$ sudo gem install treetop

とする。次に

# arithmetic.treetop
grammar Arithmetic
  rule additive
    multitive '+' additive / multitive
  end

  rule multitive
    primary '*' multitive / primary
  end

  rule primary
    '(' additive ')' / number
  end

  rule number
    [1-9] [0-9]*
  end
end

という定義ファイルを作って

$ tt arithmetic.treetop

とコマンドを実行すると arithmetic.rb が作られる

#!/usr/local/bin/ruby
# vi:set ts=3 sw=3:
# vim:set sts=0 noet:

require 'rubygems'
require 'treetop/runtime'
require 'arithmetic'

parser = ArithmeticParser.new
result = parser.parse '(1+2)*3'
p result

という Ruby スクリプトを作って実行すると

SyntaxNode+Multitive0 offset=0, "(1+2)*3" (primary,multitive):
  SyntaxNode+Primary0 offset=0, "(1+2)" (additive):
    SyntaxNode offset=0, "("
    SyntaxNode+Additive0 offset=1, "1+2" (additive,multitive):
      SyntaxNode+Number0 offset=1, "1":
        SyntaxNode offset=1, "1"
        SyntaxNode offset=2, ""
      SyntaxNode offset=2, "+"
      SyntaxNode+Number0 offset=3, "2":
        SyntaxNode offset=3, "2"
        SyntaxNode offset=4, ""
    SyntaxNode offset=4, ")"
  SyntaxNode offset=5, "*"
  SyntaxNode+Number0 offset=6, "3":
    SyntaxNode offset=6, "3"
    SyntaxNode offset=7, ""

出力はこんな感じ。最初 "(1 + 2) * 3" とかを喰わせて nil しか返ってこなくて悩んだ。デフォルトでは空白を無視しない模様