RubyとParsletで算術演算のパーサを作った

はじめに

Ruby用のパーサジェネレータ、Parslet というものを見つけたので、 簡単な練習として算術演算のパーサを作ってみました。

加減乗除と剰余算・累乗（+-*/%^）、および括弧を使った数式の文字列を入力して、値を浮動小数点数で計算できます。

Parsletの基本的な使い方は Get Started が参考になりました。

方針

1. パーサで文字列をHashとArrayの組み合わせに分割
2. パース結果からASTを構築
3. ASTを評価

パーサ

まず、Parslet::Parserクラスを継承して、パースを行うクラスを用意します。

ルールはBNFの様に記述することができます。

Parsletの仕組みとして、パースされた結果はHashとArrayの組み合わせとして出力されます。

class Parser < Parslet::Parser

  #ルールを指定する
  rule(:lparen) { str('(') >> space? }
  rule(:rparen) { str(')') >> space? }

  rule(:space) { match('\s').repeat(1) }
  rule(:space?) { space.maybe }
  
  rule(:numeral) { match('[0-9]').repeat(1) }
  rule(:number) { ( numeral >> ( str('.') >> numeral ).maybe ).as(:number) >> space? }
  rule(:factor) { number | lparen >> expression.as(:expression) >> rparen }
  rule(:expression) { factor >> ( match['+-/*%^'].as(:operator) >> space? >> factor).repeat(0) }
  
  root :expression
end

実行例

parsed = Parser.new.parse("(1 + 2) * 3.5 + 4 * (2 / 4) ^ 2")
pp parsed

出力結果

[{:expression=>[{:number=>"1"@1}, {:operator=>"+"@3, :number=>"2"@5}]},
 {:operator=>"*"@8, :number=>"3.5"@10},
 {:operator=>"+"@14, :number=>"4"@16},
 {:operator=>"*"@18,
  :expression=>[{:number=>"2"@21}, {:operator=>"/"@23, :number=>"4"@25}]},
 {:operator=>"^"@28, :number=>"2"@30}]

ASTのノード

ASTのノードとして、数値リテラルを表すNumberLiteralと、二項演算を表すBinaryExpressonを用意します。

evalで評価ができます。

class NumberLiteral < Struct.new(:value)
  def eval
    value.to_f
  end
end

class BinaryOperation < Struct.new(:left, :operator, :right)
  def eval
    case operator
    when '+'
      left.eval + right.eval
    when '-'
      left.eval - right.eval
    when '*'
      left.eval * right.eval
    when '/'
      left.eval / right.eval
    when '%'
      left.eval % right.eval
    when '^'
      left.eval ** right.eval
    end
  end
end

演算子の優先順位

定数のハッシュとして、演算子の優先順位を用意します。 ASTの構築時に使用します。

OP_PRECEDENCE = {
  '+' => 10,
  '-' => 10,
  '*' => 20,
  '/' => 20,
  '%' => 20,
  '^' => 30
}

ASTの構築

construct_ast_recursiveで、パーサで得られた ((数値), (演算子, 数値), (演算子, 数値), ...) のようになった構造から、演算子の優先順位を考慮してASTを構築します。

#戻り値: 構築されたAST, 余ったexpression
def construct_ast_recursive(expression, precedence_limit)
  
  if expression.length == 0
    return nil, nil
  end

  first = expression[0]

  #最初の要素は値として取得
  case
  when first.has_key?(:number)
    lhs = NumberLiteral.new(first[:number])
  when first.has_key?(:expression)
    lhs = construct_ast(first[:expression])
  else
    raise "no expression or integer literal in expression item"
  end

  expression = expression[1..-1]
  if expression.length == 0
    expression = nil
  end

  while expression
    op = expression[0][:operator].to_s
    precedence = OP_PRECEDENCE[op]
    #演算子の優先順位が再帰で上位の優先順位以下なので中断
    if precedence <= precedence_limit
      return lhs, expression
    end
    #現在の演算子に対して右辺になるASTを再帰的に構築
    rhs, expression = construct_ast_recursive(expression, precedence)
    lhs = BinaryOperation.new(lhs, op, rhs)
  end

  return lhs, nil

end

def construct_ast(expression)
  construct_ast_recursive(expression, -1)[0]
end

評価

実際に文字列から値を評価します。

def parse(str)
  parsed = Parser.new.parse(str)
  ast = construct_ast(parsed)
  p ast.eval
end

parse("3.4 * 2 + 5 * 3") # 21.8
parse("(1 + 2) * 3.5 + 4 * (2 / 4) ^ 2") # 11.5

全ソース（gist）