search
Log In
0 votes
408 views

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.

in Compiler Design
recategorized by
408 views
0

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

3 Answers

1 vote
Both conflicts are present .

SR and RR
1
grammar is ambiguous.
0 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:

  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 .$ )

 

–1 vote
only RR conflict

Related questions

3 votes
2 answers
1
598 views
Consider the following grammar: $S \rightarrow S$ $S \rightarrow SS \mid a \mid \epsilon$ Construct the collection of sets of LR (0) items for this grammar and draw its goto graph.
asked Dec 19, 2016 in Compiler Design jothee 598 views
3 votes
1 answer
2
320 views
Consider the DFA $M$ and NFA M2 as defined below. Let the language accepted by machine $M$ be $L$. What language machine M2 accepts, if $F2=A$ ? $F2=B$ ? $F2=C$ ? $F2=D$ ? $M=(Q, \Sigma, \delta, q_0, F)$ $M2=(Q2, \Sigma, \delta_2, q_{00}, F2)$ ... $D=\{\langle p, q, r \rangle \mid p \in Q; q \in F\}$
asked Dec 20, 2016 in Theory of Computation jothee 320 views
1 vote
0 answers
3
168 views
The code for the implementation of a sub-routine to convert positive numeric data from binary to appropriate character string in a $PDP-11$ like machine has been given below Note-that $SP$ is the stack pointer and $R_i$ represents $i^{th}$ ...
asked Dec 19, 2016 in CO and Architecture jothee 168 views
0 votes
0 answers
4
138 views
A ROM has the following time parameters: Maximum Address to valid Data Output delay = 30 n sec. Maximum Chip Select to valid Data Output delay = 20 n sec. Maximum Data Hold time (after address change or after chip deselect) = 10 n sec Assume that, the chip ... time is negligible What is the maximum rate at which a CPU can continuously read data from this ROM? (Show your calculations step-by-step)
asked Dec 19, 2016 in CO and Architecture jothee 138 views
...