LR(0) or SLR(1) or LALR(1)

Question

I am badly stuck on a question i am attempting from a sample final exam of compilers. I will really appreciate if someone can help me out with an explanation. Thanks

Consider the grammar G listed below

1. S = E $
2. E = E + T | T
3. T = T * F | F
4. F = ident | ( E )

Where + * ident ( ) are terminal symbols and $ is end of file. a) is this grammar LR( 0 )? Justify your answer. b) is the grammar SLR( 1 ) ? Justify your answer. c) is this grammar LALR( 1 )? Justify your answer.

Answer 1

If you can show that the grammar is LR(0) then of course it is SLR(1) and LALR(1) because LR(0) is more restrictive.

Unfortunately, the grammar isn't LR(0).

For instance suppose you have just recognized E:

S -> E . $

You must not reduce this E to S if what follows is a + or * symbol, because E can be followed by + or * which continue to build a larger expression:

S -> E . $
E -> E . + T
T -> T . * F

This requires us to look ahead one token to know what to do in that state: to shift (+ or *) or reduce ($).

SLR(1) adds lookahead, and makes use of the follow-set information to make reductions (better than nothing, but the follow-set information globally obtained from the grammar is not context sensitive, like the state-specific lookahead sets in LALR(1)).

Under SLR(1), the above conflict goes away, because the S -> E reduction is considered only when the lookahead symbol is in the follow set of S, and the only thing in the follow set of S is the EOF symbol $. If the input symbol is not $, like +, then the reduction is not considered; a shift takes place which doesn't conflict with the reduction.

So the grammar does not fail to be SLR(1) on account of that conflict. It might, however, have some other conflict. Glancing through it, I can't see one; but to "justify that answer" properly, you have to generate all of the LR(0) state items, and go through the routine of verifying that the SLR(1) constraints are not violated. (You use the simple LR(0) items for SLR(1) because SLR(1) doesn't augment these items in any new way. Remember, it just uses the follow-set information cribbed from the grammar to eliminate conflicts.)

If it is SLR(1) then LALR(1) falls by subset relationship.

Update

The Red Dragon Book (Compilers: Principles, Techniques and Tools, Aho, Sethi, Ullman, 1988) uses exactly the same grammar in a set of examples that show the derivation of the canonical LR(0) item sets and the associated DFA, and some of the steps of filling in the parsing tables. This is in section 4.7, starting with example 4.34.