in Compiler Design edited by
1,445 views
2 votes
2 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
in Compiler Design edited by
by
1.4k views

4 Comments

LR(0) is a top-down parser, it can not parse ambiguous grammar, even all parser can't parse ambiguous grammar and every regular grammar need't be unambiguous  

example: A-->Ba/aa

                  B-->a

for above regular grammar has two parse tree for string "aa"
0
0

@Arjun @GO Classes

Hi sir, If I take a grammar:

S -> M A
M ->
A -> a

Then, this grammer is LR(0) and also have GOTO action with REDUCED action. So, can I say that Op C is also false?

Please correct me sir If I am wrong.

1
1
I am not getting how 1,2,3 are true,as LR(0) parser can have both r-r and s-r conflict possible,

hence a LR(0) configurating set can have multple reduce item,etc
0
0

2 Answers

3 votes
3 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.
by

4 Comments

Ambiguous Regular:

S→A | B
A→a
B→a

4
4
I have doubt in option C.. it can be the case that A-> a. is a reduce move and along with it we can have other items as B->a.C and C->.d (in the same state of LR0 items)
1
1
0 votes
0 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
Answer:

Related questions