JavaScriptでパーサーを書く方法

...すなわち、単純な構造から複雑な構造を構築することにより、それほど複雑ではない構造用のLL構文解析を書く方法。 時折、XMLに似た構造や何らかのデータURLなど、複雑でないものを解析する必要があります。通常は、読みづらい読みにくいコードのシートか、さらに複雑でトリッキーな解析ライブラリへの依存関係のいずれかです。 ここでは、いくつかの有名なアイデア（そのうちのいくつかはHabréで出会ったもの）を組み合わせて、非常に複雑なパーサーを、ごく少数のコード行を維持しながら、できるだけシンプルかつ簡潔に記述する方法を示します。 たとえば、XMLに似た構造パーサーを作成します。 はい、注意を引くためにここに写真を挿入しません。 記事には写真がまったくないので、読みにくくなります。

主なアイデア

入力テキストの各部分が個別の関数（「パターン」と呼びましょう）によって解析され、これらの関数を組み合わせることで、より複雑なテキストを解析できるより複雑な関数を取得できるという事実にあります。 したがって、パターンとは、解析を実行するexecメソッドを持つオブジェクトです。 この関数は、何からどこで解析するかを示し、解析された場所と解析が終了した場所を返します。

var digit = { exec: function (str, pos) { var chr = str.charAt(pos); if (chr >= "0" && chr <= "9") return { res: +chr, end: pos + 1}; } };
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

現在、数字は解析数字パターンであり、次のように使用できます。

 assert.deepEqual(digit.exec("5", 0), { res: 5, end: 1 }); assert.deepEqual(digit.exec("Q", 0), void 0);
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

なぜそのようなインターフェースなのか？ JSには、非常によく似たインターフェースを持つ組み込みのRegExpクラスがあるためです。 便宜上、これらのパターンをインスタンスとするPatternクラス（RegExpの類似物として見てください）を導入します。

 function Pattern(exec) { this.exec = exec; }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

次に、多少複雑なパーサーで役立ついくつかの単純なパターンを紹介します。

シンプルなパターン

最も単純なパターンはtxtです-固定された、あらかじめ決められたテキスト行を解析します：

 function txt(text) { return new Pattern(function (str, pos) { if (str.substr(pos, text.length) == text) return { res: text, end: pos + text.length }; }); }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

次のように適用されます。

 assert.deepEqual(txt("abc").exec("abc", 0), { res: "abc", end: 3 }); assert.deepEqual(txt("abc").exec("def", 0), void 0);
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

JSにデフォルトのコンストラクターがある場合（C ++など）、より複雑なパターンを構築するコンテキストで、txt（「abc」）エントリを「abc」に短縮できます。



次に、正規表現の類似物を紹介し、rgxと呼びます。

 function rgx(regexp) { return new Pattern(function (str, pos) { var m = regexp.exec(str.slice(pos)); if (m && m.index === 0) return { res: m[0], end: pos + m[0].length }; }); }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

次のように適用します。

 assert.deepEqual(rgx(/\d+/).exec("123", 0), { res: "123", end: 3 }); assert.deepEqual(rgx(/\d+/).exec("abc", 0), void 0);
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

繰り返しますが、JSにデフォルトのコンストラクターがある場合、rgx（/ abc /）エントリは/ abc /に短縮できます。

組み合わせパターン

次に、既存のパターンを組み合わせた複数のパターンを入力する必要があります。 これらの「コンビネーター」の中で最も単純なものはoptです。これにより、任意のパターンがオプションになります。 元のパターンpがテキストを解析できない場合、同じテキストのopt（p）はすべてが解析され、解析結果のみが空であると言います：

 function opt(pattern) { return new Pattern(function (str, pos) { return pattern.exec(str, pos) || { res: void 0, end: pos }; }); }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

使用例：

 assert.deepEqual(opt(txt("abc")).exec("abc"), { res: "abc", end: 3 }); assert.deepEqual(opt(txt("abc")).exec("123"), { res: void 0, end: 0 });
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

JSで演算子のオーバーロードとデフォルトのコンストラクターが可能な場合、レコードopt（p）をp ||に減らすことができます。 void 0（これは、optの実装方法から明らかにわかります）。



次に複雑なコンビネータはexcです。最初のパターンを解析でき、2番目のパターンを解析できないもののみを解析します。

 function exc(pattern, except) { return new Pattern(function (str, pos) { return !except.exec(str, pos) && pattern.exec(str, pos); }); }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

