GATE CSE 2008 | Question: 55

Question

An LALR(1) parser for a grammar G can have shift-reduce (S-R) conflicts if and only if

• A. The SLR(1) parser for G has S-R conflicts

• B. The LR(1) parser for G has S-R conflicts

• C. The LR(0) parser for G has S-R conflicts

• D. The LALR(1) parser for G has reduce-reduce conflicts

Comments

If  CLR(1) have RR conflict or may not have RR conflict .still LALR(1) may have RR Conflict

LALR(1) have SR conflict if and only if CLR(1) have SR conflict 

 

(CLR(1) is also called as LR(1))

---

@Mitali gupta do u have any resources to support your point. If Yes then please share the link.

---

example, of

“If  CLR(1) have RR conflict or may not have RR conflict .still LALR(1) may have RR Conflict

LALR(1) have SR conflict if and only if CLR(1) have SR conflict “

 

 

 

 

 

 

 

 

 

 

 

 

 

Answer 1

Both LALR(1) and LR(1) parser uses LR(1) set of items to form their parsing tables. And LALR(1) states can be found by merging LR(1) states of LR(1) parser that have the same set of first components of their items.

i.e. if LR(1) parser has $2$ states I and J with items $A \rightarrow a.bP$,$x$ and $A \rightarrow a.bP$,$y$ respectively, where $x$ and $y$ are look ahead symbols, then as these items are same with respect to their first component, they can be merged together and form one single state, let’s say $K$. Here we have to take union of look ahead symbols. After merging, State $K$ will have one single item as $A \rightarrow a.bP$,$x$,$y$ . This way LALR(1) states are formed ( i.e. after merging the states of LR(1) ).

Now, $S-R$ conflict in LR(1) items can be there whenever a state has items of the form :

A-> a.bB , p
C-> d. , b

i.e. it is getting both shift and reduce at symbol b, 
hence a conflict. 

Now, as LALR(1) have items similar to LR(1) in terms of their first component, shift-reduce form will only take place if it is already there in LR(1) states. If there is no S-R conflict in LR(1) state it will never be reflected in the LALR(1) state obtained by combining LR(1) states.

Correct Answer: $B$

Comments

CLR don’t have RR conflict but they can still arise in LALR on merging .

But SR conflict may arise after merging (Does not matter If present in CLR or not )

---

can someone please provide an example wherein the SLR(1) doesn’t have SR conflict but LALR(1) has ??

---

@reboot that’s not possible bro please read the answer.

Answer 2

Answer is B.

Comments

LALR(1) can have conflict even if LR(1) do not contain any conflict. Conflict may arise while merging.

---

why not (c), in LR(0) items S-R conflict??

edit:correction, LR(1) = CLR(1) so it makes sense , so option (b) is correct

---

can someone please provide an example wherein the SLR(1) doesn’t have SR conflict but LALR(1) has ??

Answer 3

The answer is The LR(1) parser for G has S-R conflicts.

Here's a breakdown of why:

1. Relationship between LALR(1) and LR(1):

• LALR(1) is a simplified version of LR(1).
• It constructs its parsing table by merging states from the LR(1) parser.
• This means any S-R conflict present in LR(1) will also exist in LALR(1).

2. SLR(1) and LR(0):

• SLR(1) is even simpler than LALR(1), so it can have S-R conflicts that LALR(1) doesn't.
• LR(0) doesn't use lookahead information, so it can also have S-R conflicts that LALR(1) doesn't.

3. Reduce-Reduce Conflicts:

• Reduce-reduce conflicts are different from S-R conflicts and don't directly imply S-R conflicts in LALR(1).