CODEWITHSUNDEEP
compiler-constructionautomatacomputabilitylr1
Ryan Foster
Ryan Foster

Reputation: 101

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

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

Upvotes: 1

Views: 1130

Answers (1)

rici
rici

Reputation: 241911

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.

Upvotes: 2

Related Questions