An Empirical Comparison of General Context-Free Parsers
本論文は、Rustで実装された6種類の汎用文脈自由解析アルゴリズムの初の統一的なベンチマークを提示し、GLRファミリーが、決定論的LR(1)パーサと比較してわずか3倍の中央値パフォーマンスオーバーヘッドのみで完全な言語表現力をサポートすることから、ソフトウェアエンジニアリングツールにおける実用的なデフォルトの選択肢であることを実証する。
原論文は CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/) でライセンスされています。 これは以下の論文のAI生成解説です。著者が執筆または承認したものではありません。技術的な正確性については原論文を参照してください。 免責事項の全文を読む
あなたは、外国語（ソースコード）をコンピュータが理解できる形式に変換しようとしている翻訳者だと想像してください。このプロセスは**パース（解析）**と呼ばれます。
何十年もの間、ソフトウェアエンジニアが使用してきた翻訳者は、厳格でルールに縛られたロボットのようでした。彼らは非常に高速でしたが、同時に非常に潔癖でした。もしあなたが与えた言語に、わずかな曖昧さや複雑な文章構造が含まれていれば、ロボットは作業を拒否しました。ロボットを喜ばせるために、エンジニアは言語を「ハック」することに何時間も費やさなければなりませんでした。文章を書き換え、自然な構造を取り除き、そのロボットの狭いルールに適合するように文法を歪めるのです。それは、丸い杭しか持っていないからといって、無理やり四角い穴に丸い杭を押し込むようなものでした。
このため、多くのエンジニアはこれらの形式的なロボットを使うことを諦め、自分たちで手作りの翻訳者を作り始めました。これらの手作りの翻訳者は、しばしばバグが多く、メンテナンスが難しく、セキュリティ面でも脆弱です。
大きな疑問
長年、「ジェネラル（汎用）」パーサー（あらゆる言語構造を扱うことができ、ハックを必要としない翻訳者）は、実用的なレベルでは遅すぎて役に立たないという信念がありました。それらは、速くて厳格なロボットと比較して、遅くて不器用な巨人のようなものだと考えられていたのです。
この論文の著者たちは、この論争に決着をつけることにしました。彼らは、これら6種類の異なるタイプの「ジェネラル」パーサーを、古い「厳格な」ロボットと対決させるための「レーストラック」を構築しました。彼らは、すべてのレーサーが同じ靴を履き、同じトラックを走り、同じストップウォッチを使用するようにしました（すべてのコードを同じ言語であるRustで書き、同じツールを使用しました）。
レーサーたち
彼らは6つの異なる戦略をテストしました：
- マトリックス・ムーバー（CYK & Valiant）： 巨大なグリッドを埋めることでパズルを解こうとするもの。
- トップダウン・エクスプローラー（Earley & GLL）： 上から構造を推測しようとし、一度に多くの経路を探索するもの。
- ボトムアップ・ビルダー（RNGLR & BRNGLR）： 下から構造を構築し、衝突が発生した場合は複数の経路に注意を分散させて対処するもの。
- 厳格なロボット（LL(1) & LR(1)）： 旧世代の、速いが潔癖なパーサー。
結果：驚きの勝者
- 「不器用な巨人」（CYK & Valiot）： これらはひどいものでした。あまりにも遅すぎて、現実世界のタスクには実質的に使い物になりませんでした。それは、街の中を戦車で走ろうとするようなものです。ここでは全く機能しません。
- 「トップダウン・エクスプローラー」（Earley & GLL）：
- Earley は、この中で最も遅かった。
- GLL は、いくつかの言語では速かったものの、他の言語では非常に遅くなり、メモリを大量に消費しました。それは、直線コースでは優秀だが、曲がりくねったコースでは自分の足に躓いてしまうランナーのようなものでした。
- 「ボトムアップ・ビルダー」（RNGLR & BRNGLR）： これらがチャンピオンでした。
- 彼らはすべての「ジェネラル」パーサーの中で最も高速でした。
- メモリ効率が非常に高く、厳格なロボットとほぼ同等のメモリ使用量でした。
- 大発見： 言語が厳格なロボットにとって十分に単純な場合、これらの新しい「ジェネラル」パーサーの速度は、厳格なロボットよりわずか3倍遅いだけでした。著者たちは、どんな言語でもハックなしで扱える能力を得るために、3倍の減速は支払う価値のある極めて小さな代償であると主張しています。
「文法ハック」の罠
この論文は、厳格なロボットに適合させるために言語を「ハック」しようとすると何が起こるかも調査しました。
- 速度： はい、厳格なロボットに合うように言語をハックすれば、4倍から7倍速くなります。
- 落とし穴： しかし、言語をハックすることは、新しい「ジェネラル」パーサーにとって最悪のシナリオを生み出すことにもなります。それは、お気に入りのプレイヤーを勝たせるためにゲームのルールを変えるようなものですが、その結果、ゲーム自体が他の全員にとってプレイ不可能なものになってしまうのです。
- 判定： 著者たちは、わずかなスピードを絞り出すために言語をハックすべきではないと述べています。「ジェネラル」パーサーはほとんどのケースで十分に速く、言語をハックすることは可読性やメンテナンス性を低下させます。
シンプルな教訓
長い間、ソフトウェアエンジニアは、速度（厳格でハックされたパーサーを使用する）か、柔軟性（遅いジェネラル・パーサーを使用する）かのどちらかを選ばなければならないと考えてきました。
この論文は、その選択肢は幻想であることを証明しています。新しい「ジェネラル」パーサー（特に GLR ファミリー）は、デフォルトの選択肢となるほど十分に高速です。それらはユニバーサル・アダプターのようなものです。あらゆるプラグに適合し、専用のアダプターよりも少し重いかもしれませんが、デバイスごとに異なるアダプターを買わなくて済むようにしてくれます。
要するに： 古くて潔癖なパーサーに合わせるために、言語をハックするのはやめましょう。新しい、柔軟な「ジェネラル」パーサーを使ってください。それらは高速で、メモリ使用量も少なく、言語を自然な形で記述することを可能にします。
短く言えば： 「ジェネラル」パーサーは速く、メモリ消費も少なく、言語を本来の自然な姿で記述できるようにしてくれるのです。
自分の分野の論文に埋もれていませんか？
研究キーワードに一致する最新の論文のダイジェストを毎日受け取りましょう——技術要約付き、あなたの言語で。