Rubyでパーサーを書いてみたくなってちょっと調べてみたら、strscanという標準ライブラリがあるらしいので、使ってみることにした。

以下、単純な四則演算パーサー。

# ライブラリの読み込み
require "strscan"

# 構文木
module AST
  BinOp = Struct.new :op, :lhs, :rhs do
    def value
      op.to_proc.call lhs.value, rhs.value
    end
    def to_s
      lhss = lhs.instance_of?(BinOp) && opRank(op) > opRank(lhs.op) ? "(#{lhs})" : lhs.to_s
      rhss = rhs.instance_of?(BinOp) && opRank(op) > opRank(rhs.op) ? "(#{rhs})" : rhs.to_s
      "#{lhss} #{op} #{rhss}"
    end
    
    private
    def opRank(op)
      case op
      when :+, :-
        1
      when :*, :/
        2
      end
    end
  end
  UnOp  = Struct.new :op, :rhs do
    def value
      op.to_proc.call rhs.value
    end
    def to_s
      "#{op}#{rhs}"
    end
  end
  Num   = Struct.new :value do
    def to_s
      value.to_s.gsub(/\.?0+$/, "")
    end
  end
end

# パーサー
class Parser
  def parse(src)
    @scanner = StringScanner.new src
    parse_expr
  end

  private
  include AST

  #expr <- term (('+'|'-') term)*
  def parse_expr
    ast = parse_term

    while op = scan(/[+-]/)
      ast = BinOp.new op.intern, ast, parse_term
    end

    ast
  end

  #term <- fact (('*'|'/') fact)*
  def parse_term
    ast = parse_fact
    
    while op = scan(/[*\/]/)
      ast = BinOp.new op.intern, ast, parse_fact
    end
    
    ast
  end

  #fact <- ('+'|'-') fact
  #      | '(' expr ')'
  #      | float
  def parse_fact
    if op = scan(/[+-]/)
      ast = UnOp.new op.intern, parse_fact
    elsif scan(/\(/)
      ast = parse_expr
      raise "excepted ')'" unless scan /\)/
    else
      ast = parse_float
    end
    
    ast
  end

  def parse_float
    raise "unexcepted" unless value = scan(/([1-9][0-9]*|0+)(\.[0-9]*)?/)
    Num.new value.to_f
  end

  def scan(rex)
    space
    @scanner.scan rex
  end
  
  def space
    @scanner.scan(/\s+/)
  end
end

if __FILE__ == $0
  require "pp"

  parser = Parser.new

  while (print ">>> "; src = gets.chomp) != "quit"
    begin
      ast = parser.parse src
      puts "input  => #{ast}"
      pp ast
      puts "result => #{ast.value.to_s.gsub(/\.0+$/, "")}"
    rescue => e
      puts "parse error", e
    end
  end
end

パーサーの部分はそれなりに短く書けた感じ。

RParsecとかはメンテされてなさそうだけどどうなんだろう？