JavaScript で数式パーサを書いてみた。

背景

いままで、ちゃんとパーサというものを書いたことがなかったので勉強のためにアレコレ考えながらやってみようと思って、簡単な数式を木にするパーサを書いてみようと思ったのです＞＜

今回作るパーサの仕様

パースする数式の演算子は二項演算子 + - * / と単項演算子 + - だけ。
括弧とかは使わない。
演算の優先順位は * / のほうが + - より高い。つまり、 1 + 1 * 1 は 1 + (1 * 1)
単項演算子は二項演算子より優先順位が高い。つまり、 - 1 + 1 は (-1) + 1

で、作ってみた！

ソースコード

filter 関数とか使ってるので、 Firefox only です。

var parse = function(source) {
  var tokens = source.match(/[-+*/]|[^-+*/\s]+|\s+/g).filter(/^[^\s]/);
  var index = 0;
  var binarys = {'*':2,'/':2,'-':1,'+':1};
  var unarys = {'-':1,'+':1};
  var stack = [];

  while (tokens[index] != undefined) {

    var expression = (function() {
      var token = tokens[index++];
      if (unarys[token]) return [token, arguments.callee()]
      return token;
    })();

    var operator = tokens[index++];
    precedence = (operator == undefined) ? 0: binarys[operator];

    while (stack.length && precedence <= binarys[stack[stack.length-1]]) {
      expression = [stack.pop(), stack.pop(), expression]
    }
    stack.push(expression, operator);
  }
  return expression;
};

実際使うとこんな感じ

var tree = parse('- 1 * 2 + -3 / -4 * 5');

alert(tree); // ["+", ["*", ["-", "1"], "2"], ["*", ["/", ["-", "3"], ["-", "4"]], "5"]]

おおおおおお。

ソースの解説

自分の備忘録のために、ソースを解説します。

var tokens = source.match(/[-+*/]|[^-+*/\s]+|\s+/g).filter(/^[^\s]/);

これは、ソースをトークンに切り分けています。まず、空白、演算子、その他に分けて、 filter で空白を削除しています。

var binarys = {'*':2,'/':2,'-':1,'+':1};
var unarys = {'-':1,'+':1};

binarys は二項演算子の定義と優先度です。unarys は単項演算子の定義と優先度です。数値が大きいほど優先されます。

while (tokens[index] != undefined) {
  ..
}

トークンが無くなるまでループするんです。

var expression = (function() {
  var token = tokens[index++];
  if (unarys[token]) return [token, arguments.callee()]
  return token;
})();

再帰処理で単項演算子を木にします。expression というのは単項演算を解析した（部分）木です。木は配列で表現しています。

['-', 'a']

たとえば、 -a などはこの時点で上のような木（配列）になります。

var operator = tokens[index++];
precedence = (operator == undefined) ? 0: binarys[operator];

ここでの operator は二項演算子です。precedence はその演算子の優先度です。数式の末尾の場合は、優先度 0 になります。

while (stack.length && precedence <= binarys[stack[stack.length-1]]) {
  expression = [stack.pop(), stack.pop(), expression]
}

ここの行は、最初の１ループ目では飛ばされます。（stack が空だから

stack.push(expression, operator);

ここでは expression （左辺の部分木）と operator （二項演算子）をスタックに保存しておきます。

while (stack.length && precedence <= binarys[stack[stack.length-1]]) {
  expression = [stack.pop(), stack.pop(), expression]
}

さあ、２ループ目で一つ上の行に戻ってきました。ここで expression は１ループ目から見たら右辺に当たります。左辺と演算子はスタックにあります。precedence は次の演算子の優先度になります。
ここで、 operator と stack の演算子の優先度を比較します。ここで、優先度が同じだったり、stack の演算子のほうが高い場合はそこまでの計算は先にしてもいいはずなので、二項演算の木を作ります。

例えば、下のような演算を想像してみてください。

1 * 2 + 3 * 4

1 * 2 + まで読んだ時点で 1 * 2 は計算してしまってもいいと分かるはずです。
このように、次々と演算子を読み込んでは優先度的に組み合わせてしまってもいい式を部分木にしていくのです。
数式の末尾までいくと優先度 0 になるので、すべての数式が木になります。
以上で、ソースの解説は終わりです。

まとめ

パーサとか書いたことのない素人なので、用語とかが意味不明だと思います＞＜
一応、自分用のメモなので許してください＞＜
勉強になりました！

IT戦記

プログラミング、起業などについて書いているプログラマーのブログです😚