JavaScriptで数式解析パーサーを20行で作る方法

JavaScriptで数式解析パーサー作りたい。

数式を解析評価できるパーサー
例えば 5*(4/(2-1))+3 だったら
その評価値 23 を返すみたいな…

ググると色々出てきます。

逆ポーランド記法とか抽象構文木とか…

自力で実装するのも面白いですが、
より汎用的なパーサーを作る方法があります。

それが Rena.js というライブラリ

少し癖があるけど汎用性が高いので、
これで +-*/^() に対応したパーサーを作りました。

このページの目次

Rena.jsをインストールまたは読込
Rena2.jsで数式パーサーを作ってみた
Rena2.jsで重要となるメソッド一覧
数式パーサーをBigIntに対応させる
数式解析ライブラリを使うのもアリ
Rena.jsは数式以外のパーサー作成に使える

Rena.jsをインストールまたは読込

下記で公開されているライブラリです。

▼ GitHub : y-moriguchi/rena2

GitHub

GitHub - y-moriguchi/rena2: A parsing library by Parsing Expression Grammar

https://github.com/y-moriguchi/rena2

A parsing library by Parsing Expression Grammar. Contribute to y-moriguchi/rena2 development by creating an account on GitHub.

▼ Node.jsならnpmからインストール

npm install rena2

1	npm install rena2

▼ ブラウザで読み込む場合

<script src="rena2.js"></script>

1	<script src="rena2.js"></script>

MITライセンスで配布されてます。

名前から分かるように旧バージョン Rena.js（ https://github.com/y-moriguchi/rena-js ）もあったのですが、そちらは廃止（obsolete）になってます。今はRena2.jsを使うのが推奨されてます。

▼ これを使えば色々なパーサーが作成可能

CSV・JSONパーサーとか、
簡易的なコンパイラーとか、
数式解析評価パーサーとか、

そういうのが手軽に作れるのが利点です。

Rena2.jsで数式パーサーを作ってみた

次の仕様で数式パーサーを作ります。

数式には少数含む数値を含められる
演算子は +-*/^() に対応する
数式を解析評価して１つの値で返す

一見すると複雑そうに見えますが
Rena2.jsなら十数行もあれば簡単に書けます。

▼ 数式パーサーのコードがこちら

var r = Rena2();
var formulaParser = r.letrec((f1, f2, f3, f4)=>{
  return r.then(f2, r.zeroOrMore(r.or(
    r.action(r.then("+", f2), (x, a, b)=>{ return b + a; }),
    r.action(r.then("-", f2), (x, a, b)=>{ return b - a; }))))
}, (f1, f2, f3, f4)=>{
  return r.then(f3, r.zeroOrMore(r.or(
    r.action(r.then("*", f3), (x, a, b)=>{ return b * a; }),
    r.action(r.then("/", f3), (x, a, b)=>{ return b / a; }))))
}, (f1, f2, f3, f4)=>{
  return r.then(f4, r.zeroOrMore(r.or(
    r.action(r.then("^", f4), (x, a, b)=>{ return b ** a; }))))
}, (f1, f2, f3, f4)=>{
  return r.or(r.real(), r.then("(", f1, ")"))
});

var parseFormula = (formula)=>{
  return formulaParser(formula, 0, 0).attr
};

var r = Rena2();

var formulaParser = r.letrec((f1, f2, f3, f4)=>{

return r.then(f2, r.zeroOrMore(r.or(

r.action(r.then("+", f2), (x, a, b)=>{ return b + a; }),

r.action(r.then("-", f2), (x, a, b)=>{ return b - a; }))))

}, (f1, f2, f3, f4)=>{

return r.then(f3, r.zeroOrMore(r.or(

r.action(r.then("*", f3), (x, a, b)=>{ return b * a; }),

r.action(r.then("/", f3), (x, a, b)=>{ return b / a; }))))

}, (f1, f2, f3, f4)=>{

return r.then(f4, r.zeroOrMore(r.or(

r.action(r.then("^", f4), (x, a, b)=>{ return b ** a; }))))

}, (f1, f2, f3, f4)=>{

return r.or(r.real(), r.then("(", f1, ")"))

});

var parseFormula = (formula)=>{

return formulaParser(formula, 0, 0).attr

};

▼ 数式パーサーに色々な式を渡してみた

console.log(parseFormula("12/3+4*5"));
  /// => 24
console.log(parseFormula("4/2*(1-3)*5"));
  /// => -20
console.log(parseFormula("123*45+67*890"));
  /// => 65165
console.log(parseFormula("2+(5*(7*9))/3-14680"));
  /// => -14573
console.log(parseFormula("2^3+4^5+6^7+8^9"));
  /// => 134498696

console.log(parseFormula("12/3+4*5"));

/// => 24

console.log(parseFormula("4/2*(1-3)*5"));

/// => -20

console.log(parseFormula("123*45+67*890"));

/// => 65165

console.log(parseFormula("2+(5*(7*9))/3-14680"));

/// => -14573

console.log(parseFormula("2^3+4^5+6^7+8^9"));

/// => 134498696

初見だと意味不明だと思います(笑)
自分自身も初めて見た時そう思いました。

でも１つ１つかみ砕いていけば簡単です。

Rena2.jsで重要となるメソッド一覧

Rena.jsで構文解析が簡単な理由…

それは豊富な解析メソッドが用意されてるからです。

上記コードで使った主要メソッドをまとめます。

▼ 数式パーサーでは以下メソッドを多用

Rena2.letrec()

引数に１つ以上の関数を渡し、その関数を再帰的に実行できるメソッド。最初に渡した関数の戻り値をreturnして返す。例えば４つの引数を渡したなら、引数の関数には (f1,f2,f3,f4) のように自分自身を含む関数が渡される。例えば上記コードの次の部分

