文脈自由文法の解析

Question

左回帰文法を受け入れることができるので、ボトムアップ・パーサはトップダウン・パーサよりも優れていることが分かります。なぜなら、解析しますか？

Answer 1

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

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

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

希望すると便利です。

Answer 2

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