📝
四則演算と剰余のみのexprコマンドをRubyで作ってみた
他所に書いていたものを引っ越してきました。元の記事公開日は 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
参考
- Rubyで作る奇妙なプログラミング言語
- 低レイヤを知りたい人のためのCコンパイラ作成入門
- パーサー(www.ss.cs.meiji.ac.jp) / archive.org
- Numeric expressions (GNU Coreutils)
この記事を読んだ人は(ひょっとしたら)こちらも読んでいます
Discussion