r.letrec((f1, f2, f3, f4)=>{
return r.then(f2, r.zeroOrMore(r.or(
r.action(r.then("+", f2), (x, a, b)=>{ return b + a; }),
r.action(r.then("-", f2), (x, a, b)=>{ return b - a; }))))
}, ...)

r.letrec((f1, f2, f3, f4)=>{

return r.then(f2, r.zeroOrMore(r.or(

r.action(r.then("+", f2), (x, a, b)=>{ return b + a; }),

r.action(r.then("-", f2), (x, a, b)=>{ return b - a; }))))

}, ...)

ここでは４つの引数で+-*/^()を優先順位の高い順に処理している。もし優先度の異なる演算子を増やしたいなら、その分だけ関数引数が必要になる。

Rena2.then()
複数の文字列（literal）や正規表現（regular expression）を結合するための関数。引数はいくつでも取れる。最も多用されるメソッドの１つ
Rena2.action()
第１引数に正規表現または文字列、第２引数にその表現に対して実行する関数（ここなら四則演算＋累乗＋括弧展開）を定義する。第２引数の関数引数は (x, a, b) のようになっているが、x はマッチした文字列、a は左辺のオペランド、b は右辺のオペランドを表す

主要なメソッドの役割はこういう感じ

基本的には上記メソッドの組み合わせです。

数式パーサーをBigIntに対応させる

自分的にはここからが本題です。

今作った数式パーサーをBigInt対応させます。

▼ BigIntとはなにか

BigInt 値は、単に BigInt と呼ばれることもありますが、bigint プリミティブです。整数リテラルの末尾に n を追加するか、BigInt() コンストラクターを呼び出し、整数値または文字列値を与えることで生成することができます（ただし new 演算子なしで）。

引用元　：　https://developer.mozilla.org/ja/docs/Web/JavaScript/Reference/Global_Objects/BigInt

▼ BigInt対応させた数式パーサー例

var r = Rena2();
var formulaParser = r.letrec((f1, f2, f3, f4)=>{
  return r.then(f2, r.zeroOrMore(r.or(
    r.action(r.then("+", f2), (x, a, b)=>{ 
      return BigInt(b) + BigInt(a); }), 
    r.action(r.then("-", f2), (x, a, b)=>{ 
      return BigInt(b) - BigInt(a); }))))
}, (f1, f2, f3, f4)=>{
  return r.then(f3, r.zeroOrMore(r.or(
    r.action(r.then("*", f3), (x, a, b)=>{ 
      return BigInt(b) * BigInt(a); }),
    r.action(r.then("/", f3), (x, a, b)=>{ 
      return BigInt(b) / BigInt(a); }))))
}, (f1, f2, f3, f4)=>{
  return r.then(f4, r.zeroOrMore(r.or(
    r.action(r.then("^", f4), (x, a, b)=>{ 
      return BigInt(b) ** BigInt(a); }))))
}, (f1, f2, f3, f4)=>{
  return r.or(r.real(), r.then("(", f1, ")"))
});
var parseFormula = (formula)=>{
  return formulaParser(formula, 0, 0).attr
};

var r = Rena2();

var formulaParser = r.letrec((f1, f2, f3, f4)=>{

return r.then(f2, r.zeroOrMore(r.or(

r.action(r.then("+", f2), (x, a, b)=>{

return BigInt(b) + BigInt(a); }),

r.action(r.then("-", f2), (x, a, b)=>{

return BigInt(b) - BigInt(a); }))))

}, (f1, f2, f3, f4)=>{

return r.then(f3, r.zeroOrMore(r.or(

r.action(r.then("*", f3), (x, a, b)=>{

return BigInt(b) * BigInt(a); }),

r.action(r.then("/", f3), (x, a, b)=>{

return BigInt(b) / BigInt(a); }))))

}, (f1, f2, f3, f4)=>{

return r.then(f4, r.zeroOrMore(r.or(

r.action(r.then("^", f4), (x, a, b)=>{

return BigInt(b) ** BigInt(a); }))))

}, (f1, f2, f3, f4)=>{

return r.or(r.real(), r.then("(", f1, ")"))

});

var parseFormula = (formula)=>{

return formulaParser(formula, 0, 0).attr

};

単純に Rena2.action() で演算を実行する時、 BigInt(b) + BigInt(a) のようにBigIntでラップしてあげればいいだけです。

これでBigInt対応も完了

数式解析ライブラリを使うのもアリ

もちろんライブラリを使うという手もあります。

▼ 特に使いやすそうなライブラリ

GitHub

GitHub - bylexus/fparse: A JavaScript Formula Parser

https://github.com/bylexus/fparse

A JavaScript Formula Parser. Contribute to bylexus/fparse development by creating an account on GitHub.

上記ライブラリは変数にも対応してます。

こういうのも便利なんですが、たとえば「数式をBigIntとして解析してBigIntで評価したい」「独自演算子を定義したい」などの特殊なケースでは使えません。

そういう時はRena.jsが便利です。

Rena.jsは数式以外のパーサー作成に使える

このRena.jsは本当に汎用性が高いです。

ただ慣れるまでは少しクセがあるかも。
でも数式に限らず色々なパーサーが定義できます。

以上、JavaScriptで数式パーサーを作るでした。

JavaScriptで数式解析パーサーを20行で作る方法

Rena.jsをインストールまたは読込

Rena2.jsで数式パーサーを作ってみた

Rena2.jsで重要となるメソッド一覧

数式パーサーをBigIntに対応させる

数式解析ライブラリを使うのもアリ

Rena.jsは数式以外のパーサー作成に使える

関連記事

プロフィール

人気記事

検索してみる