search
Log In
2 votes
296 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
edited by
296 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.
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.


edited by
Answer:

Related questions

2 votes
2 answers
1
329 views
Which of the following sentences regarding Viable prefixes is/are CORRECT? Viable prefixes is the set of prefixes of right-sentential forms that can appear on the stack of a shift-reduce parser Viable prefixes is the set of prefixes of right-sentential forms that do not extend past the end of the ... prefixes can be recognized using a DFA Only (i) Only (ii) Only (i) and (ii) (i), (ii) and (iii)
asked Jan 26, 2019 in Compiler Design Arjun 329 views
0 votes
2 answers
2
211 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 possible handle for it? $\begin{array}{ccc} A &\rightarrow & ab \end{array}$ ... $\begin{array}{ccc} S &\rightarrow & A \end{array}$ $\begin{array}{ccc} B &\rightarrow & ab \end{array}$
asked Jan 26, 2019 in Compiler Design Arjun 211 views
2 votes
0 answers
3
196 views
Which of the following statements regarding LR parsers is WRONG? LR(1) does no guess work LR parsers can handle a large range of grammars than predictive parsers LR parsers can handle a large range of languages than predictive parsers LR parser is better at error reporting compared to LL ones Only (i) (i) and (iv) Only (iv) All are CORRECT
asked Jan 26, 2019 in Compiler Design Arjun 196 views
4 votes
2 answers
4
567 views
Which of the following statements is FALSE? Any DCFL has an equivalent grammar that can be parsed by a SLR(1) parser with end string delimiter Languages of grammars parsed by LR(2) parsers is a strict super set of the languages of grammars parsed by LR(1) parsers Languages of ... of grammars parsed by LL(1) parsers There is no DCFL which is not having a grammar that can be parsed by a LR(1) parser
asked Jan 26, 2019 in Compiler Design Arjun 567 views
...