再帰降下パーサーで使用される文法には 2 種類の制限があることを私は知っています。
- 文法には左再帰生成を含めることはできません
- 文法は、トークン先読み以上を要求してはなりません。
最初の制限は理解していますが、2 番目の制限については少し迷っています。なぜこの制限が必要なのですか？
1573 次
1 に答える
4
2 番目の制限は、パーサーがk(単一のトークンに基づくのではなく) 最初のトークンに基づいて使用するプロダクションを決定できるようにすることで、いくらか緩和できます。これにより、このクラスの文法に対して効率的な (つまり、線形時間の) 構文解析アルゴリズムが可能になります (再帰降下パーサーを参照してください)。
実際に選択する主な理由は、文法用のパーサーの方が構築しやすいk=1ためと思われます。LL(1)どうやら多くのコンピューター言語は、LL(1)文法によって生成されるように設計されています。LL パーサーを参照してください。
パーサーは単一のトークンに基づいてどのプロダクションを使用するかを決定できないため、プロダクションS -> A | B、A -> a A b | eps、およびで構成される文法はB -> a B b b | eps、あいまいでない非文法の例です。（ここLL(1)から撮影。）
于 2016-03-24T13:21:19.320 に答える