C ++で多くの小さなテキストを解析するための最良のパーサジェネレータ?
-
27-10-2019 - |
質問
パフォーマンス上の理由から、C#ライブラリをC ++に移植しています。通常の操作では、このライブラリは、とりわけ、平均長が150文字未満の約15万の数式(Excelの数式を考えてください)を解析する必要があります。
C#バージョンでは、GOLDパーサーを使用して解析コードを生成しました。 1秒以内に150,000の式すべてを解析できます。
言語の拡張を考えていたので、C ++への移行はANTLRに変更する良いチャンスかもしれないと思いました。 (単純な)文法をANTLRに移植し、そこからCコードを生成しました。 150,000の式の解析には、12秒以上かかります。これは、式ごとに、新しいANTL3_INPUT_STREAM、トークンストリーム、レクサー、パーサーを作成する必要があるためです。少なくともバージョン3.4では、それらを再利用する方法はありません。
誰かが代わりに何を使用するかをアドバイスしてくれるとありがたいです-C ++またはCコードの生成はC#の種類よりもはるかに複雑に見えますが、GOLDはもちろんオプションです。私の文法はLALRとLL(1)と互換性があります。最も懸念されるのは、小さな入力でのパフォーマンスの解析です。
解決
boost :: spiritを試してみます。多くの場合、非常に高速です(整数のような単純なものを解析する場合でも、C関数atoi http://alexott.blogspot.com/2010/01/boostspirit2-vs-atoi.html )
すばらしい点があります。ヘッダーのみなので、依存関係地獄、リベラルなライセンスです。
ただし、学習曲線は難しいことに注意してください。これは最新のC ++(ポインターはありませんが、テンプレートが多く、コンパイルエラーが非常にイライラします)なので、CまたはC#を使用しているため、あまり快適ではない可能性があります。
他のヒント
解析する文法が単純な場合は、パーサーを手動で記述するだけです。
ほとんどのパーサジェネレータは、動作中のパーサを簡単に作成できるように設計されているため、結果として実行時間が長くなることがよくあります。
解析で見た中で最高のパフォーマンスは、メタテンプレートプログラミングを使用してC ++で文法を表現するBoost.Spirit.Qiから得られました。しかし、それは気弱な人向けではありません。
これは十分に分離する必要があり、パーサーを含むファイルのコンパイル時間は数秒に増加します(したがって、そこにできるだけ少ないことを確認してください)。
expr
の代わりに、文法でsequence-of-expr
を認識させます。
編集:
(バイソン構文)の代わりに: ジェネラコディセタグプレ
持っている: ジェネラコディセタグプレ
私は多くのパーサーを作成しましたが、手書きの再帰下降がその方法です。それらは書くのが簡単で、ほとんど最適です。
とはいえ、スピードが求められているのであれば、何を書いても、スピードを上げる余地は十分にあります。 これらはあなたを驚かせる可能性のある方法になります。なぜなら、あなたが考えられることは何でも、あなたはすでに行っているはずだからです。
こちらが スライドセット です。方法。