Editing LR parser (section)

=== Bottom-up parse tree for example A * 2 + 1 ===

[[File:Shift-Reduce Parse Steps for A*2+1.svg|thumb|x200px|right|Bottom-up parse tree built in numbered steps]]

An LR parser scans and parses the input text in one forward pass over the text.  The parser builds up the [[parse tree]] incrementally, bottom up, and left to right, without guessing or backtracking.  At every point in this pass, the parser has accumulated a list of subtrees or phrases of the input text that have been already parsed.  Those subtrees are not yet joined together because the parser has not yet reached the right end of the syntax pattern that will combine them.

At step 6 in an example parse, only "A * 2" has been parsed, incompletely.  Only the shaded lower-left corner of the parse tree exists.  None of the parse tree nodes numbered 7 and above exist yet.  Nodes 3, 4, and 6 are the roots of isolated subtrees for variable A, operator *, and number 2, respectively.  These three root nodes are temporarily held in a parse stack.  The remaining unparsed portion of the input stream is "+ 1".