PEGめも

PEG - Parsing Grammer Expression

参照
http://www.konokida.com/orengo/01.ParsingExpressionGrammar/index.htmlhttp://d.hatena.ne.jp/kmizushima/20100203/1265183754http://d.hatena.ne.jp/ku-ma-me/20070906/p1http://code.google.com/p/dupsrem/source/browse/trunk/dupes/chrome/content/removedupes/kouprey.js?r=15http://practical-scheme.net/wiliki/wiliki.cgi?Rui%3AParsingExpressionGrammar

入力に対してパーサを次々に試していき、成功したらマッチした部分を消費し、失敗したらバックトラックを行う(失敗したパーサ試行前まで戻る)。

連接 a b
全て読み込むかまったく読み込まず死。

選択 a / b
aに失敗したらbを検査。どちらかが読み込めればOK

繰り返し a*
aの0回以上の繰り返し.

1回以上の繰り返し a+
aa*のシンタックスシュガー

先読みAnd &a
入力がaにマッチするか検査して、マッチしたら成功。ただし入力を消費しない。
失敗したら死

先読みNot !a
Andの否定

• • • • • • • • • • -

Packrat Parser
PEGの実装方法の一つ。パーサをメモ化して効率化

• • • • • • • • • • -

作りかけ。バグだらけ。
https://gist.github.com/3658681#file_packratparser.js

利用イメージ:

  p = new Packrat("aabc");
  p.sequence(function () { return p.many(toParser("a"))}, toParser("bc")); //"aabc"

  function AbcParser (input) { this.input = input; }
  
  AbcParser.prototype = new Packrat("");
  
  AbcParser.prototype.a = function () {var _this=this; return this.cacheDo("a", function () { return _this.chr("a"); }) };
  AbcParser.prototype.manyB = function () {var _this = this; return this.cacheDo("manyB", function () { return _this.many(function () {return _this.chr("b")}) })};
  AbcParser.prototype.c = function () {var _this = this; return this.cacheDo("c", function () {return _this.chr("c")})};
 
  var p = new AbcParser("abbbc");
  p.sequence(p.a, p.manyB, p.c); // "abbbc"

上のは勉強用に作ったけど、実用ならこれとかよさそう。 キャッシュ自動でやってくれそう.
https://github.com/doublec/jsparse