パーサ入門の定番である四則演算の電卓です。
こういうのは、単体でも何かしら実用的に使えることが分かっているとモチベーション的にいいんですよね。 どうしようかなと考えていたところ、昔から世界中でめちゃくちゃ実用されているプログラムがあったことを思い出しました。 そう、 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で素朴な自作言語のコンパイラを作った
- 四則演算と剰余のみのexprコマンドをKotlinで作ってみた - Qiita
- Kotlin で書いてみたもの