多くの Web サイトでは、packrat パーサーは線形時間で入力を解析できると述べています。
したがって、一見すると、ツール yacc や bison によって構築された LALR パーサーよりも高速です。
理論的な入力ではなく一般的な入力 (プログラミング言語のソース ファイルなど) でテストした場合、packrat パーサーのパフォーマンスが LALR パーサーのパフォーマンスよりも優れているか劣っているかを知りたいと思いました。
2つのアプローチの主な違いを説明できる人はいますか?
ありがとう！
私は packrat の構文解析の専門家ではありませんが、ウィキペディアの式文法の構文解析で詳細を学ぶことができます。
私はそれを掘り下げていないので、packrat 解析の線形時間特性が正しいと仮定します。
L(AL)R パーサーも線形時間パーサーです。したがって、理論的には、packrat パーサーも L(AL)R パーサーも「高速」ではありません。
もちろん、実際に重要なのは実装です。L(AL)R 状態遷移は、非常に少数のマシン命令 (「トークン コードをベクトルで検索し、次の状態とアクションを取得する」) で実行できるため、実際には非常に高速です。L(AL)R 構文解析を機械語コードに「コンパイル」することで、非常に高速な LR 構文解析に関する 1986 年の Tom Pennello の論文で示されているように、非常に高速なパーサーを作成できます。(マシンは、彼が論文を書いたときよりも 20 年速くなりました!)。
packrat パーサーが結果を保存/キャッシュしている場合、それらは線形時間である可能性がありますが、一定のオーバーヘッドがかなり高くなると思います。実際には、L(AL)R パーサーの方がはるかに高速です。私が聞いたところによると、YACC と Bison の実装はかなり優れています。
答えが気になる場合は、基本的な技術論文をよく読んでください。本当に気にするなら、それぞれを実装して、オーバーヘッド定数をチェックしてください。私のお金は L(AL)R に強く依存しています。
観察: ほとんどの言語フロントエンドは、ほとんどの時間を「解析」に費やしていません。むしろ、彼らは字句解析に多くの時間を費やしています。それを最適化すれば (あなたのバイオはそう言っています)、パーサーの速度はそれほど重要ではなくなります。
(以前は LALR パーサー ジェネレーターとそれに対応するパーサーを作成していました。もうそれは行いません。代わりに、実際には線形時間であるが、任意のコンテキストフリー文法を処理するGLR パーサーを使用します。パフォーマンスはいくらか犠牲になりますが、[およびバイオを参照してください] 多くの問題なしに多くの言語用の数十のパーサーを構築します。)
私はオープンソースのLR（k）パーサジェネレータであるLRSTARの作者です。人々がそれに興味を示しているので、私はここ LRSTARで製品をオンラインに戻しました。
LALRパーサーとDFAレクサーの速度を長年研究してきました。Tom Pennelloの論文は非常に興味深いものですが、コンパイラー向けの実際のソリューションというよりは、学術的な演習です。ただし、必要なのがパターン認識機能だけである場合は、それが最適なソリューションになる可能性があります。
問題は、実際のコンパイラは通常、着信シンボルのシンボルテーブルルックアップ、エラーリカバリ、期待リスト（ステートメント完了情報）の提供、抽象構文ツリーの構築など、パターン認識以上のことを行う必要があることです。解析。
1989年に、LRSTARパーサーの解析速度を「yacc」と比較したところ、「yacc」パーサーの2倍の速度であることがわかりました。LRSTARパーサーは、論文「ポータブルコンパイラー用のパーサーテーブルの最適化」で公開されているアイデアを使用します。
字句解析（字句解析）の速度については、2009年に、「re2c」が「flex」によって生成される速度の約2倍の最速の字句を生成していることを発見しました。当時、私はLRSTARレクサージェネレーターセクションを書き直していて、「re2c」とほぼ同じ速度ではるかに小さいレクサーを作成する方法を見つけました。ただし、LRSTARが生成するテーブル駆動型レクサーは、ほぼ同じくらい高速で、コードのコンパイルがはるかに高速であるため、私は好みます。
ところで、LRSTARによって生成されたコンパイラフロントエンドは、毎秒2,400,000行以上の速度でソースコードを処理できます。LRSTARによって生成されたレクサーは、1秒あたり30,000,000トークンを処理できます。テスト用コンピューターは3.5GHzマシン（2010年以降）でした。
[2015/02/15] 1986 年の Tom Pennello の超高速 LR 解析に関する論文はこちら
http://www.genesishistory.org/content/ProfPapers/VF-LRParsing.pdf
パフォーマンスは、主に言語設計の問題です。言語ごとに、最適なアプローチ、テクノロジ、またはパーサー ジェネレーターが存在します。
もっとよく考えないと証明できませんが、セマンティクスがパーサーを駆動し、パーサーがレクサーをパフォーマンスの面で駆動するトップダウン降下パーサーに勝るものはないと思います。また、実装の中で最も汎用性が高く、保守が容易です。