下降再帰/演算子順位で数式パーサー

JavaScript

前回の記事の続き的な何か.

数式パーサーを下降!!!! じゃなくて書こう!!!


実は, id:ajalabox さんの http://d.hatena.ne.jp/ajalabox/20110328/1301319299 にかなり精神的に影響を受けた.

うおおおおおおおおおおおおお俺も言語処理系作りてええええええええええええええええええええ.

(新しい言語を作りたいってのも内心あるけど, そりゃもっと先の話だわ

ふう.

さてさて.

数式パーサーなら下降再帰が一番楽なんじゃないでしょうか?

//  Recursive descent expression parser

//  E ::= T { ("+" | "-") T }
//  T ::= F { ("*" | "/") F }
//  F ::= "(" E ")" | "+" F | "-" F | digit

try { console; var print = console.log; } catch (e) {};

function calc (text) {
  var _text = text;
  var digit = /^((?:(?:0|[1-9][0-9]*)(?:\.[0-9]*|)|\.[0-9]+)(?:[eE][+-]?[0-9]+)?)/,
      white = /^(\s+)/,
      ans = expr();
  if (text) error();
  return ans;

  function expr () {
    var ans = term();
    while (text) {
      if (next('+')) {
        ans = ans + term();
      } else if (next('-')) {
        ans = ans - term();
      } else {
        break;
      }
    }
    return ans;
  }
  function term () {
    var ans = fact();
    while (text) {
      if (next('*')) {
        ans = ans * fact();
      } else if (next('/')) {
        ans = ans / fact();
      } else {
        break;
      }
    }
    return ans;
  }
  function fact () {
    var ans = 0;
    if (next('(')) {
      ans = expr();
      if (!next(')')) {
        error('unmatched (');
      }
    } else if (next('+')) {
      ans = fact();
    } else if (next('-')) {
      ans = -fact();
    } else {
      ans = num();
    }
    return ans;
  }
  function num () {
    skipWhite();
    var d = digit(text);
    if (d) {
      text = text.slice(d[0].length);
      skipWhite();
      return parseFloat(d[0]);
    }
    error();
  }
  function next (s) {
    skipWhite();
    if (text[0] === s) {
      text = text.slice(s.length);
      skipWhite();
      return true;
    }
    return false;
  }
  function skipWhite () {
    if (white(text)) {
      text = text.slice(RegExp.$1.length);
    }
  }
  function error (m) {
    throw (m || 'unexpected token: ' + text + '\n                  ^');
  }
}

var e = (' 3.2+ 22 + 0.e10 * -.1e-1 - 2.3e1 - - - (1 - 3 * 3 )* 3 * 4- 3');
print('expression: ' + e);
print('answer: ' + calc(e));
print('eval: ' + eval(e));
// expression:  3.2+ 22 + 0.e10 * -.1e-1 - 2.3e1 - - - (1 - 3 * 3 )* 3 * 4- 3
// answer: 95.2
// eval: 95.2

やったね!!!!

分かりやすいね! ばんざい!!!

特に問題なさそう.


お次は演算子順位構文解析法によるパーサー.

//  Operator precedence grammar expression parser

//  E ::= T { ('+' | '-') T }
//  T ::= F { ('*' | '/') F }
//  F ::= '(' E ')' | digit

try { console; var print = console.log; } catch (e) {};

Array.prototype.last = function () { return this.slice(-1)[0]; };

function calc (text) {
  var _text = text;
  var digit = /(^(?:(?:0|[1-9][0-9]*)(?:\.[0-9]*|)|\.[0-9]+)(?:[eE][+-]?[0-9]+)?)/,
      operator = /^(\+|\-|\*|\/)/,
      paren = /^(\(|\))/,
      token = new RegExp('^(' + paren.source + '|' + digit.source + '|' + operator.source + ') *'),
      white = /^(\s+)/,
      EOF = { toString: function () { return 'EOF'; } };
  var stack = [],
      out = [],
      priorityl = { '(': 0, ')': 5, '+': 2, '-': 2, '*': 4, '/': 4, EOF: -1 },
      priorityr = { '(': 5, ')': 0, '+': 1, '-': 1, '*': 3, '/': 3, EOF: -1 },
      fun = {
    '+': function (x, y) { return x + y; },
    '-': function (x, y) { return x - y; },
    '*': function (x, y) { return x * y; },
    '/': function (x, y) { return x / y; }
  };
  while (next() === undefined);
  return out[0];

  function next () {
    var a = takeNext();
    text = text.slice(a.length);
    if (digit(a)) {
      output(a);
    } else {
      while (priorityl[stack.last()] >= priorityr[a]) output(stack.pop());
      stack.push(a);
    }
    if (a === EOF) return true;
  }
  function takeNext () {
    skipWhite();
    if (text === '') return EOF;
    if (token(text)) return RegExp.$1;
    throw 'Unexpected token. \n'
        + _text + '\n'
        + (new Array(_text.length - text.length)).join(' ') + ' ^\n';
  }
  function output (s) {
    var l, r;
    if (digit(s)) {
      out.push(parseFloat(s));
    } else if (operator(s)) {
      r = out.pop(), l = out.pop();
      out.push(fun[s](l, r));
    }
  }
  function skipWhite () {
    if (white(text)) {
      text = text.slice(RegExp.$1.length);
    }
  }
}

var e = '(.375 + ( 22- 111*3))* .2 * 3 + 16 / (3.2 / 8 )- 1 - (2 - .3)';
print('expression: ' + e);
print('answer: ' + calc(e));
print('eval: ' + eval(e));

// expression: (.375 + ( 22- 111*3))* .2 * 3 + 16 / (3.2 / 8 )- 1 - (2 - .3)
// answer: -149.075
// eval: -149.075


何気に下降再帰より短い!!!


括弧とかは大丈夫だけど, 単項のマイナスとかプラスが使えない.

単項演算子のマイナス使おうと思ったら...

  • ( か + か - か * か / の後 → 単項演算子の-

みたいに分類しなきゃいけないのか...

なんかめんどくさいなぁ.