私は LR(1) パーサーを作成していますが、さまざまな場所でパフォーマンスのボトルネックに遭遇しました。
パーサーのデータ構造の最適化を試みたいのですが、そのためには、C++ などの (おそらく複雑な) コンピューター言語に妥当な状態、規則、および終端記号の数を大まかに把握する必要があります。
私の推測では、複雑な言語の典型的な文法は次のようになります。
しかし、それらがどれほど正しいかは本当にわかりません。
各ルールは非終端記号→記号 記号 記号...の形式であると想定しているため、1 つfoo: (bar | baz)+の規則だけではなく、実際には 5 つの規則で構成されているように見える単一の複合「規則」であることに注意してください。
彼らは合理的ですか？そうでない場合、これらの数字はどこにありますか?
私が開発した DMS システムは、実稼働の IBM Enterprise COBOL フロントエンド文法を、粗末なラップトップで約 7 秒で処理します (そのラップトップで今測定したところ)。
文法には約 500 のターミナルと 2500 のプロダクションがあり、プロダクションあたり平均約 2.5 トークンです。私たちのプロダクションは、あなたが説明したとおりです (EBNF はありません。重要なほど十分に購入していません。そうです、私たちは DSL の大ファンです。人々が DSL に入れているオタクは、それだけの価値がない場合があります)。パーサー ジェネレーターは 3800 の状態を生成します。（これらの値も今測定したものです）。
DMS には、OpenMP だけでなく、GCC や MS の方言を処理するための多くの追加機能を備えた完全な C++11 文法があります。文法には 457 のターミナル、約 3000 のプロダクション、プロダクション平均あたり約 2.3 のトークンがあります。パーサー ジェネレーターは 5800 の状態を生成します。生成には多少時間がかかります: i7 では 11 秒。驚くかもしれませんが、レクサー (実際には複数のレクサー) を生成するのに数十秒かかります。C++11 には、予想以上に奇妙な字句変換があります。
ジェネレーターは、独自の実装の GLR ジェネレーターです。
生成時間を最適化するために多くのことを行いませんでした。おそらく10倍以上高速化できます。LR パーサー生成に関するほとんどの論文で提案されているような、洗練されたサイクル検出の最適化は行いません。その結果、テーブルの生成に時間がかかりますが、機能が失われることはありません。パーサー テーブルの生成時間を気にする以外にも、言語フロント エンドで行うべきことがたくさんあるため、最適化を行う十分な動機がありませんでした。
合理的に設計されていれば、データ構造が重要であるとは思えません。ルール、アイテム セット、または状態のサイズについてはあまり気にしません。動的配列を使用するだけで、それらは自分自身を処理します。先読みを密なビット ベクトルにパックします。
追加の背景データとして、 Tiago Alves と Joost Visser による SDF Grammars の計量化に関する論文がおそらく役立つでしょう。テクニカル レポート、DI-Research.PURe-05.05.01、Departamento de Informática、Universidade do Minho、2005 年 5 月。
パーサー ジェネレーターは、文法で苦労する場所ではありません。特定の実装に適した文法規則を取得しています。