recategorized by
2,152 views
4 votes
4 votes

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 $\text{LR(0)}$ parser.

recategorized by

2 Answers

Best answer
7 votes
7 votes

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:

  1. State $I_{0}$: Shift move on 'a' and a reduce move $S\rightarrow .$
  2. State $I_{1}$: Shift move on 'a' and a reduce move $S\rightarrow .$
  3. 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:

  1. State $I_{1}$: $S\rightarrow .$ and $S\rightarrow S.$
  2. State $I_{2}$: ($S\rightarrow S.$ and $S\rightarrow .$ ) , ( $S\rightarrow SS.$ and $S\rightarrow .$ )
edited by
1 votes
1 votes
Both conflicts are present .

SR and RR

Related questions

10 votes
10 votes
2 answers
1
go_editor asked Dec 19, 2016
3,592 views
Consider the following grammar:$S \rightarrow S$$S \rightarrow SS \mid a \mid \epsilon$Construct the collection of sets of $\text{LR (0)}$ items for this grammar and draw...
8 votes
8 votes
1 answer
4
go_editor asked Dec 19, 2016
2,410 views
Construct a DAG for the following set of quadruples:E:=A+BF:=E-CG:=F*DH:=A+BI:=I-CJ:=I+G