RubyとParsletで算術演算のパーサを作った
はじめに
Ruby用のパーサジェネレータ、Parslet というものを見つけたので、 簡単な練習として算術演算のパーサを作ってみました。
加減乗除と剰余算・累乗(+-*/%^)、および括弧を使った数式の文字列を入力して、値を浮動小数点数で計算できます。
Parsletの基本的な使い方は Get Started が参考になりました。
方針
- パーサで文字列をHashとArrayの組み合わせに分割
- パース結果からASTを構築
- 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