LoginSignup
12
6

More than 5 years have passed since last update.

@pocariinしくみ製作所株式会社

[ruby]Parsletで構文解析する[その3]

Last updated at Posted at 2018-06-06

Parsletで構文解析する[その3]

その1
その2

ここまで

その1で基本的なルールと簡単な数値リテラルパーサを作った。
その2で加減算のパーサを作ってASTに変換し計算できるようになった。

計算機改善

[その2]までで下記のような加減算ができるパーサ（とASTまで）を作ってきました。

(なお、ここまでは単純だったので、なにか追加するたび、ソース全体を載せてきましたが大きくなってきたので、その3以降は、追加、変更点のみ記載していきます)

require 'parslet'

class CalcParser < Parslet::Parser
  rule(:sign) { match('[-+]') }
  rule(:integer) {
    (match('[1-9]') >> match('[0-9]').repeat) |
    match('[0-9]')
  }
  rule(:decimal) {
    str('.') >> match('[0-9]').repeat(1)
  }
  rule(:number) {
    (sign.maybe >> integer >> decimal.maybe).as(:number) >> space?
  }

  rule(:exp) { (number.as(:left) >> (exp_op >> number.as(:right)).repeat).as(:exp) }
  rule(:exp_op) { match('[+-]').as(:op) >> space? }

  rule(:space) { match('\s').repeat(1) }
  rule(:space?) { space.maybe }

  root(:exp)
end

# 数値用クラス
NumericNode = Struct.new(:value) do
  def eval
    value.to_f
  end
end

# 二項演算用クラス
BinOpNode = Struct.new(:left, :op, :right) do
  def eval
    l = left.eval
    r = right.eval
    case op
    when '-'
      l - r
    when '+'
      l + r
    else
      raise "予期しない演算子です. #{op}"
    end
  end
end

class CalcTransform < Parslet::Transform
  rule(number: simple(:x)) { NumericNode.new(x) }
  # left: xxxの構造も xxxに変換する
  rule(left: simple(:x)) { x }
  rule(exp: subtree(:tree)) {
    if tree.is_a?(Array)
      # 配列ならBinOpNodeに変換
      tree.inject do |left, op_right|
        # 演算子と右辺を取り出し
        op = op_right[:op]
        right = op_right[:right]
        BinOpNode.new(left, op, right)
      end
    else
      # 配列でないならそのものを返す
      tree
    end
  }
end

parsed = CalcParser.new.parse('1 - 2 + 3')
p parsed
# => {:exp=>[{:left=>{:number=>"1"@0}}, {:op=>"-"@2, :right=>{:number=>"2"@4}}, {:op=>"+"@6, :right=>{:number=>"3"@8}}]}

ast = CalcTransform.new.apply(parsed)
p ast
# => #<struct BinOpNode left=#<struct BinOpNode left=#<struct NumericNode value="1"@0>, op="-"@2, right=#<struct NumericNode value="2"@4>>, op="+"@6, right=#<struct NumericNode value="3"@8>>

p ast.eval
# => 2.0

乗除算も追加する

上記のパーサに新しく乗除算もパースできるルールを追加しましょう。

乗除算は加減算よりも優先して処理する必要がありますが、対応としては単純で加減算より先にパースされるようにすれば対応できます。

現在加減算をパースする部分は

  rule(:exp) { (number.as(:left) >> (exp_op >> number.as(:right)).repeat).as(:exp) }
  rule(:exp_op) { match('[+-]').as(:op) >> space? }

になっていますが、ここで exp は 数値(number) か、 演算子(exp_op)で構成されていますが、これは例えば、 number は expをパースするより先にパースされるということを意味します。なので、numberより先に乗除算をパースしてやれば、加減算をパースするタイミングではすでに乗除算を先に計算するようになっているはずです。

ですので、 expと numberの間にtermという乗除算をパースするルールを追加し下記のようになります。

  rule(:exp) { (term.as(:left) >> (exp_op >> term.as(:right)).repeat).as(:exp) }
  rule(:term) { (number.as(:left) >> (term_op >> number.as(:right)).repeat).as(:term) }
  rule(:exp_op) { match('[+-]').as(:op) >> space? }
  rule(:term_op) { match('[*/]').as(:op) >> space? }

expの要素はnumberではなくtermになり、termの要素がnumberになりました。

乗除算自体の結合順序は加減算と同じく左結合なので、transformも同様に追加します。

class CalcTransform < Parslet::Transform
  # ...中略

  # expと同様の処理を追加
  rule(term: subtree(:tree)) {
    if tree.is_a?(Array)
      # 配列ならBinOpNodeに変換
      tree.inject do |left, op_right|
        # 演算子と右辺を取り出し
        op = op_right[:op]
        right = op_right[:right]
        BinOpNode.new(left, op, right)
      end
    else
      # 配列でないならそのものを返す
      tree
    end
  }
