Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
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
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.
They can all be derived from the LR(0) table - in fact directly so, if using the right kind of analysis. But the result may involve state-splitting. The same LR(0) state may appear in 2 or more LR(k) contexts, making necessary a split into nearly duplicate copies. Each copy differs in terms of which further restrictions it imposes; the restrictions borne of which lookaheads are present.
The Wikipedia article on SLR parsing describes the situation a little better https://en.wikipedia.org/wiki/Simple_LR_parser. Both SLR(1) and LALR(1) work off the same tables. Neither table splits any states from the LR(0) parsing table (a point made clear in the LALR Wikipedia article https://en.wikipedia.org/wiki/LALR_parser), but may impose look-ahead restrictions on reduce actions.
The historically standard method for LR(k) for k > 0 (especially for k > 1!) uses the same number of lookaheads for every state - even when it's not necessary to do so. So, many more splittings may occur as a result. https://en.wikipedia.org/wiki/Canonical_LR_parser
A minimal LR parser for LR(k), in effect, will keep k at the smallest possible value that resolves conflicts for a given state. So, it can be LR(0) 90% of the time and maybe LR(1) or LR(2) or higher for a few bothersome states. It's LR(ω) with variable k ∈ {0,1,2,3,...} = ω.
The ability to talk about this more cogently is greatly impeded by the fact that the LR formalism, itself, is not fully self-contained in an important sense. The parsing tables only describe part of what the parser does. The all-important "roll-back" actions do not explicitly appear anywhere in the table (though they can be derived from what's in the table) and they are not represented directly by the parser itself but only indirectly by either a separate narrative description or separate procedural/algorithmic description. In YACC, that "separate" account is traditionally the "skeleton" use to create the cookie-cutter code that appears in YACC code output.
It is possible to bring it all together within a fully unified, algebraic, framework using a newly-published algebraic framework for context-free expressions; and I'm strongly tempted to describe it in detail here; but this would make the reply an order of magnitude larger. Within this setting it is easier to describe what the different methods are doing.
If there's enough interest I may post the fuller account in a followup; but will hang onto it, in the meanwhile for now.
