Antlr の利点 (lex/yacc/bison と比較したもの) [終了]

StackOverflow https://stackoverflow.com/questions/212900

  •  03-07-2019
  •  | 
  •  

質問

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

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

役に立ちましたか？

解決

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

大きな違いの 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 ;

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

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

他のヒント

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

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

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

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

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

ANTLRで生成されたパーサーは通常、1万行以上のコードの近くにあります。手書きの再帰パーサーは、多くの場合同じ場所にあります。 WirthのOberonコンパイラはおそらく、コード生成を含む約4000行のコードを備えた最もコンパクトなコンパイラですが、Oberonは約40のプロダクションルールしか持たない非常にコンパクトな言語です。

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

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

ANTLRのいくつかの利点：

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

マイ.02 $

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

  • BisonとFlexはメモリフットプリントを小さくしますが、グラフィカルなIDEはありません。
  • antlrはより多くのメモリを使用しますが、グラフィカルなIDEであるantlrworksがあります。

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

解析したいファイルが大きい場合、antlrがメモリを使い果たす可能性があるため、設定ファイルを解析したいだけであれば、実行可能なソリューションになります。それ以外の場合、大量のデータを含むファイルを解析する場合は、Bisonを試してください。

ライセンス： CC-BY-SA と 帰属
所属していません StackOverflow
scroll top