Parsing: A grammar in LL(3) but not in LR(2) [closed]

Question

Closed. This question is off-topic. It is not currently accepting answers.

---

Want to improve this question? Update the question so it's on-topic for Stack Overflow.

Closed 8 years ago.

Improve this question

I'm trying to prove that LL(3) is not a subset of LR(2).

Intuitively it's easy, but I can't point my intuition into finding such a grammar.

Could you please give me a hand? Thanks for any help

Answer 1

Theorem: If a grammar is LL(3) but not LR(2), then the grammar has ε-productions.

Proof: A grammar is LL(3) if it always is possible to identify the handle in a right sentential form after reading three characters past the beginning of the handle.

A grammar is LR(2) if it always is possible to identify the handle in a right sentential form after reading two characters past the end of the handle.

If a grammar is LL(3) but not LR(2), then reading three characters past the beginning of the handle must sometimes provide more information than reading two characters past the end of the handle. That can only happen if the handle is empty.

Answer 2

Well, apparently the trick is to use ε-productions.

The following grammar would work:

S->aa|Aaaa

A->ε