Posted at

ANTLR 4を使ってJavaScript用の数式パーサを作成する


tl;dr

ANTLR 4を使ってJavaScriptで構文解析するサンプルを作ってみた

https://github.com/recyclebin5385/antlr4-sample-20181230


はじめに

ウェブアプリケーションを作っていると、入力項目のエラーチェックの実装を要求されることがままある。

エラーチェックと言っても、単純な必須チェック、数値の最小値・最大値、文字数、文字列の書式、項目間の大小関係など様々なものがあり、さらにはそのような型にはめられない複雑な条件が要求されることもある。

入力項目がガチガチに固定されているのであれば開発者が力技で記述すれば済むが、システムのユーザが自由に入力項目を追加して、それに対して自由にエラーチェックの設定もできるようなシステムであるとそうもいかない。

そのようなときに、エラーにする条件を数式で記述できるようにしておけば、個別のエラーチェックの種別ごとに作り込みをする必要もなく、後から条件を追加された場合でも数式の書き換えだけで柔軟に対応することができるだろう。

ここで必要になるのが、文字列として記述した数式を解釈して評価するための仕組みである。

ところで、いくつかのプログラミング言語には文字列をそのまま式として評価する関数が用意されている。JavaScriptだとeval関数がそれに該当する。PythonRubyにも同様の関数が存在する。以降、この手の関数を単にeval関数と呼ぶ。

ならば式を評価するための仕組みとしてeval関数をそのまま使えばいいじゃないかと思われるかもしれないが、そのような真似はやってはいけない。

なぜなら、eval関数は与えられた文字列をそのままプログラムとして実行するので、悪意のあるユーザがシステムを停止させたり無限ループに陥ったりメモリを使い果たしたりするような式を書いて設定する可能性を捨てきれないからである。

そのような危険を避けるためには、eval関数に頼らず、独自に数式を構文解析して評価する仕組みを実装する必要がある。

そして、そのための道具のひとつがパーサジェネレータと呼ばれるツールである。

パーサジェネレータとは、式を構文解析するパーサと呼ばれるプログラムを生成するプログラムのことである。

パーサジェネレータは数多く存在するが、その中から今回はANTLR 4を選択した。

理由として、


  • 構文定義の記述の仕方が比較的容易であること

  • 複数のプログラミング言語に対応しているため他のプログラミング言語への展開が容易であること

  • 特にJavaScriptに対応しているのでウェブアプリケーションのクライアントサイドの処理にも使えること

が挙げられる。


サンプルコード

GitHubにソースコード一式を置いたので参考にしてほしい。

https://github.com/recyclebin5385/antlr4-sample-20181230

ビルドする場合は、あらかじめ開発用マシンに、JavaScriptのパッケージ管理ツールとしてnpmをインストールする。

取得したソースコードのフォルダをカレントとし、以下のコマンドを実行する。

npm install

npm run build

取得したソースコードのsample/index.htmlをブラウザで開くと動作を試すことができる。


解説

Gruntのタスクgrunt-antlr4を使い、ANTLR 4の文法定義を元にコードを生成している。

Gruntの設定において、オプションを指定してListenerを生成せずVisitorを生成するようにしている。

cf. https://github.com/recyclebin5385/antlr4-sample-20181230/blob/master/Gruntfile.js


文法ファイル

ANTLR 4の文法ファイルは以下のURLを参照。

https://github.com/recyclebin5385/antlr4-sample-20181230/blob/master/src/Expression.g4

この文法はありがちな四則演算に対応している。

式のリテラルとして十進数、true、false、nullが使用できる。

前置演算子は+、-、!が使用できる。+は特に効果はない。-は数値の正負を反転させる。!は真偽値を反転させる。

2項演算子は+、-、、/、%が使用できる。それぞれ加算、減算、乗算、除算、剰余を表す。、/、%は+、-より優先される。

丸括弧を用いて演算の優先順位を変えることができる。

top、expression、…、Decimal、WSといった記号のうち、先頭が小文字のものは非終端記号、大文字のものは終端記号になる。

Visitorを生成するとき、非終端記号に対しては対応する関数visit○○が生成される。decimalLiteralなどのリテラルを非終端記号として定義しているのはvisit○○が生成されたほうが処理を書くときに都合が良いため。


数式評価モジュール

grunt-antlr4によって生成されたJavaScriptのファイルは、フォルダdistの下に配置される。

以下は、生成されたJavaScriptおよびANTLR 4のライブラリを読み込み、数式を評価してその値を返す独自のVisitorを実装するためのコードである。

https://github.com/recyclebin5385/antlr4-sample-20181230/blob/master/src/parser-sample1.js

このファイルのコード中、ExpressionVisitorはANTLR 4が生成したVisitorを指す。それを拡張して式の評価結果を返す独自のEvalVisitorを定義する。

ExpressionVisitorのプロトタイプには文法中の非終端記号ごとに対応する関数visit○○が生成されるがすべて空実装になっているので、EvalVisitorのプロトタイプにおいてそれを上書きする。

その際、visit○○の戻り値は関数getValue()を持つオブジェクトとし、getValue()の戻り値は数式においてその非終端記号に対応する部分の評価結果になるようにする。このようにしているのは、将来的に式の機能を拡張するときに遅延評価を行えるようにするためである。

なお、このEvalVisitorは外部には公開されない。

parser-sample1.jsの公開するモジュールに、関数evalを追加する。

これは数式の文字列を引数に取り、EvalVisitorのインスタンスを作成して式の構文解析と評価を行い、その評価結果を返す関数である。


ウェブブラウザ用のスクリプト

ANTLR 4やそれを使って生成したファイルは、require関数でモジュールをインポートすることを前提としており、そのままではrequire関数を持たないウェブブラウザで実行させることができない。

その対策として、以下のようなファイルを用意する。

https://github.com/recyclebin5385/antlr4-sample-20181230/blob/master/src/antlr4-bundle.js

https://github.com/recyclebin5385/antlr4-sample-20181230/blob/master/src/parser-sample1-bundle.js

これらは、それぞれANTLR 4のモジュールおよび、今回作成した数式評価モジュールに対し、必要なファイルを結合した上でモジュールをグローバルスコープに公開し、require関数なしでもウェブブラウザ上で使えるようにするものである。

Gruntを実行すると、grunt-webpackによってフォルダdistに同名のファイルが作成される。作成されたファイルにはrequire関数でインポートされるはずのモジュールがすべて結合されているため、ウェブブラウザ上でエラーを起こすことなく実行することができる。

https://github.com/recyclebin5385/antlr4-sample-20181230/blob/master/sample/index.html および https://github.com/recyclebin5385/antlr4-sample-20181230/blob/master/sample/index.js は作成したモジュールを使って実際に数式を評価するためのサンプルである。

ビルドした後でindex.htmlをウェブブラウザで開き、数式を入力してEnterキーを押下すると、式の評価結果が表示される。

1.png

2.png