読者です 読者をやめる 読者になる 読者になる

レガシーコード生産ガイド

私に教えられることなら

演算子順位法で再実装

再帰下降構文解析の練習 - レガシーコード生産ガイドで作った四則演算の計算機を、BNFに依った演算子の定義ではなく、演算子順位法を用いて二項演算子を追加していけるようにした。

making-script-engine/calc.js at 307e233a5f3056914a15d8c77c6619616eb1f8ba · phaendal/making-script-engine · GitHub

しかし本を読んでもイマイチピンとこない。というより昨日の夜、集中力がもう無くなっていたのだと思う。

少し調べたらスタックを使うと書いてあったので、まずスタック使用版を作った。

git commitすらしていなかったのでコードは(スタックの痕跡を残して)消えたけど、以下の様に入力とスタックの遷移を書いて考えた。

2 + 3 * 4 ^ 5 + 6

2   |+    |3   |*  |4   |^   |5   |+                     =>   
-----------------------------------------------------------
    |     |    |   |    |    |5   |5   |       |           
    |     |    |   |4   |4 ^ |4 ^ |4 ^ |(4^5)  |           
    |     |3   |3 *|3 * |3 * |3 * |3 * |  3  * |(3*(4^5)   
2   |2 +  |2 + |2 +|2 + |2 + |2 + |2 + |  2  + |   2     + 


|=>              |6                | END               |  
|------------------------------------------------------|
|                |       6         |                   |
|(2+(3*(4^5))) + | (2+(3*(4^5))) + | ((2+(3*(4^5)))+6) |

上は入力、下は左が被演算子で右が演算子のスタック。

入力された演算子が、演算子スタックのトップより優先順位が高ければそのままpushしていく。

低ければ(5の次の+のところ)、演算子スタックが空になるか、又はトップが入力された演算子より低い順位のものになるまで、ツリーを作って被演算子スタックに積んでいく。

最後に演算子スタックが空になるまで上から順にツリーを作っていけば完成。

このバージョンでも多分動いたのだけど、ソースが壊滅的に汚くなった。複数の状態を扱うのでデバッグが面倒だった。

もっといい方法があるはずだ、と調べていると、英語版wikipediaの記事で

Operator-precedence parser - Wikipedia, the free encyclopedia

The algorithm that is presented here does not need an explicit stack; instead, it uses recursive calls to implement the stack.

ああなるほどこれも再帰でやればいいのか、と再帰で書きなおした。

それでできたものが上のコードなんだけど、図でメモしておかないと絶対にわけがわからなくなりそうだ。

もっと簡単な方法があるに違いない。頭がハッキリしたら「2週間〜」本のコードをちゃんと解読してみよう。

$ node calc.js 
1*3+4*5
expr: ((1 * 3) + (4 * 5))
result: 23
1==1
expr: (1 == 1)
result: true
1!=1
expr: (1 != 1)
result: false
2^5/32==1
expr: (((2 ^ 5) / 32) == 1)
result: true
2^5%32==0
expr: (((2 ^ 5) % 32) == 0)
result: true
3^5>3^4
expr: ((3 ^ 5) > (3 ^ 4))
result: true

感想

  • あんまりいいカンジじゃないコードだと動いても心残りがある
  • 図を簡単に描くツールがほしい
  • AAは辛い
  • テスト書こう
  • ちゃんと寝よう
広告を非表示にする