7

大規模な商用アプリでカスタム テキスト ファイル形式を読み取るために使用できる優れたパーサー ジェネレーターを探しています。現在、この特定のファイル形式は手作りの再帰パーサーで読み取られますが、その方法が管理不能になるまで、形式は成長し、複雑化しています。

究極の解決策は、この形式に適した文法を構築し、yacc のような実際のパーサー ジェネレーターを使用してそれを読み取ることのようですが、どのジェネレーターを使用するか、または問題を解決する価値があるかどうかを判断するのに苦労しています。まったく。私はANTLRとSpiritを見てきましたが、私たちのプロジェクトには以前の回答を超えた特定の制約があり、それらが私たちに適しているかどうか疑問に思います. 特に、次のものが必要です。

  • MSVC で C または C++ コードを生成するパーサー。ANTLR 3 は C++ をサポートしていません。ストレートCを生成すると主張していますが、実際に動作させるためのドキュメントはちょっと混乱しています。
  • メモリ使用量が大幅に制限されています。私たちのアプリではメモリが非常に重要であり、わずかなリークでも致命的です。カスタム malloc() を使用するには、パーサーのメモリ アロケータをオーバーライドできるようにする必要があります。または、少なくとも、すべてのメモリを取得する連続したプールをパーサーに与える必要があります (後で一括して割り当てを解除できます)。パーサーの実行可能ファイル自体に約 200kb を割くことができますが、解析で割り当てた動的ヒープは後で解放する必要があります。
  • 良い成果。これはそれほど重要ではありませんが、3 GHz プロセッサで 1 秒以内に 100 KB のテキストを解析できるはずです。
  • GPL フリーである必要があります。GNU コードは使用できません。

ANTLRworks の IDE とデバッグ ツールは気に入っていますが、その C ターゲットを実際にアプリで動作させるのは大変な作業になりそうです。その話に着手する前に、ANTLR はこの仕事に適したツールですか?

問題のテキスト形式は次のようになります。

attribute "FluxCapacitance"  real constant

asset DeLorean
{
    //comment foo bar baz
    model "delorean.mdl"
    animation "gullwing.anm"
    references "Marty"
    loadonce
}

template TimeMachine
{
    attribute FluxCapacitance 10      
    asset DeLorean
}
4

7 に答える 7

4

アプリケーションでブーストスピリットをうまく使用しています。Boost ライセンスは非常に自由度の高いライセンスなので、商用アプリケーションで使用しても問題ありません。

ドキュメントからの引用：

Spirit は、テンプレートのメタプログラミング手法を使用して実装された、オブジェクト指向の再帰降下パーサー ジェネレーター フレームワークです。式テンプレートを使用すると、Extended Backus-Normal Form (EBNF) の構文を C++ で完全に近似することができます。Spirit フレームワークを使用すると、ターゲット文法を C++ のみで記述できます。インライン EBNF 文法仕様は、他の C++ コードと自由に組み合わせることができ、C++ テンプレートの生成力のおかげで、すぐに実行できます。振り返ってみると、従来のコンパイラー コンパイラーまたはパーサー ジェネレーターは、ソース EBNF コードから C または C++ コードへの追加の変換ステップを実行する必要があります。

于 2009-04-21T00:49:54.707 に答える
4

ANTLR 3 は C++ をサポートしていません。ストレートCを生成すると主張していますが、実際に動作させるためのドキュメントはちょっと混乱しています。

C を生成し、さらに Visual Studio および C++ で動作します。私は以前にそれを行い、stdcall で動作するようにパッチを提出したので、これを知っています。

私たちのアプリではメモリが非常に重要であり、わずかなリークでも致命的です。カスタム malloc() を使用するには、パーサーのメモリ アロケータをオーバーライドできるようにする必要があります。または、少なくとも、すべてのメモリを引き出す連続したプールをパーサーに与える必要があります (そして、後で一括して割り当てを解除できます)。パーサーの実行可能ファイル自体に約 200kb を割くことができますが、解析で割り当てた動的ヒープは後で解放する必要があります。

