LL(3)がLR(2)のサブセットではないことを証明しようとしています。
直感的には簡単ですが、そのような文法を見つけることに直感を向けることはできません。
手を貸していただけませんか。助けてくれてありがとう
定理:文法が LL(3) であるが LR(2) でない場合、その文法には ε プロダクションがあります。
証明:ハンドルの先頭から 3 文字を読み取った後、常に正しい文形式でハンドルを識別できる場合、その文法は LL(3) です。
ハンドルの末尾から 2 文字を読み取った後、常に正しい文形式でハンドルを識別できる場合、文法は LR(2) です。
文法が LL(3) で LR(2) ではない場合、ハンドルの先頭から 3 文字を読み取ると、ハンドルの末尾から 2 文字を読み取るよりも多くの情報が得られる場合があります。これは、ハンドルが空の場合にのみ発生します。
どうやら、トリックは ε プロダクションを使用することです。
次の文法が機能します。
S->aa|Aaaa
A->ε