end

またAST用のstructのBinOpNodeにも新しく 乗除算の考慮を追加します。

# 二項演算用クラス
BinOpNode = Struct.new(:left, :op, :right) do
  def eval
    l = left.eval
    r = right.eval
    case op
    when '-'
      l - r
    when '+'
      l + r
    when '*'
      l * r
    when '/'
      l / r
    else
      raise "予期しない演算子です. #{op}"
    end
  end
end

ここまでを考慮し、最終的に 1 - 2 * 3 + 4 を計算するソース全体が下記になります。

require 'parslet'

class CalcParser < Parslet::Parser
  rule(:sign) { match('[-+]') }
  rule(:integer) {
    (match('[1-9]') >> match('[0-9]').repeat) |
    match('[0-9]')
  }
  rule(:decimal) {
    str('.') >> match('[0-9]').repeat(1)
  }
  rule(:number) {
    (sign.maybe >> integer >> decimal.maybe).as(:number) >> space?
  }

  rule(:exp) { (term.as(:left) >> (exp_op >> term.as(:right)).repeat).as(:exp) }
  rule(:term) { (number.as(:left) >> (term_op >> number.as(:right)).repeat).as(:term) }
  rule(:exp_op) { match('[+-]').as(:op) >> space? }
  rule(:term_op) { match('[*/]').as(:op) >> space? }

  rule(:space) { match('\s').repeat(1) }
  rule(:space?) { space.maybe }

  root(:exp)
end

# 数値用クラス
NumericNode = Struct.new(:value) do
  def eval
    value.to_f
  end
end

# 二項演算用クラス
BinOpNode = Struct.new(:left, :op, :right) do
  def eval
    l = left.eval
    r = right.eval
    case op
    when '-'
      l - r
    when '+'
      l + r
    when '*'
      l * r
    when '/'
      l / r
    else
      raise "予期しない演算子です. #{op}"
    end
  end
end

class CalcTransform < Parslet::Transform
  rule(number: simple(:x)) { NumericNode.new(x) }
  # left: xxxの構造も xxxに変換する
  rule(left: simple(:x)) { x }
  rule(exp: subtree(:tree)) {
    if tree.is_a?(Array)
      # 配列ならBinOpNodeに変換
      tree.inject do |left, op_right|
        # 演算子と右辺を取り出し
        op = op_right[:op]
        right = op_right[:right]
        BinOpNode.new(left, op, right)
      end
    else
      # 配列でないならそのものを返す
      tree
    end
  }
  rule(term: subtree(:tree)) {
    if tree.is_a?(Array)
      # 配列ならBinOpNodeに変換
      tree.inject do |left, op_right|
        # 演算子と右辺を取り出し
        op = op_right[:op]
        right = op_right[:right]
        BinOpNode.new(left, op, right)
      end
    else
      # 配列でないならそのものを返す
      tree
    end
  }
end

parsed = CalcParser.new.parse('1 - 2 + 3 * 4')
p parsed
# => {:exp=>[{:left=>{:term=>{:left=>{:number=>"1"@0}}}}, {:op=>"-"@2, :right=>{:term=>{:left=>{:number=>"2"@4}}}}, {:op=>"+"@6, :right=>{:term=>[{:left=>{:number=>"3"@8}}, {:op=>"*"@10, :right=>{:number=>"4"@12}}]}}]}
ast = CalcTransform.new.apply(parsed)
p ast
# => #<struct BinOpNode left=#<struct BinOpNode left=#<struct NumericNode value="1"@0>, op="-"@2, right=#<struct NumericNode value="2"@4>>, op="+"@6, right=#<struct BinOpNode left=#<struct NumericNode value="3"@8>, op="*"@10, right=#<struct NumericNode value="4"@12>>>

p ast.eval
# => 11.0

最後の計算結果が 11.0 なので、 1 - 2 + 3 * 4 の演算子の優先順位も考慮して計算されていますね！

二項演算改善

さて、上記までで優先度を考慮した二項演算をパースすることができましたが、普通のプログラミング言語ではもっとたくさんの優先度でもっとたくさんの演算子がありますね。全部手動で定義すると大変です。

こういうケースは一般的なので Parslet　で優先度付き(と結合順)を考慮した二項演算定義専用のルールが用意されています。