W（p）がpパターン解析するテキストのセットである場合、W（exc（p、q））= W（p）\ W（q）。 これは、たとえば、文字Hを除くすべての大文字を解析する必要がある場合に便利です。

 var p = exc(rgx(/[AZ]/), txt("H")); assert.deepEqual(p.exec("R", 0), { res: "R", end: 1 }); assert.deepEqual(p.exec("H", 0), void 0);
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

JSに演算子のオーバーロードがある場合、exc（p1、p2）をp1-p2またはto！P2 && p1に減らすことができます（ただし、このため、組み合わせパターンall /を導入する必要があり、これは&&演算子として機能します） 。



次に、コンビネータパターンがあります。いくつかのパターンを取り、これらのパターンの最初のパターンを解析する新しいパターンを作成します。 W（any（p1、p2、p3、...））= W（p1）v W（p2）v W（p3）v ...

 function any(...patterns) { return new Pattern(function (str, pos) { for (var r, i = 0; i < patterns.length; i++) if (r = patterns[i].exec(str, pos)) return r; }); }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

[] .slice.call（arguments、0）のような不器用なコードを避けるために、...パターン（調和：rest_parameters）構成を使用しました。 anyの使用例：

 var p = any(txt("abc"), txt("def")); assert.deepEqual(p.exec("abc", 0), { res: "abc", end: 3 }); assert.deepEqual(p.exec("def", 0), { res: "def", end: 3 }); assert.deepEqual(p.exec("ABC", 0), void 0);
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

JSに演算子のオーバーロードがある場合、任意の（p1、p2）をp1 ||に減らすことができます。 p2。



次のコンビネーターパターンはseqです-パターンのシーケンスによって与えられたテキストを順次解析し、結果の配列を生成します。

 function seq(...patterns) { return new Pattern(function (str, pos) { var i, r, end = pos, res = []; for (i = 0; i < patterns.length; i++) { r = patterns[i].exec(str, end); if (!r) return; res.push(r.res); end = r.end; } return { res: res, end: end }; }); }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

次のように適用されます。

 var p = seq(txt("abc"), txt("def")); assert.deepEqual(p.exec("abcdef"), { res: ["abc", "def"], end: 6 }); assert.deepEqual(p.exec("abcde7"), void 0);
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

JSに演算子のオーバーロードがある場合、seq（p1、p2）をp1、p2に減らすことができます（コンマ演算子がオーバーロードされます）。



そして最後に、repコンビネーターパターン-既知のパターンをテキストに何度も適用し、結果の配列を生成します。 原則として、これは、たとえばカンマで区切られた同じタイプの特定の構造の解析に使用されるため、repは2つの引数を取ります。結果が興味深いメインパターンと、結果が破棄される分離パターンです。

 function rep(pattern, separator) { var separated = !separator ? pattern : seq(separator, pattern).then(r => r[1]); return new Pattern(function (str, pos) { var res = [], end = pos, r = pattern.exec(str, end); while (r && r.end > end) { res.push(r.res); end = r.end; r = separated.exec(str, end); } return { res: res, end: end }; }); }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

許容される繰り返し数を制御するパラメーターminおよびmaxをさらに追加できます。 ここでは、関数（z）{return z [1]}を記述しないために、矢印関数r => r [1]（調和：arrow_functions）を使用しました。 パターン＃thenを使用してrepがseqに減少することに注意してください（Promise＃thenから取得したアイデア）：

 function Pattern(exec) { ... this.then = function (transform) { return new Pattern(function (str, pos) { var r = exec(str, pos); return r && { res: transform(r.res), end: r.end }; }); }; }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

この方法では、最初の結果に任意の変換を適用することにより、別のパターンから推測できます。 ところで、Haskellの専門家は、このパターン＃がパターンからモナドを作ると言うことは可能ですか？



さて、担当者は次のように適用されます。

 var p = rep(rgx(/\d+/), txt(",")); assert.deepEqual(p.exec("1,23,456", 0), { res: ["1", "23", "456"], end: 8 }); assert.deepEqual(p.exec("123ABC", 0), { res: ["123"], end: 3 }); assert.deepEqual(p.exec("ABC", 0), void 0);
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

担当者のオペレーターのオーバーロードとの明確な類推は私には発生しません。



結果は、これらのrep / seq / anyのすべてについて約70行です。 これでコンビネーターパターンのリストが完成し、XMLに似たテキストを認識するパターンの実際の構築に進むことができます。

