一般に、最適化された PEG パーサーは、最適化された LALR(1) または LL(k) パーサーよりも高速ではないという主張を見てきました。(もちろん、解析のパフォーマンスは特定の文法に依存します。)
PEGパーサーに特定の制限があるかどうかを知りたい.
特に、パーサー ジェネレーターに興味がありますが、特定のケースでパフォーマンスを向上させるために出力を微調整できると想定しています。また、パーサーは最適化されており、パフォーマンスを向上させるために必要な場合は、特定の文法を少し調整できると想定しています。
Packrat vs LALR parsing に関する良い答えが見つかりました。それからのいくつかの引用：
L(AL)R パーサーも線形時間パーサーです。したがって、理論的には、packrat パーサーも L(AL)R パーサーも「高速」ではありません。
もちろん、実際に重要なのは実装です。L(AL)R 状態遷移は、非常に少数のマシン命令 (「トークン コードをベクトルで検索し、次の状態とアクションを取得する」) で実行できるため、実際には非常に高速です。
観察: ほとんどの言語フロントエンドは、ほとんどの時間を「解析」に費やしていません。むしろ、彼らは字句解析に多くの時間を費やしています。それを最適化すると、パーサーの速度はそれほど重要ではなくなります。
PEGパーサーは (デフォルト) とは異なり、無制限の先読みを (packrat を介して平均して線形解析時間を維持しながら)LL(k)使用LR(k)できます。
最近 (2014-2015)は、平均して線形解析時間を維持しながら (アルゴリズムよりも効率的であると言われています)、ANTLR4任意の先読みを処理する拡張機能を作成しました(アルゴリズムよりも効率的であると言われています) 。デフォルトのアルゴリズム)。PEGpackratLRLR
packratパーサー (および 、の関連するパーサー) は必ずしも実用的ではありませんが、解析の理論的な境界を提供するため、比較を行うことができますLL。LR
ただし、無制限の先読みを使用して、文法/言語を線形時間で解析できることに注意してください (例:またはをpackrat使用antlr) 。LL(k)LR(k)