Difference between revisions of "LR(k) ---- LR(1) Parsers"

From eplmediawiki
Jump to: navigation, search
(Created page with "'''''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 e...")
 
Line 1: Line 1:
'''''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 [[http://eplmediawiki.di.uminho.pt/index.php/LL(k)_----_LL(1)_Parsers|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.  
+
'''''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 [[http://eplmediawiki.di.uminho.pt/index.php/LL(k)_----_LL(1)_Parsers | 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>
 
<br><br>
  

Revision as of 18:52, 24 November 2012

LR - Left-to-right parse, Rightmost 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.

LR(k) recognizers - and their variants such as [[1]] - 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.

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.

Personal tools
Namespaces

Variants
Actions
Navigation
extras
Toolbox