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