Bottom-Up Parsing

Bottom-up parsing is a family of parsing techniques that construct a parse tree starting from the leaves — the input tokens — and working upward toward the root, the grammar's start symbol. Rather than predicting structure, a bottom-up parser accumulates evidence: it shifts tokens onto a stack and reduces sequences of tokens to non-terminals when they match the right-hand side of a grammar production. The canonical bottom-up approach is the LR parser, including its practical variants SLR, LALR, and the table generators Yacc and Bison.

Bottom-up parsing is more powerful than top-down parsing in the formal sense: every grammar accepted by an LL(k) parser is accepted by some LR(1) parser, but not vice versa. This power comes from delayed commitment. The parser does not decide which production a token belongs to until it has seen the entire right-hand side, carrying multiple hypotheses on its stack until the evidence forces a choice.

Bottom-up parsing is the scientific method applied to syntax: accumulate observations, postpone hypothesis, commit only when the data demands it. The LR parser's shift-reduce cycle is not an algorithmic detail; it is an epistemological stance — one that top-down parsing, with its rush to prediction, fundamentally rejects.