Can a grammar ever be parsed by LL(1) but not with LR(1)?

Question

For homework, I was given the following grammar:

S: D
D: AbBb | BaAb
A: ε 
B: ε

I computed it using LL(1) just fine. The first sets were:

S: a, b
D: a,b
A: ε 
B: ε

The follow sets were:

S: $
D: $
A: b
B: a,b

When I made my parsing table, the example string "ab" parsed just fine. However, when I tried to parse the same exact grammar using LR(1), I ran into errors.

For item set 0 I got the following: (the , separates the look ahead terminals)

Item set 0:

S: .D, $
D: .AbBb, $ 
D: .BaAb, $
A: ., b
B: ., a,b

If you make the table, you will clearly see that there is a reduce-reduce conflict between A and B in item set 0. If I'm asked to parse the string "ab", the parser won't know whether to reduce my empty to A or to reduce it to B. What am I doing wrong? I was always told that LR(1) can actually parse more grammars than LL(1), so what is the deal here? I would appreciate if somebody could help me out because it's driving me nuts. Thanks

Answer 1

They state you've generated looks like its from an SLR(1) parser.

If you use LR(1) or even LALR(1), you will find there are no conflicts. Here, for example, is state 0 of the LALR(1) machine, as generated by Bison:

State 0

0 $accept: . S $end
1 S: . D
2 D: . A 'b' B 'b'
3  | . B 'a' A 'b'
4 A: . %empty  ['b']
5 B: . %empty  ['a']

'a'       reduce using rule 5 (B)
$default  reduce using rule 4 (A)

S  go to state 1
D  go to state 2
A  go to state 3
B  go to state 4

---

While it is certainly true that LL(1) ⊂ LR(1), there is no simple relationship between LL(1) and either SLR(1) or LALR(1). (I'm talking about grammars here. For sets of languages, the relationships are simpler.) Your grammar is a reasonably simple example of an LL(1) grammar which is not SLR(1); for an example of an LL(1) grammar which is not LALR(1), see this answer.