The following grammar is: S → Aa | bAc | Bc | bBa A → d B → d

The following grammar is: S → Aa | bAc | Bc | bBa A → d B → d
|

The following grammar is:

S → Aa | bAc | Bc | bBa

A → d

B → d

A. LR(1) and LALR(1)

B. Not LR(1) but LALR(1)

C. LR(1) but not LALR(1)’

D. Neither LR(1) nor LALR(1)

Please scroll down to see the correct answer and solution guide.

Right Answer is: C

SOLUTION

Constructing canonical collection for LR (1) items,

All the final states have been reached without any conflict, hence the grammar is CLR (1) or LR (1).

Now to find out whether the grammar is LALR (1) or not, it is necessary to fetch the states that are different only in terms of lookaheads. If there are any two states like this, the grammar cannot be LALR (1).  The states marked with * satisfy this condition.

For CLR (1) or LR (1)

 

a

b

c

d

$

2

r5

 

r5

 

 

3

r6

 

r6

 

 

 

Here, no RR conflict arises. Therefore, given grammar is LR (1).

For LALR (1), we combine state 2 and state 3.

 

a

b

c

d

$

23

r5/r6

 

r5/r6

 

 

 

Here, RR conflict arises. Therefore, given grammar is not LALR (1).

Related Questions