227 views

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 | 227 views
0
Sir, cannot we have a reduce move and a GOTO action in same canonical item ?
+1
Not for LR(0) parser
0
I just realized how dumb that question was. Sorry sir
0
If there is a reduce move we place it only in the action part right???

So what happens when we have a reduce item and Goto item in the same state??
0
When we reduce using a production say $A \to Bcd$, we pop 3 items from stack - since production used for REDUCE has 3 symbols, and move to a state given by GOTO(S, A) where S is the stack top after the pop moves.
0
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"

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 Veteran (430k points)
0

@Arjun sir, isn't B false?

0
Yes. Just corrected the option
+2
Sir, can we say that since a given regular grammar can be ambiguous and LR(0) parsers can't parse any ambiguous grammar, so option (d) is false ?
+1
Can you give an ambiguous regular grammar?
+4

Ambiguous Regular:

S→A | B
A→a
B→a

+2

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.

by Loyal (5.9k points)
edited