JavaScript で構文解析2007年09月12日 14時46分

C++ の特徴のひとつである演算子オーバーロード、その粋を極めたのが Boost Lambda (無名関数)Boost Spirit (構文解析) ではないかと思っています。JavaScript では無名関数が使えるので Lambda に関しては間に合っているとも言えますが、Spirit はそうも行きません。JavaScript 2 で演算子オーバーロードがサポートされるのならチャレンジしてみようかななどと思ってそれきりになっていました。

しかし、一部でパーサブームが起こっているというのを受け、Perl 6 Rules をつらつらと眺めているうち、正規表現のメタ文字を使えば文法定義をきれいに書けるのではと思い至りました。そこで実際に JavaScript でパーサジェネレータを作り、Spirit にあやかって Gin (ジン) と名づけてみました。

文法定義

正規表現リテラルを使うことにより、EBNF に非常に近い形で文法定義を書けます。たとえば四則演算を用いた数式パーサを作成する場合は次のようになります。

var calc = new Gin.Grammar({
  Expr: / Term ([+] Term | [-] Term)* /,
  Term: / Fctr ([*] Fctr | [/] Fctr)* /,
  Fctr: / $INT | [(] Expr [)] /
}, "Expr", Gin.SPACE);

var input = ["1 + 2 * 3", "(4 - 5) / 6", "7 * (8 - 9"];
for (var i = 0; i < input.length; i++) {
  var match = calc.parse(input[i]);
  if (match && match.full)
    print("構文木: " + match.value.toSource());
  else
    print("数式が間違っています。");
}
// 構文木: [[[1]], "+", [[2], "*", [3]]]
// 構文木: [[["(", [[[4]], "-", [[5]]], ")"], "/", [6]]]
// 数式が間違っています。

Gin.Grammar コンストラクタの引数に生成規則の集合、開始記号、スキップパーサを渡してやることで、構文解析器を生成できます。ただし、生成されるのは再帰下降パーサなので、左再帰を含んだ生成規則は扱えません。

生成規則内では丸括弧によるグループ化、縦線による選択、*、+、?、{n,m} 形式の繰り返しなどが使えるほか、角括弧、一重引用符、二重引用符で囲まれた文字列が終端記号として認識されます。Digits: / <\d+> / のように、小なり大なり記号で囲めば正規表現を使うこともできます。$ から始まるのは定義済みの終端記号で、INT のほかにも符号を含まない UINT、小数部・指数部を含む REAL、改行文字を表す EOL または NL などがあります。

解析は開始記号で指定された非終端記号の生成規則から始まり、構文解析に先立ってスキップパーサで解析される文字列 (この場合はスペース、タブ、復帰、改行の空白文字) が除去されます。スキップパーサを省略するとデフォルトで空白文字が除去されます。

実際に解析を行うには Grammar オブジェクトの parse メソッドを呼び出します。解析が成功すれば Match オブジェクト、失敗すれば null がかえります。Match オブジェクトは構文木を納める value プロパティや、文字列を最後まで読み込んだかを示す full プロパティなどを持ちます。

セマンティックアクション

入力が文法に適合しているか調べるだけならこれで十分ですが、そうでない場合はさらに構文木を処理する必要があります。後からの処理を避け、構文解析時に特定の動作を実行するためには、セマンティックアクションを付加してやります。

var calc = new Gin.Grammar({
  Expr: / Term ([+] Term:add | [-] Term:sub)* /,
  Term: / Fctr ([*] Fctr:mul | [/] Fctr:div)* /,
  Fctr: / $INT:push | [(] Expr [)] /
}, "Expr", Gin.SPACE);

var calcAction = {
  _stack: [],
  push: function (v) { this._stack.push(v); },
  pop: function () { return this._stack.pop(); },
  add: function (v) { var b = this.pop(), a = this.pop(); this.push(a + b); },
  sub: function (v) { var b = this.pop(), a = this.pop(); this.push(a - b); },
  mul: function (v) { var b = this.pop(), a = this.pop(); this.push(a * b); },
  div: function (v) { var b = this.pop(), a = this.pop(); this.push(a / b); }
};

var input = "1 + (2 - 3) * 4";
var match = calc.parse(input, calcAction);
if (match && match.full)
  print(input + " = " + calcAction.pop());

// 1 + (2 - 3) * 4 = -3

生成規則内ではコロンの後にメソッド名を続け、parse メソッドの第 2 引数にアクションをつかさどるオブジェクトを渡すことにより、適宜そのオブジェクトのメソッドが呼び出されます。この例では数値が出現するごとにそれをスタックに積み、演算子が現れれば演算結果をスタックに積み直しています。

ソースコード、サンプル

ソースファイルは gin.js (Gin 0.90) です。数式パーサ、JSON パーサの動作を確認できるサンプルもごらんください。

参考文書

コメント

_ hallux varus ― 2015年06月28日 06時42分

hello there and thank you for your info - I've certainly picked up something new from right here. I did however expertise some technical issues using this website, as I experienced to reload the web site lots of times previous to I could get it to load properly. I had been wondering if your web hosting is OK? Not that I am complaining, but slow loading instances times will very frequently affect your placement in google and can damage your high quality score if advertising and marketing with Adwords. Well I am adding this RSS to my e-mail and could look out for much more of your respective intriguing content. Make sure you update this again soon.

_ Plantar Fasciitis ― 2015年06月29日 00時16分

When I initially commented I clicked the "Notify me when new comments are added" checkbox and now each time a comment is added I get several emails with the same comment. Is there any way you can remove me from that service? Thanks a lot!

_ Ankle Pain treatment ― 2015年07月01日 07時11分

If you desire to improve your knowledge only keep visiting this site and be updated with the latest news posted here.

_ Orthotic Insoles ― 2015年07月01日 17時15分

I do consider all of the ideas you've introduced for your post. They are very convincing and will definitely work. Nonetheless, the posts are very short for newbies. Could you please extend them a little from next time? Thank you for the post.

コメントをどうぞ

※メールアドレスとURLの入力は必須ではありません。 入力されたメールアドレスは記事に反映されず、ブログの管理者のみが参照できます。

名前:
メールアドレス:
URL:
コメント:

トラックバック

このエントリのトラックバックURL: http://nanto.asablo.jp/blog/2007/09/12/1793275/tb

_ nakatani @ cybozu labs - 2007年11月22日 13時51分

OreScript時代の幕開け - yukobaの日記 http://d....