0
$\begingroup$

I understand the difference in the parsing tables of the above 4 parsers. I understand that CLR>LALR>SLR>LR(0) in terms of power.

Are shift and goto moves for all LR parsers ( LR(0), SLR(1),CLR(1),LALR(1) ) same?. I think goto should vary as reduce moves vary? Also, if a grammar is accepted by CLR(1) parser, for which parser it would have highest and lowest no. of reduce moves or would it be the same? Please explain

$\endgroup$
1
$\begingroup$

Every reduce action corresponds to a production; the action "undoes" the production by replacing its right-hand side with the non-terminal which produced it.

That can only happen in one way; the parsing automaton does not invent or suppress non-terminals. So it doesn't matter which algorithm was used to create the automaton; the actions will be the same.

The automata may have different numbers of states, so the state sequence may differ. But not the actions performed on state transitions.

To put it another way:

If a grammar has an *LR automaton, the grammar is unambiguous, which by definition means that there is only one rightmost derivation. A rightmost derivation, written backwards from sentence to start symbol, can be represented as a series of shifts and reduces. Any LR grammar which recognises a sentence in this grammar must produce the same rightmost derivation, so it must perform the sane sequence of shifts and reduces.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.