先読みの文法制限

Question

私は、再帰的降下パーサーで使用される文法には2つのタイプの制限があることを知っています。

1. 文法は文法は、トークンが先読みでより多くを要求してはなりません任意の左再帰的な制作
2. を持つことはできません。

私は最初のものを理解していますが、2番目の制限で少し失われています。なぜこの制限が必要であり、それがなければ生産も存在するのだろうか？

Answer 1

2番目の制限は、最初のkトークン（単一のトークンに基づいているのではなく）に基づいて、パーサーがどのプロダクションを使用するかを決定することを要求することによって幾分緩和することができます。これにより、文法のこのクラスに対する効率的な（すなわち、線形時間の）解析アルゴリズムが可能になる（Recursive descent parser参照）。

実際にk=1を選択する主な理由は、LL(1)文法のパーサを構築する方が簡単だと思われます。明らかに多くのコンピュータ言語は、LL(1)文法によって生成されるように設計されています。 LL parserを参照してください。

文法はプロダクションS -> A | B、A -> a A b | eps成る、パーサは、単一のトークンに基づいて、使用する生産を決定することができないためB -> a B b b | eps非曖昧非LL(1)文法の一例です。 （hereから）