☰

Antlr の利点 (lex/yacc/bison と比較した場合) [closed] 質問する

tag-icon • tag-icon c++ antlr yacc bison
Antlr の利点 (lex/yacc/bison と比較した場合) [closed] 質問する

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

これまでさまざまなフォーラムで Antlr に関する肯定的なコメントを見てきましたが、私が見逃している点が何なのか気になっています。両方を使用したことがある方は、Antlr のどちらが優れているか、またはより先進的であるかを教えてください。現在の制約は、私が C++ ショップで働いており、出荷する製品に Java が含まれないため、結果として得られるパーサーはそのルールに従う必要があるということです。

ベストアンサー1

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

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

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

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

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

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

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

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

おすすめ記事