最近コンパイラーのお勉強をしてます.
練習で数式のパーサーをSLR(1)で書いてみたり,
単純に下降再帰で書いてみたり,
演算子順位法で書こうとしたりしています...
でも, 数式をパースするだけなら, スタックとか作らなくてもいいんじゃね?
数式を手計算で変形していくみたいにパースしていけば!
'2 * (3 + 5) + 6' -> '2 * (8) + 6' -> '2 * 8 + 6' -> '16 + 6' -> '22'
これって文字列を置換していけばいけるよね?
ってことで, 正規表現で置換していく数式パーサー書きました!
// Expression parser by RegExp // expr ::= term { ('+' | '-') term } // term ::= fact { ('*' | '/') fact } // fact ::= '(' expr ')' | digit try { console; var print = console.log; } catch (e) {}; var digit = /((?:\-|\+)? *(?:(?:0|[1-9][0-9]*)(?:\.[0-9]*|)|\.[0-9]+)(?:[eE][+-]?[0-9]+)?)/, paren = / *\( *([^()]*) *\) */, plus = new RegExp(digit.source + / *(\+|\-) */.source + digit.source), mul = new RegExp(digit.source + / *(\*|\/) */.source + digit.source), isdigit = new RegExp('^' + digit.source + '$'), addsign = function (x) { return x < 0 ? x : '+' + x; }, fun = { '+': function (x, y) { return x + y; }, '-': function (x, y) { return x - y; }, '*': function (x, y) { return addsign(x * y); }, '/': function (x, y) { return addsign(x / y); } }; String.prototype.toNum = function () { return this[0] === '-' ? - parseFloat(this.slice(1)) : this[0] === '+' ? parseFloat(this.slice(1)) : parseFloat(this); }; String.prototype.calc = function () { return paren(this) ? this.replace(paren, RegExp.$1.calc()).calc() : mul(this) ? this.replace(mul, fun[RegExp.$2](RegExp.$1.toNum(), RegExp.$3.toNum())).calc() : plus(this) ? this.replace(plus, fun[RegExp.$2](RegExp.$1.toNum(), RegExp.$3.toNum())).calc() : isdigit(this) ? this.toNum() : 'Error!'; }; function calc (expr) { print('- - - - - - - - - - '); var ans = expr.calc(); print('expression: ' + expr); print('parsed: ' + ans); try { print('eval: ' + eval(expr)); } catch (e) {}; return ans; }; calc('-2e2 + .05 * ((1 + 3) - 10) - 4 * (1 - 3 - 5)'); // - - - - - - - - - - // expression: -2e2 + .05 * ((1 + 3) - 10) - 4 * (1 - 3 - 5) // parsed: -172.3 // eval: -172.3
ちゃんとパーサーの値とevalした値が一致するはずです!
素晴らしく読みやすくて, デバッグしやすいコードですね(((ちょとまて
こんなコード書かないようにしましょう(^_^;)