Which of the following statement(s) is/are FALSE? (i) The grammar S → Aa | bAc | dc | bda, A → d is LALR(1) but not SLR(1). (ii) The grammar S → Aa | bAc | Bc | bBa, A → d, B → d is LALR(1) but not LR(1).

Which of the following statement(s) is/are FALSE? (i) The grammar S → Aa | bAc | dc | bda, A → d is LALR(1) but not SLR(1). (ii) The grammar S → Aa | bAc | Bc | bBa, A → d, B → d is LALR(1) but not LR(1). Correct Answer Only (ii)

The correct answer is option 1.

Concept:

SLR Parser:

SLR stands for simple LR.

LALR Parser:

A lookahead LR parser is LALR Parser.

LR(1) items = LR(0) items + look ahead.

Explanation:

Option 1: The grammar

S → Aa

S → bAc

S → dc 

S → bda

A → d 

LALR(1) Parser:

In addition to the preceding rules, there is one more rule S' S as the first item. Following the processes for building the LR(1) parser, here is the original state and the resultant state diagram using a closure.

[ alt="F1 Harshita11-2-22 Savita D7" src="//storage.googleapis.com/tb-img/production/22/02/F1__Harshita11-2-22_Savita_D7.png" style="width: 497px; height: 163px;">

LR(1) parsing table as follows:

Next, following the similar procedures for taking closure, but without including the lookahead in items, we obtain the state diagram as follows:

SLR(1) Parser:

[ alt="F1 Harshita11-2-22 Savita D8" src="//storage.googleapis.com/tb-img/production/22/02/F1__Harshita11-2-22_Savita_D8.png" style="width: 466px; height: 148px;">

Let's assume that the parser is in state I7, and the next symbol is a, since a Follows(A)={a,c}, it causes a shift-reduce conflict. The same problem also happens to state I4. Thus, the given grammar is not SLR(1).

Option 2: The grammar

S → Aa

S → bAc

S → Bc 

S → bBa

 A → d

 B → d

In addition to the rules given above, one extra rule S' → S as the initial item. Following the procedures for constructing the LR(1) parser, here is the resulting state diagram:

[ alt="F1 Harshita11-2-22 Savita D9" src="//storage.googleapis.com/tb-img/production/22/02/F1__Harshita11-2-22_Savita_D9.png" style=" width: 482px; height: 205px;">

LR(1) parsing table as follows:

Since there are no multiple actions in any entry, the given grammar is LR(1). However, when obtaining the LALR(1) parsing table by merging states, we will merge states I5 and I9, and the resulting state will be as follows:

I5+9:

A → d., a/c

B → d., a/c

It is basically a reduce-reduce conflict. So, the given grammar is not LALR(1).

Hence the correct answer is Only (ii).