GATE1988-10ib

Question

Consider the following grammar:

• $S \rightarrow S$
• $S \rightarrow SS \mid a \mid \epsilon$

Indicate the shift-reduce and reduce-reduce conflict (if any) in the various states of the LR(0) parser.

Comments

Here  S→  ϵ will take as reduce/ shift action or not effect on LR(0)  DFA??

Answer 1

Both conflicts are present .

SR and RR

Comments

grammar is ambiguous.

Answer 2

The LR(0) DFA is shown below with states labeled as $I_{0}, I_{1}, I_{2}, I_{3}$.

Note : In the DFA, the transition $S\rightarrow \varepsilon$ is same as the transition $S\rightarrow .$ (as it is a reduce move).

The SR conflicts in this DFA are:

  a. State $I_{0}$: Shift move on 'a' and a reduce move $S\rightarrow .$

  b. State $I_{1}$: Shift move on 'a' and a reduce move $S\rightarrow .$

  c. State $I_{2}$: Shift move on 'a' and a reduce move $S\rightarrow .$

(moves on non-terminal symbol 'S' are goto moves and not shift moves).

 

The RR conflicts in this DFA are:

  a. State $I_{1}$: $S\rightarrow .$ and $S\rightarrow S.$

  b. State $I_{2}$: ($S\rightarrow S.$ and $S\rightarrow .$ ) , ( $S\rightarrow SS.$ and $S\rightarrow .$ )

 

Answer 3

only RR conflict