edited by
3,060 views
3 votes
3 votes

Which of the following statements regarding $LR(0)$ parser is FALSE?

  1. A $LR(0)$ configurating set cannot have multiple reduce items
  2. A $LR(0)$ configurating set cannot have  both shift as well as reduce items
  3. If a reduce item is present in a $LR(0)$ configurating set it cannot have any other item
  4. A $LR(0)$ parser can parse any regular grammar
edited by

3 Answers

4 votes
4 votes
No grammar with empty production can be LR(0). But empty rules are allowed in regular grammar as the only condition for a grammar to be regular is to be either left linear or right linear.
1 votes
1 votes

Since LR(0) parser places reduce-moves in the entire row of "Action", having anything more than just the reduce-move in the state having final-item would lead to SR or RR conflict.

So, Options A, B and C are true.

 

So Option D must be false. But why is that?

Intuitively, there can be a Regular Language that has its grammar such that the state having a final-item would have some additional item.

But to give a counter example:

$S\rightarrow aA$,

$A\rightarrow b|\epsilon$

It has an $\epsilon$ production. Any grammar with $\epsilon$ production can't be LR(0), because in the parsing table, we'd put reduce-

moves in the corresponding row, on which a shift-move can result in an SR conflict.



In contrast, an SLR(1) parser can have multiple reduce-moves, or both shift and reduce moves in the same state.

edited by
0 votes
0 votes

 

  1. A LR(0) configurating set cannot have multiple reduce items => This is true bcoz multiple reduce items will create a RR conflict 
  2. A LR(0) configurating set cannot have  both shift as well as reduce items => This is true bcoz multiple reduce items will create a SR conflict
  3. If a reduce item is present in a LR(0) configurating set it cannot have any other item => True bcoz in LR(0) the entire row is filled with reduce part. So having anything else will 100% be a conflict.
  4. A LR(0) parser can parse any regular grammar . False => Bcoz LR(0) cant parse Ambiguos Grammars and Regular G can be ambigious too.

So Ans is D

Answer:

Related questions

4 votes
4 votes
2 answers
2
Arjun asked Jan 26, 2019
835 views
Suppose we have a rightmost derivation which proceeds as follows:$\begin{array}{ccc}S &\rightarrow & Aabw \\ & \rightarrow &ABw \end{array}$Which of the following is a po...
6 votes
6 votes
2 answers
4
Arjun asked Jan 26, 2019
1,691 views
If we merge states in LR(1) parser to form a LALR(1) parser, we may introduceshift-reduce conflictreduce-reduce conflictno extra conflictboth shift-reduce as well as redu...