XMLのようなテキストのパーサー

このようなXMLのようなテキストに制限します。

 <?xml version="1.0" encoding="utf-8"?> <book title="Book 1"> <chapter title="Chapter 1"> <paragraph>123</paragraph> <paragraph>456</paragraph> </chapter> <chapter title="Chapter 2"> <paragraph>123</paragraph> <paragraph>456</paragraph> <paragraph>789</paragraph> </chapter> <chapter title="Chapter 3"> ... </chapter> </book>
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

まず、name = "value"という形式の名前付き属性を認識するパターンを記述します。これは明らかにXMLでよく見られます。

 var name = rgx(/[az]+/i).then(s => s.toLowerCase()); var char = rgx(/[^"&]/i); var quoted = seq(txt('"'), rep(char), txt('"')).then(r => r[1].join('')); var attr = seq(name, txt('='), quoted).then(r => ({ name: r[0], value: r[2] }));
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

ここで、attrは名前付き属性を文字列形式の値で解析し、quoted-引用符で文字列を解析します。char-文字列内の1文字を解析します（これを別のパターンとして記述する必要がありますか？ ）、ただしnameは属性名を解析します（大文字と小文字の両方を解析しますが、すべての文字が小さい解析済みの名前を返します）。 attrアプリケーションは次のようになります。

 assert.deepEqual( attr.exec('title="Chapter 1"', 0), { res: { name: "title", value: "Chapter 1" }, end: 17 });
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

次に、<？Xml ...？>のようなヘッダーを解析できるパターンを作成します。

 var wsp = rgx(/\s+/); var attrs = rep(attr, wsp).then(r => { var m = {}; r.forEach(a => (m[a.name] = a.value)); return m; }); var header = seq(txt('<?xml'), wsp, attrs, txt('?>')).then(r => r[2]);
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

ここで、wspは1つ以上のスペースを解析し、attrsは1つ以上の名前付き属性を解析し、解析したものを辞書の形式で返します（repは名前と値のペアの配列を返しますが、辞書はより便利なので、配列は内部の辞書に変換されます）、ヘッダーはヘッダーを解析し、同じディクショナリの形式でタイトル属性のみを返します。

 assert.deepEqual( header.exec('<?xml version="1.0" encoding="utf-8"?>', 0), { res: { version: "1.0", encoding: "utf-8" }, end: ... });
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

次に、<node ...> ...の形式の構文解析に移りましょう。

 var text = rep(char).then(r => r.join('')); var subnode = new Pattern((str, pos) => node.exec(str, pos)); var node = seq( txt('<'), name, wsp, attrs, txt('>'), rep(any(text, subnode), opt(wsp)), txt('</'), name, txt('>')) .then(r => ({ name: r[1], attrs: r[3], nodes: r[5] }));
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

ここでは、テキストはノード内のテキストを解析し、xmlエンティティを認識するために学習できる文字パターンを使用し、サブノードは内部ノード（実際にはサブノード=ノード）を解析し、ノードは属性と内部ノードでノードを解析します。 なぜこのようなサブノードのトリッキーな定義ですか？ nodeの定義でn​​odeを直接参照すると（node = seq（...、node、...）など）、nodeの定義時にこの変数はまだ空であることがわかります。 サブノードのトリックは、この循環依存を排除​​します。



ヘッダーを持つファイル全体を認識するパターンを決定することは残っています。

 var xml = seq(header, node).then(r => ({ root: r[1], attrs: r[0] }));
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

したがって、アプリケーションは次のとおりです。

 assert.deepEqual( xml.exec(src), { attrs: { version: '1.0', encoding: 'utf-8' }, root: { name: 'book', attrs: { title: 'Book 1' }, nodes: [ { name: 'chapter', attrs: { title: 'Chapter 1' }, nodes: [...] }, ... ] } });
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

ここでは、1つの引数でパターン＃execを呼び出します。これの意味は、最初から文字列を解析し、最後まで解析されることを確認することですが、最後まで解析されるため、その場所へのポインタなしで解析されたものだけを返すだけで十分ですパーサーが停止した場所（これが行の終わりであることは既に知っています）：

 function Pattern(name, exec) { ... this.exec = function (str, pos) { var r = exec(str, pos || 0); return pos >= 0 ? r : !r ? null : r.end != str.length ? null : r.res; }; }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

実際には、パーサー全体が20行になっています（rep、seq、anyなどを実装する70行について忘れないでください）。

 var name = rgx(/[az]+/i).then(s => s.toLowerCase()); var char = rgx(/[^"&]/i); var quoted = seq(txt('"'), rep(char), txt('"')).then(r => r[1].join('')); var attr = seq(name, txt('='), quoted).then(r => ({ name: r[0], value: r[2] })); var wsp = rgx(/\s+/); var attrs = rep(attr, wsp).then(r => { var m = {}; r.forEach(a => (m[a.name] = a.value)); return m; }); var header = seq(txt('<?xml'), wsp, attrs, txt('?>')).then(r => r[2]); var text = rep(char).then(r => r.join('')); var subnode = new Pattern((str, pos) => node.exec(str, pos)); var node = seq( txt('<'), name, wsp, attrs, txt('>'), rep(any(text, subnode), opt(wsp)), txt('</'), name, txt('>')) .then(r => ({ name: r[1], attrs: r[3], nodes: r[5] })); var xml = seq(header, node).then(r => ({ root: r[1], attrs: r[0] }));
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

JS（またはC ++）で演算子をオーバーロードすると、次のようになります。

 var name = rgx(/[az]+/i).then(s => s.toLowerCase()); var char = rgx(/[^"&]/i); var quoted = ('"' + rep(char) + '"').then(r => r[1].join('')); var attr = (name + '=' + quoted).then(r => ({ name: r[0], value: r[2] })); var wsp = rgx(/\s+/); var attrs = rep(attr, wsp).then(r => { var m = {}; r.forEach(a => (m[a.name] = a.value)); return m; }); var header = ('<?xml' + wsp + attrs + '?>').then(r => r[2]); var text = rep(char).then(r => r.join('')); var subnode = new Pattern((str, pos) => node.exec(str, pos)); var node = ('<' + name + wsp + attrs + '>' + rep(text | subnode) + (wsp | null) + '</' + name + '>') .then(r => ({ name: r[1], attrs: r[3], nodes: r[5] })); var xml = (header + node).then(r => ({ root: r[1], attrs: r[0] }));
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

ここでの各変数は1つのABNFルールに厳密に対応するため、RFCの記述（およびそこでABNFが気に入っている）に従って何かを解析する必要がある場合、それらのルールを転送することは機械的な問題です。 さらに、ABNFルール自体（およびEBNFおよびPEG）は厳密に形式的であるため、これらのルールのパーサーを記述し、rep、seqなどを呼び出す代わりに、次のように記述できます。

 var dataurl = new ABNF('"data:" mime ";" attrs, "," data', { mime: /[az]+\/[az]+/i, attrs: ..., data: /.*/ }).then(r => ({ mime: r[1], attrs: r[3], data: r[5] }));
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

そしていつものように適用します：

 assert.deepEqual( dataurl.exec('data:text/plain;charset="utf-8",how+are+you%3f'), { mime: "text/plain", attrs: { charset: "utf-8" }, data: "how are you?" });
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

さらにいくつかのブナ

解析に失敗した場合、パターン＃execがnull /未定義を返すのはなぜですか？ 例外をスローしないのはなぜですか？ このように例外を使用すると、パーサーは20秒ごとに遅くなります。 例外は例外的な場合に適しています。



説明した方法を使用すると、すべての目的に適さないLLパーサーを作成できます。 たとえば、次の形式のXMLを解析する必要がある場合

 <book attr1="..." attr2="..."    ???
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

それが立っている場所で??? /およびsimple>の両方になることがあります。 LLパーサーがこれをすべて<book ...>として解析しようとしたが、その場所にある場合??? >>であることが判明した場合、パーサーは、これが<book ... />であるという仮定の下で、解析とやり直しに非常に時間がかかったすべてを破棄します。 LRパーサーにはこの欠点はありませんが、作成するのは困難です。



また、LLパーサーは、優先順位が異なる演算子などがあるさまざまな構文/数式の解析にはあまり適していません。 LLパーサーはもちろん作成できますが、やや混乱し、動作が遅くなります。 LRパーサーはそれ自体で混乱しますが、高速です。 したがって、このような式は、いわゆる Crockford がよく説明した Prattのアルゴリズム（このリンクが紫色の場合は、おそらく私よりもパーサーをよく理解しており、おそらくこれをすべて読むことに退屈しているでしょう）。



誰かが役に立つといいな。 かつて、さまざまな不器用さのパーサーを作成しましたが、上記の方法は私にとって発見でした。