ドキュメントもあまりなくて、exampleとソース上のドキュメントしか無いのですが、 infix_expression という組み込みの処理が用意されており、下記のように呼び出します。

  infix_expression(
    演算対象の数値にマッチするルール,
    [演算子の種類、その優先度、結合順序],
    [演算子の種類、その優先度、結合順序],
    ...演算の定義が優先度の種類分続く
  )

  • 演算対象の数値にマッチするルール
    今作っている内容でいうと numberルール

  • 演算子の種類
    exp_op, term_op など演算子にマッチするルール

  • その優先度
    複数種類の演算子を定義する場合、より優先度が高いものほど高い数値を設定

  • 結合順序
    左結合なら :left, 右結合なら :right

という内容で設定します。今回の数値、加減算, 乗除算 を定義する場合は下記のように定義します。

rule(:rule_name) {
  infix_expression(
    number,
    [term_op, 10, :left],
    [exp_op, 5, :left],
  )
}

これだけで優先度、結合度を考慮したパースを行ってくれます。

infix_expressionは左辺, 演算子, 右辺パラメータが渡されるブロックを取ることができ、そのブロックで定義した内容でTransformerに構文解析結果が渡されます。
ブロックを指定しない場合、下記のようなブロックが渡されたものとしてTransformerに渡されます。

rule(:rule_name) {
  infix_expression(
    number,
    [term_op, 10, :left],
    [exp_op, 5, :left],
  ) {|l, o, r|
    {
      l: l,
      o: o,
      r: r
    }
  }
}

このデフォルトの形式で渡される想定でTransformerの処理は下記のようになります。

require 'parslet'

class CalcParser < Parslet::Parser
  rule(:sign) { match('[-+]') }
  rule(:integer) {
    (match('[1-9]') >> match('[0-9]').repeat) |
    match('[0-9]')
  }
  rule(:decimal) {
    str('.') >> match('[0-9]').repeat(1)
  }
  rule(:number) {
    (sign.maybe >> integer >> decimal.maybe).as(:number) >> space?
  }
  rule(:expression) {
    infix_expression(
      number,
      [term_op, 10, :left],
      [exp_op, 5, :left],
    )
  }

  rule(:exp_op) { match('[+-]') >> space? }
  rule(:term_op) { match('[*/]') >> space? }

  rule(:space) { match('\s').repeat(1) }
  rule(:space?) { space.maybe }

  root(:expression)
end

# 数値用クラス
NumericNode = Struct.new(:value) do
  def eval
    value.to_f
  end
end

# 二項演算用クラス
BinOpNode = Struct.new(:left, :op, :right) do
  def eval
    l = left.eval
    r = right.eval
    case op
    when '-'
      l - r
    when '+'
      l + r
    when '*'
      l * r
    when '/'
      l / r
    else
      raise "予期しない演算子です. #{op}"
    end
  end
end

class CalcTransform < Parslet::Transform
  rule(number: simple(:x)) { NumericNode.new(x) }
  rule(left: simple(:x)) { x }

  rule(
    l: simple(:l),
    o: simple(:o),
    r: simple(:r)
  ) {
    BinOpNode.new(l, o.to_s.strip, r)
  }
end

parsed = CalcParser.new.parse('1 + 2 * 3 / 6 - 4')
p parsed
# => {:l=>{:l=>{:number=>"1"@0}, :o=>"+ "@2, :r=>{:l=>{:l=>{:number=>"2"@4}, :o=>"* "@6, :r=>{:number=>"3"@8}}, :o=>"/ "@10, :r=>{:number=>"6"@12}}}, :o=>"- "@14, :r=>{:number=>"4"@16}}
ast = CalcTransform.new.apply(parsed)
p ast
# => <struct BinOpNode left=#<struct BinOpNode left=#<struct NumericNode value="1"@0>, op="+", right=#<struct BinOpNode left=#<struct BinOpNode left=#<struct NumericNode value="2"@4>, op="*", right=#<struct NumericNode value="3"@8>>, op="/", right=#<struct NumericNode value="6"@12>>>, op="-", right=#<struct NumericNode value="4"@16>>

p ast.eval
# => -2.0

生の文字列 1 + 2 * 3 / 6 - 4の計算結果が-2.0になり、正常に計算できていますね！

まとめ

Parsletに関して、単純なパーサから、AST変換、ASTの評価、二項演算の改善まで見てきましたが、最初はとっつきにくいですがある程度できた後に新しいルールを追加するのはとても簡単に感じました。

ある程度複雑な構文はもちろん、比較的シンプルな構文でも正規表現などでゴリゴリ解析するよりは将来のメンテナンスコストは低いとも感じているので、使えそうなケースがあれば使っていきたいですね。その際、この記事が参考になれば幸いです。

今回作ったサンプル(github)

12
6
1

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
12
6