前回チェックしたantlr3cランタイムにはメモリリークがなく、説明したメモリプールパラダイムを使用しています。ただし、作成者が変更を拒否している API の欠点が 1 つあります。それは、ノードの文字列を要求すると、パーサー全体を解放するまで毎回新しいコピーが作成されることです。

カスタム malloc の使いやすさについてはコメントしませんが、プロジェクト全体で使用する malloc 関数を定義するマクロがあります。

実行可能サイズに関しては、私のコンパイルのサイズは小さなインタープリターを含めて約 100 kb でした。

あなたへの私の提案は、ANTLR の学習を続けることです。なぜなら、それはまだあなたの要件に適合しており、それが機能し始める前におそらくもう少し時間を犠牲にする必要があるからです。

于 2009-04-21T07:09:11.660 に答える
2

手動でコーディングされた再帰降下パーサーは、実際には非常に高速であり、非常にコンパクトにすることができます。唯一の欠点は、本質的に LL(1) 文法のコーディングに注意する必要があることです。[ANTLR を使用する場合、同様の制限があるため、これはそれほど大きな問題ではありません]。

このようなパーサーは、単純な再帰 C コードとしてハンドコーディングできます。(完全な詳細については、この回答を参照してください: Is there an alternative for flex/bison that is available on 8-bit embedded systems? )

スペースが非常に限られている場合は、解析用の仮想マシンを定義し、それを実行する小さな C インタープリターを構築できます。私は 70 年代初頭に、この方法で BASIC インタープリターを構築していました。

これらのパーサーを実際に機能させる非常に単純な規則に従うことで、解析機構によるメモリ リークが発生しないことを保証できます。(もちろん、パーサーが関心のある項目を認識する任意のアクションをパーサーにアタッチすることもできます。これらのアクションがリークするかどうかは、パーサーではなく、一般的なプログラミングの問題です)。

このアイデアは、Val Schorre によるメタコンパイラに関する 1964 年の論文から生まれました。この論文は、10 ページで完全なコンパイラを構築する方法を示しています。Shore の小さなパーサー ジェネレーターは、かなり優れた再帰降下パーサーを生成します。この論文について説明し、そのようなパーサーを構築する方法を正確に示しているサイトは、 http: //www.bayfronttechnologies.com/metaii.html にあります。

複雑な文法を手作業でコーディングすることに疲れた後、70 年代後半に、私は Schorre の方法を使用して Basic コンパイラを構築しました。

于 2009-06-27T02:15:00.677 に答える
2

ANTLR 用に投稿した新しい C++ ターゲットをご覧ください。また、パーサーのメモリ使用量を制限するオプションもあり、必要なすべてのメモリ管理ルーチンを特性の形式で公開します。

http://www.antlr.org/wiki/pages/viewpage.action?pageId=29130826

于 2012-03-01T01:17:42.150 に答える
1

では、flex/yacc を使用しないのはなぜですか? Cコードを生成し、MSVCから実行でき、効率を考慮して開発され、mallocをオーバーライドできます（yymallocの場合はgoogle）。それら自体はGPLですが、結果のコード（プロジェクトで使用するコード）はAFAIKではありません。

または、手作りのパーサーを使用します。

于 2009-04-21T06:58:47.923 に答える
0

ANTLR パーサー、および実際には、LALR などで構築されたパーサーはすべて、大きくなる傾向があります。これには実際の文法がありますか？手書きの再帰降下パーサーで最も簡単に解析できるように見えますが、あまりサンプルではありません。

おっと、ANTLRは明らかに再帰降下を生成するため、私の間違いです。それでも、大きなパーサーを生成する ANTLR には問題がありました。

于 2009-04-21T00:19:39.943 に答える