再帰下降パーサーは、説明が最も簡単であるだけでなく、設計と保守も最も簡単なようです。それらはLALR（1）文法に限定されず、コード自体は単なる人間によって理解することができます。対照的に、ボトムアップパーサーには認識できる文法に制限があり、特別なツールで生成する必要があります（それらを駆動するテーブルは手作業で生成することがほぼ不可能であるため）。
それでは、なぜボトムアップ（つまりシフトリデュース）解析がトップダウン（つまり再帰下降）解析よりも一般的であるのでしょうか？
14932 次
6 に答える
20
強力なパーサジェネレータを選択すると、固有のプロパティを気にせずに文法をコーディングできます。（LA）LRは、左再帰について心配する必要がなく、頭痛が1つ少ないことを意味します。GLRは、ローカルのあいまいさや先読みについて心配する必要がないことを意味します。
そして、ボトムアップパーサーはかなり効率的である傾向があります。したがって、少し複雑な機械の代償を払えば、文法を書くのが簡単になり、パーサーはうまく機能します。
一般的に発生するプログラミング構造がある場合は常に、この種の選択が見られることを期待する必要があります。指定が簡単で、機械が複雑な場合でも非常に優れたパフォーマンスを発揮する場合は、複雑な機械が優先されます。別の例として、インデックス付きファイルを自分で手動で作成できるにもかかわらず、データベースの世界はリレーショナルツールに移行しました。データスキーマの記述、インデックスの指定が簡単で、背後に十分に複雑な機械があれば（ギアを見る必要はなく、ギアを使用するだけです）、ほとんど労力をかけずにかなり高速にできます。同じ理由。
于 2010-11-30T18:36:11.527 に答える
8
それはいくつかの異なるものから生じています。
BNF（および文法などの理論）は、計算言語学、つまり自然言語解析を研究している人々に由来します。BNFは文法を記述する非常に魅力的な方法であるため、これらの表記法を使用してパーサーを作成するのは自然なことです。
残念ながら、トップダウン構文解析手法は、多くの一般的なケース（左再帰など）を処理できないため、このような表記法に適用すると失敗する傾向があります。これにより、パフォーマンスが高く、文法を処理できるLRファミリが残ります。また、それらはマシンによって生成されているため、コードがどのように見えるかを気にしますか？
ただし、その通りです。トップダウンパーサーはより「直感的に」機能するため、デバッグと保守が容易であり、少し練習すれば、ツールによって生成されるパーサーと同じように簡単に記述できます。（特に、シフト/競合の地獄を減らす場合。）回答の多くは構文解析のパフォーマンスについて説明していますが、実際には、トップダウンパーサーは、マシンで生成されたパーサーと同じ速度になるように最適化できることがよくあります。
そのため、多くの実動コンパイラーは手書きのレクサーとパーサーを使用します。
于 2010-11-30T22:08:51.910 に答える
6
再帰下降パーサーは、入力文字列の一般的な構造を仮定しようとします。これは、文字列の終わりに達する前に多くの試行錯誤が発生することを意味します。これにより、そのような推論エンジンを必要としないボトムアップパーサーよりも効率が低下します。
文法の複雑さが増すにつれて、パフォーマンスの違いは大きくなります。
于 2010-11-30T17:25:50.177 に答える
3
他の答えに加えて、ボトムアップパーサーは、効率に加えて、再帰下降パーサーよりもはるかに多くの文法を受け入れることができることを理解することが重要です。トップダウンパーサーは、予測的かどうかに関係なく、先読みトークンを1つしか持つことができず、現在のトークンとその直後のトークンを2つの異なるルールを使用して導出できる場合は失敗します。もちろん、パーサーを実装して先読みを増やすこともできますが（LL（3）など）、ボトムアップパーサーのように複雑になる前に、パーサーをどこまでプッシュしてもかまいませんか？一方、ボトムアップパーサー（具体的にはLALR）は、リストを維持し、firstsトップfollowsダウンパーサーができない場合を処理できます。
もちろん、コンピュータサイエンスはトレードオフに関するものです。文法が十分に単純な場合は、トップダウンパーサーを作成するのが理にかなっています。複雑な場合（ほとんどのプログラミング言語の文法など）、入力を正常に受け入れるには、ボトムアップパーサーを使用する必要がある場合があります。
于 2014-08-08T18:48:53.473 に答える
1
私には2つの推測がありますが、どちらかがそれを完全に説明しているとは思えません。
トップダウン構文解析は遅くなる可能性があります。再帰下降パーサーは、ジョブを完了するのに指数関数的な時間を必要とする場合があります。これにより、トップダウンパーサーを使用するコンパイラーのスケーラビリティーに厳しい制限が課せられます。
より良いツール。EBNFのいくつかのバリアントで言語を表現できる場合は、多くの面倒なコードを通り過ぎてLex/Yaccを実行できる可能性があります。トップダウンパーサーをまとめるタスクを自動化するのに役立つツールはそれほど多くないようです。それに直面しましょう。パーサーコードを細かくすることは、言語をいじるのが楽しい部分ではありません。
于 2010-11-30T17:22:09.217 に答える
1
トップダウンパーサーとshift-reduceパーサーの実際の比較は見たことがありません。
わずか2つの小さなプログラムが同時に並行して実行されました。1つはトップダウンアプローチを使用し、もう1つはボトムアップアプローチを使用しました。それぞれ約200行のコードです。
あらゆる種類のカスタム二項演算子と数式を解析できます。2つは同じ文法宣言形式を共有し、変数宣言と影響を追加して、「ハック」（文脈自由ではない）を実装する方法を示します。
それで、私たちが決してしなかったことについて正直に話す方法：2つのアプローチを厳密に比較しますか？
于 2015-11-12T05:40:33.183 に答える