algorithm - 文脈自由文法の構文解析

Question

ボトムアップパーサーは、左再帰文法を受け入れることができるため、トップダウンパーサーよりも優れていることを私は知っていますが、トップダウン構文解析よりもボトムアップ構文解析を好む他の理由は何でしょうか。

Answer 1

理論的には、LL（k）文法は、常に任意のkのLR（k）文法の厳密なサブセットであるため、決定論的予測ボトムアップパーサーは、決定論的予測トップダウンパーサーよりも厳密に多くの文法セットを受け入れることができます。これは、LL（k）文法もLR（k）であることを意味します。

また、トリッキーな証明は、決定性CFL（決定性プッシュダウンオートマトンによって受け入れられるCFL）がLR（1）文法を持っていることを示しています。これは、LR文法が効率的なスタックベースの解析アルゴリズムを持つ言語に正確に対応することを意味します。

とはいえ、Ungerのアルゴリズム、Earleyのアルゴリズム、CYKアルゴリズムなど、より一般的な解析アルゴリズムを許可する場合は、任意のCFGを解析するためのトップダウンおよびボトムアップの方法が存在します。ただし、これらのアルゴリズムは予測手法よりもはるかに低速になる可能性があるため、通常、プログラミング言語には使用されません。

お役に立てれば！

Answer 2

bysonのようなボトムアップパーサージェネレーターがあります。それらを使用することは、パーサーを手動で作成するよりもはるかに簡単です。
また、再帰下降パーサーは、デフォルトですべての操作を右連想にしますが、これは算術演算では正しくありません。それらを左結合に戻すには、解析に追加の手順が必要です。