Editing LR parser (section)

=== LR parser loop ===

The LR parser begins with a nearly empty parse stack containing just the start state 0, and with the lookahead holding the input stream's first scanned symbol.  The parser then repeats the following loop step until done, or stuck on a syntax error:

The topmost state on the parse stack is some state ''s'', and the current lookahead is some terminal symbol ''t''.  Look up the next parser action from row ''s'' and column ''t'' of the Lookahead Action table.  That action is either Shift, Reduce, Accept, or Error:
* Shift ''n'':
::Shift the matched terminal ''t'' onto the parse stack and scan the next input symbol into the lookahead buffer.
::Push next state ''n'' onto the parse stack as the new current state.
* Reduce r<sub>''m''</sub>:  Apply grammar rule r<sub>''m''</sub>: Lhs → S<sub>1</sub> S<sub>2</sub> ... S<sub>L</sub>
::Remove the matched topmost L symbols (and parse trees and associated state numbers) from the parse stack.
::This exposes a prior state ''p'' that was expecting an instance of the Lhs symbol.
::Join the L parse trees together as one parse tree with new root symbol Lhs.
::Lookup the next state ''n'' from row ''p'' and column ''Lhs'' of the LHS Goto table.
::Push the symbol and tree for Lhs onto the parse stack.
::Push next state ''n'' onto the parse stack as the new current state.
::The lookahead and input stream remain unchanged.
* Accept: Lookahead ''t'' is the ''eof'' marker.  End of parsing. If the state stack contains just the start state report success. Otherwise, report a syntax error.
* Error: Report a syntax error.  The parser ends, or attempts some recovery.

LR parser stack usually stores just the LR(0) automaton states, as the grammar symbols may be derived from them (in the automaton, all input transitions to some state are marked with the same symbol, which is the symbol associated with this state). Moreover, these symbols are almost never needed as the state is all that matters when making the parsing decision.<ref name="Compilers 2006">Compilers: Principles, Techniques, and Tools (2nd Edition), by Alfred Aho, Monica Lam, Ravi Sethi, and Jeffrey Ullman, Prentice Hall 2006.</ref>