The Gateway to Computer Science Excellence
+2 votes
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
in Compiler Design by Veteran (430k points)
edited by | 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"

2 Answers

+2 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 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

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.

by Loyal (5.9k points)
edited by
Answer:

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,741 questions
57,231 answers
197,991 comments
104,578 users