shift-reduce parsing

Picture a worker at a conveyor belt with a small table beside them. Items come down the belt one at a time. The worker has just two moves: take the next item off the belt and set it on the table (that is a shift), or notice that the last few items on the table form a known assembly and clip them together into a single completed part (that is a reduce). Shift-reduce parsing is exactly this discipline applied to tokens and grammar rules, using a stack as the table.

The parser maintains a stack and reads input left to right. A shift pushes the next input token onto the stack. A reduce looks at the top of the stack, finds that the top symbols match the right-hand side of some production A -> alpha, pops those symbols, and pushes A in their place. Parsing succeeds when the entire input has been consumed and the stack holds exactly the start symbol. For E -> E + E | num on num + num, the parser shifts num, reduces to E, shifts +, shifts num, reduces to E, then reduces E + E to E and accepts. The hard decision at every step is shift versus reduce, and which rule to reduce by, this is the decision that LR parsers automate with a state machine and a table.

Shift-reduce is the engine of all bottom-up parsing, and the LR family (LR(0), SLR, LALR, LR(1)) is simply different ways of computing precisely when to shift and when to reduce. When the grammar leaves the choice genuinely undecidable from the available information, the table-builder reports a shift-reduce conflict or a reduce-reduce conflict, which the grammar writer resolves with precedence and associativity declarations or by rewriting the grammar. Tools like yacc and bison generate exactly this kind of parser.