Editing LR(k) ---- LR(1) Parsers

'''''LR''' - '''L'''eft-to-right parse, '''R'''ightmost derivation''. The '''LR(k)''' class of grammars is weaker than the context-free grammar class, but is still extremely expressive. In contrast to the LL(k) parsers where k lookahead symbols must uniquely predict which alternative to attempt (i.e., on the left edge), the LR(k) parsers make decisions at the right edge, after having seen the entire production. 
<br><br>

LR(k) recognizers - and their variants such as [http://eplmediawiki.di.uminho.pt/index.php/LALR_Parsers LALR(k)] - are stronger than LL(k) recognizers because the LR strategy uses more context information. For an LR parser, the context consists of all grammar productions consistent with the previously seen input. This context often includes several "pending" grammar productions. Intuitively, an LR(k) parser attempts to match multiple productions at the same time and postpones making a decision until sufficient input has been seen. In contrast, the context for an LL parser is restricted to the sequence of previously matched productions and the position within the current grammar production being matched. An LL(k) parser must make decisions about which production to match without having seen any portion of the pending productions - it has access to less context information. Hence, LL(k) parsers rely heavily on lookahead. 
<br><br>

The LR(k) Parser is a standard iterative algorithm that in each iteration decides the action to perform based on the current (analysis) state and on the next input (terminal) symbol under processing. That decision is taken according to the transition function of a pushdown deterministic finite automaton built systematically from the grammar. The transition function is kept in memory splitted into 2 tables: the '''ACTION''' table is indexed by State x Terminal and each entry has a compound value (the type of action to be performed - accept, reject (error), shift, reduce - and the next State or the Production-number); the '''GOTO''' table is indexed by State x Non-Terminal and each entry has a compound value (the type of action to be performed - shift - and the next State). The state, after a "shift" action, is pushed onto the LR(k) parsing stack; the state on the top will be the next state, to be considered in the next iteration. During a "reduce" action states are poped out of the stack, as many as the number of symbols in the right hand side of the production to be reduced. 

[[Category:Basic Concepts]]