他所に書いていたものを引っ越してきました。元の記事公開日は 2020-07-05 です。

パーサ入門の定番である四則演算の電卓です。

こういうのは、単体でも何かしら実用的に使えることが分かっているとモチベーション的にいいんですよね。どうしようかなと考えていたところ、昔から世界中でめちゃくちゃ実用されているプログラムがあったことを思い出しました。そう、 expr コマンドです。

まあ、自分が作ったものをほんとに実用するかというと話は別なわけですが、いいんです。実用できると思えて、気分が乗れば。

メモ。

expr コマンドと同じなので、字句解析はなし。コマンドライン引数が渡ってきた時点でトークンに別れている
Rubyで作る奇妙なプログラミング言語の Bolic の四則演算部分の写経からスタート
- 手書きの再帰下降パーサ
しかし、そのままでは expr コマンドと同じ挙動にならないので、いくつか手を加えなければいけない。簡単な順から:
- 剰余（乗算・除算と同じ結合順位）
- 括弧
- 左結合
  - たとえば 3 - 2 - 1 が与えられた場合、 3 - (2 - 1) ではなく (3 - 2) - 1 と解釈する
ゼロ除算の場合は expr: division by zero と標準エラーに出力して exit 2 する、といったあたりも真似しようとしたが、ここだけ対応しても中途半端だし Ruby が出す例外にまかせることにした
（余談）expr コマンドに数の計算以外の機能（文字列のマッチなど）があると今回調べていて知った

expr コマンドと同じ結果になればよいので、テストコードはこんな感じで書いてました。

  def execute(expr)
    MyExpr.run(expr.split(" ")).to_s
  end

  def test
    assert_equal(
      `expr '(' 1 + 2 ')' '*' '(' 3 + 4 ')'`.chomp,
      execute("( 1 + 2 ) * ( 3 + 4 )")
    )
  end

実行の例:

$ ./my_expr.rb '(' 2 + 3 ')' '*' 4
20

以下、書いたもの。160行程度です。

#!/usr/bin/env ruby

class Parser
  class ParseError < StandardError; end

  def self.parse(tokens)
    new(tokens).parse()
  end

  def initialize(tokens)
    @tokens = tokens
    @cur = 0
  end

  def parse
    parse_expression()
  end

  def consume(token, exception: false)
    if current_token == token
      @cur += 1
      true
    else
      if exception
        raise ParseError, "expected <#{token}> / got <#{current_token}>"
      end
      false
    end
  end

  def current_token
    @tokens[@cur]
  end

  def additive?
    %w[+ -].include?(current_token)
  end

  def multiply?
    %w[* / %].include?(current_token)
  end

  def number?(token)
    /^-?\d+$/ =~ token
  end

  def parse_expression
    parse_additive()
  end

  # multiply additive_tail*
  def parse_additive
    tree = parse_multiply()

    while additive?
      operator, multiply = parse_additive_tail()
      tree = [operator, tree, multiply]
    end

    tree
  end

  # ( '+' | '-' ) multiply
  def parse_additive_tail
    case
    when consume("+") then [:+, parse_multiply()]
    when consume("-") then [:-, parse_multiply()]
    else
      raise ParseError, "expected '+' or '-' / got <#{current_token}>"
    end
  end

  # number | '(' exp ')'
  def parse_factor
    if consume("(")
      exp = parse_expression()
      consume(")", exception: true)
      exp
    else
      parse_number()
    end
  end

  # factor multiply_tail*
  def parse_multiply
    tree = parse_factor()

    while multiply?
      operator, factor = parse_multiply_tail()
      tree = [operator, tree, factor]
    end

    tree
  end

  # ( '*' | '/' | '%' ) factor
  def parse_multiply_tail
    operator =
      case
      when consume("*") then :*
      when consume("/") then :/
      when consume("%") then :%
      else
        raise ParseError, "expected '*', '/' or '%' / got <#{current_token}>"
      end

    [operator, parse_factor()]
  end

  def parse_number
    token = current_token
    @cur += 1
    if number?(token)
      token.to_i
    else
      raise ParseError, "not a number <#{token}>"
    end
  end
end

class MyExpr
  def self.run(tokens)
    new(tokens).run()
  end

  def initialize(tokens)
    @tokens = tokens
  end

  def run
    tree = Parser.parse(@tokens)
    eval(tree)
  end

  def eval(tree)
    if tree.is_a?(Integer)
      tree
    else
      operator, left, right = tree
      case operator
      when :+ then eval(left) + eval(right)
      when :- then eval(left) - eval(right)
      when :* then eval(left) * eval(right)
      when :/ then eval(left) / eval(right)
      when :% then eval(left) % eval(right)
      else
        raise "invalid operator <#{operator}>"
      end
    end
  end
end

if $0 == __FILE__
  puts MyExpr.run(ARGV)
end

2020-07-20 追記

除算の結果が負になる場合の丸めの挙動は expr コマンドと Ruby で異なっていました。

  $ ruby -v
ruby 2.7.1p83 (2020-03-31 revision a0c7c23c9c) [x86_64-linux]
  $ ruby -e "p 7 / -3"
-3

  $ expr 7 / -3
-2

参考

この記事を読んだ人は（ひょっとしたら）こちらも読んでいます

Discussion