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());
// 構文木: [[[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 パーサの動作を確認できるサンプルもごらんください。



_ plenty of fish dating site of free dating ― 2015年09月25日 15時44分

My partner and I absolutely love your blog and find almost all of your post's to be just what I'm looking for. can you offer guest writers to write content to suit your needs? I wouldn't mind writing a post or elaborating on a few of the subjects you write concerning here. Again, awesome web site!

_ Minecraft Download ― 2015年10月08日 11時51分

Appreciate the recommendation. Let me try it out.

_ pof plenty of fish dating search ― 2015年10月14日 08時02分

You're so cool! I do not believe I've read anything like this before. So great to find another person with a few genuine thoughts on this subject. Really.. thanks for starting this up. This web site is one thing that's needed on the web, someone with a little originality!

_ plenty of fish dating forum ― 2015年10月14日 10時56分

Very good website you have here but I was wondering if you knew of any community forums that cover the same topics talked about here? I'd really love to be a part of group where I can get advice from other experienced individuals that share the same interest. If you have any suggestions, please let me know. Cheers!

_ pof.Com dating ― 2015年10月15日 01時34分

Wow, that's what I was looking for, what a material! existing here at this blog, thanks admin of this website.

_ plenty Of fish dating site of free dating ― 2015年10月15日 16時08分

WOW just what I was searching for. Came here by searching for Plenty Of Fish Dating Site Of Free Dating

_ Plenty Fish Dating ― 2015年10月18日 05時33分

Hi there everyone, it's my first visit at this web site, and post is really fruitful designed for me, keep up posting these types of articles.

_ Unknown ― 2015年11月03日 06時58分

Sweet blog! I found it while browsing on Yahoo News.
Do you have any tips on how to get listed in Yahoo News?

I&#39;ve been trying for a while but I never seem to
get there! Thanks

_ forskolin where to buy ― 2015年11月05日 06時44分

My partner and I absolutely love your blog and find the
majority of your post&#39;s to be what precisely I&#39;m looking for.

Does one offer guest writers to write content
for you? I wouldn&#39;t mind composing a post or elaborating on a lot of the subjects you write in relation to here.
Again, awesome weblog!

_ plenty of fish dating site of free dating ― 2015年11月06日 07時23分

Quality content is the main to be a focus for the visitors to visit the
website, that&#39;s what this web site is providing.

_ plenty of fish dating site of free dating ― 2015年11月06日 22時29分

Great goods from you, man. I have understand your stuff previous to and you are just extremely wonderful.

I really like what you&#39;ve acquired here, certainly like what you&#39;re
stating and the way in which you say it.

You make it entertaining and you still take care of to keep it wise.
I cant wait to read much more from you. This is
really a wonderful web site.

_ Plenty of fish dating site of free dating ― 2015年11月07日 12時44分

Thanks for any other magnificent post. Where else could anybody
get that kind of info in such a perfect method of writing?
I&#39;ve a presentation next week, and I&#39;m at the search for such

_ Los Angeles ― 2015年11月21日 09時23分

Hi mates, good article and fastidious arguments commented here,
I am really enjoying by these.


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




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

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