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

rici
  • 234,347
  • 28
  • 237
  • 341
Ryan Foster
  • 103
  • 9

1 Answers1

2

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.

rici
  • 234,347
  • 28
  • 237
  • 341
  • I'm confused, are you saying the look ahead states for A and B are ['a'] and ['b']? Also, what I learned was that SLR(1) is all the first and follow sets of the grammar. Whereas in LR(1) you create the first and follow sets only for the non-terminals you need as you go. Isn't that what I did in my second example? – Ryan Foster Nov 04 '19 at 22:18
  • 2
    @ryan: those are the lookahead sets *in that state*, yes. In the LR(1) construction, you don't use the FOLLOW sets of the non-terminals, as computed for top-down parsing. The lookahead sets come from the context in which the non-terminal appears in that state. – rici Nov 04 '19 at 22:22
  • 2
    @ryan: [Here's a nice answer](https://stackoverflow.com/a/14127281/1566221) with a completely worked lookahead computation. – rici Nov 04 '19 at 22:27
  • Sorry, let me reword what I stated. I understand that the lookahead states are the first sets of the non-terminal you are currently looking at, NOT the FOLLOW sets. However I'm confused on how the lookaheads for non-terminal B are just 'a' and not 'a', 'b'. When looking at D -> .AbBb the first of B in this case is 'b'. When looking at D -> .BaAb the first of B is 'a'. Therefore, shouldn't the lookahead states be BOTH 'a', and 'b'. I'm confused on that. thanks. – Ryan Foster Nov 04 '19 at 22:32
  • 2
    @ryan: the lookaheads are not the first sets of the "nonterminal you're looking at". They are the FIRST sets of the part of the right-hand side following the non-terminal (augmented, if necessary, with the lookahead for the item). In this case, the lookahead for `A: . %empty` is `FIRST(bBb)`, which obviously doesn't contain an `a`. That should be easy to understand: the lookahead set for a reduction contains the terminals which could follow the reduction, and it is quite clear that reducing `A` *in this state* can only happen if the next terminal is `b`. – rici Nov 04 '19 at 22:40
  • 2
    @ryan: honestly, i think @ templatetypedef explains it more clearly in the answer I linked above. – rici Nov 04 '19 at 22:43
  • I think I understand now. What i was doing was looking at every occurrence of the non terminal and calculating the first sets of it. For example, for B I understood that the look-aheads were the First(aAb) which is a, but I also looked at the B in the statement above it and calculated the First(b). This is where I got a,b from. – Ryan Foster Nov 04 '19 at 22:47
  • @torek: oops, fixed. – rici Nov 07 '19 at 03:53