Editing LR parser (section)

=== Bottom-up parse stack ===

[[File:Bottom-Up Parser.svg|thumb|x250px|right|Bottom-up parser at step 6]]

Like other shift-reduce parsers, an LR parser lazily waits until it has scanned and parsed all parts of some construct before committing to what the combined construct is.  The parser then acts immediately on the combination instead of waiting any further.  In the parse tree example, the phrase A gets reduced to Value and then to Products in steps 1-3 as soon as lookahead * is seen, rather than waiting any later to organize those parts of the parse tree.  The decisions for how to handle A are based only on what the parser and scanner have already seen, without considering things that appear much later to the right.

Reductions reorganize the most recently parsed things, immediately to the left of the lookahead symbol.  So the list of already-parsed things acts like a [[stack (abstract data type)|stack]].  This '''parse stack''' grows rightwards.  The base or bottom of the stack is on the left and holds the leftmost, oldest parse fragment.  Every reduction step acts only on the rightmost, newest parse fragments.  (This accumulative parse stack is very unlike the predictive, leftward-growing parse stack used by [[top-down parser]]s.)