151

私は過去にさまざまなプロジェクト、通常は翻訳者(EDAアプリにストリーミングされたEDIFのサブセットなど)にlexとyacc(より一般的にはbison)を使用しました。さらに、数十年前にさかのぼるlex/yacc文法に基づくコードをサポートする必要がありました。ですから、私は専門家ではありませんが、ツールの使い方を知っています。

私は過去にさまざまなフォーラムでAntlrについて前向きなコメントを見てきましたが、何が欠けているのか興味があります。したがって、両方を使用したことがある場合は、Antlrで何が優れているかより高度であるかを教えてください。私の現在の制約は、私がC ++ショップで働いていることであり、出荷する製品にはJavaが含まれないため、結果として得られるパーサーはその規則に従う必要があります。

4

5 に答える 5

151

更新/警告:この回答は古くなっている可能性があります!


主な違いの1つは、ANTLRがLL(*)パーサーを生成するのに対し、YACCとBisonはどちらもLALRであるパー​​サーを生成することです。これは多くのアプリケーションにとって重要な違いであり、最も明白なのは演算子です。

expr ::= expr '+' expr
       | expr '-' expr
       | '(' expr ')'
       | NUM ;

ANTLRは、この文法をそのまま処理することはまったくできません。ANTLR(または他のLLパーサジェネレーター)を使用するには、この文法を左再帰ではないものに変換する必要があります。ただし、Bisonはこの形式の文法に問題はありません。'+'と'-'を左結合演算子として宣言する必要がありますが、これは左再帰には厳密には必要ありません。より良い例はディスパッチかもしれません:

expr ::= expr '.' ID '(' actuals ')' ;

actuals ::= actuals ',' expr | expr ;

expractualsルールの両方が左再帰であることに注意してください。これにより、複数のレジスタの必要性や不要なスピルが回避されるため、コード生成時にはるかに効率的なASTが生成されます(左寄りのツリーは折りたたむことができますが、右寄りのツリーは折りたたむことができません)。

個人的な趣味の観点から、LALR文法は構築とデバッグがはるかに簡単だと思います。欠点は、shift-reduceや(恐ろしい)reduce-reduceのようなやや不可解なエラーに対処しなければならないことです。これらは、パーサーを生成するときにBisonがキャッチするエラーであるため、エンドユーザーエクスペリエンスには影響しませんが、開発プロセスをもう少し面白くすることができます。ANTLRは、まさにこの理由から、一般的にYACC/Bisonよりも使いやすいと考えられています。

于 2008-10-17T16:50:10.670 に答える
125

YACC / BisonとANTLRの最も重要な違いは、これらのツールが処理できる文法のタイプです。YACC / BisonはLALR文法を処理し、ANTLRはLL文法を処理します。

多くの場合、LALR文法を長い間使用してきた人は、LL文法を使用するのがより困難であり、その逆も同様です。これは、文法やツールの操作が本質的に難しいという意味ではありません。どのツールを使用するのが簡単かは、ほとんどの場合、文法の種類に精通していることになります。

利点に関する限り、LALR文法がLL文法よりも優れている側面と、LL文法がLALR文法よりも優れている側面があります。

YACC / Bisonは、テーブル駆動型パーサーを生成します。これは、「処理ロジック」がパーサーのコードではなく、パーサープログラムのデータに含まれていることを意味します。見返りは、非常に複雑な言語のパーサーでさえ、コードのフットプリントが比較的小さいことです。これは、ハードウェアが非常に限られていた1960年代と1970年代にさらに重要でした。テーブル駆動型パーサジェネレータはこの時代にさかのぼり、当時は小さなコードフットプリントが主な要件でした。

ANTLRは再帰下降パーサーを生成します。これは、文法の各生成ルールがパーサーのコード内の関数によって表されるため、「処理ロジック」がパーサーのコードに含まれていることを意味します。見返りは、コードを読み取ることでパーサーが何をしているのかを理解しやすくなることです。また、再帰下降パーサーは通常、テーブル駆動パーサーよりも高速です。ただし、非常に複雑な言語の場合、コードのフットプリントは大きくなります。これは1960年代と1970年代の問題でした。当時、ハードウェアの制限により、たとえばPascalのような比較的小さな言語しかこの方法で実装されていませんでした。

ANTLRで生成されたパーサーは、通常、10.000行以上のコードの近くにあります。手書きの再帰下降パーサーは、同じ球場にあることがよくあります。WirthのOberonコンパイラは、コード生成を含めて約4000行のコードを含む最もコンパクトなコンパイラですが、Oberonは、約40のプロダクションルールしかない非常にコンパクトな言語です。

誰かがすでに指摘しているように、ANTLRの大きなプラスはANTLRworksと呼ばれるグラフィカルなIDEツールです。それは完全な文法と言語デザインの実験室です。入力時に文法規則を視覚化し、競合が見つかった場合は、競合とは何か、原因は何かをグラフィカルに表示します。左再帰などの競合を自動的にリファクタリングして解決することもできます。競合のない文法ができたら、ANTLRworksに言語の入力ファイルを解析させ、解析ツリーとASTを構築して、IDEにツリーをグラフィカルに表示させることができます。これは、多くの時間を節約できるため、非常に大きな利点です。コーディングを開始する前に、言語設計に概念上のエラーが見つかります。LALR文法用のそのようなツールは見つかりませんでした。そのようなツールはないようです。

パーサーを生成したくないが手作業でコーディングしたい人にとっても、ANTLRworksは言語の設計/プロトタイピングに最適なツールです。おそらく、そのようなツールとしては最高のものがあります。残念ながら、LALRパーサーを構築する場合は役に立ちません。単にANTLRworksを利用するためにLALRからLLに切り替えることは価値があるかもしれませんが、一部の人々にとっては、文法タイプを切り替えることは非常に苦痛な経験になる可能性があります。言い換えれば、YMMVです。

于 2009-12-14T11:41:17.783 に答える
38

ANTLR のいくつかの利点:

  • さまざまな言語でパーサーを出力できます - 生成されたパーサーの実行に Java は必要ありません。
  • 優れた GUI により、文法のデバッグが容易になります (たとえば、生成された AST を GUI で確認でき、追加のツールは必要ありません)。
  • 生成されたコードは実際には人間が判読できるものであり (これは ANTLR の目標の 1 つです)、LL パーサーを生成するという事実は、この点で確実に役立ちます。
  • 端子の定義もコンテキストフリーです ((f)lex の正規表現とは対照的に) - したがって、たとえば、適切に閉じられた括弧を含む端子の定義を許可します

私の.02$

于 2009-05-22T13:46:57.823 に答える
10

ANTRLのもう1つの利点は、ANTLRWORKSを使用できることですが他のジェネレーターにも同様のツールがある可能性があるため、これが厳密な利点であるとは言えません。

于 2008-12-02T01:19:31.077 に答える
10
  • Bison と Flex を使用すると、メモリ フットプリントが小さくなりますが、グラフィカル IDE はありません。
  • antlr はより多くのメモリを使用しますが、グラフィカル IDE である antlrworks を使用しています。

Bison/Flex のメモリ使用量は通常、1 メガバイト程度です。antlr とは対照的です。解析するファイル内のトークンごとに 512 バイトのメモリを使用すると仮定します。400 万トークンで、32 ビット システムの仮想メモリが不足しています。

解析したいファイルが大きい場合、antlr はメモリ不足になる可能性があるため、構成ファイルのみを解析したい場合は、実行可能なソリューションになります。そうではなく、大量のデータを含むファイルを解析したい場合は、Bison を試してください。

于 2012-05-31T10:09:59.997 に答える