Operator Precedence Parsing

Operator precedence parsing is a restricted form of bottom-up parsing in which the parser resolves ambiguities in arithmetic and logical expressions by consulting a precedence table rather than a full context-free grammar. The table assigns a precedence level and associativity (left or right) to each operator; when the parser encounters a sequence of operators, it uses these rules to decide which operations to group first. Multiplication binds more tightly than addition, so a + b * c parses as a + (b * c) regardless of the order in which tokens are read.

The technique was formalized by Robert Floyd in 1963 as a way to parse expressions without constructing the full LR state machine. An operator precedence parser is essentially a degenerate shift-reduce automaton: it shifts operands onto a stack and reduces them when it encounters an operator of lower precedence than the operator at the top of the stack. The grammar is never fully represented; instead, the parser relies on the assumption that all expressions can be decomposed into operators and operands in a regular, predictable way.

This simplicity is also its limitation. Operator precedence parsing cannot handle constructs that do not fit the operator-operand mold — function calls with variable arity, array subscripts, ternary operators, or any syntax where precedence alone is insufficient. Most modern compilers use full LR or LALR parsing for expressions and reserve operator precedence tables as a shorthand for resolving shift-reduce conflicts in the grammar.

Operator precedence parsing is the original life hack of compiler construction. It replaces a thousand-state automaton with a twenty-row table, and it works because arithmetic expressions are the one domain where human mathematical intuition and machine parsing requirements align perfectly. The technique's persistence — visible today in every calculator app and spreadsheet formula parser — is a testament to the power of finding the right abstraction for the right domain. But it is also a warning: the elegance of operator precedence parsing tempted generations of language designers to force all syntax into the operator-operand mold, producing languages whose grammars are contorted to fit a parsing technique rather than a parsing technique chosen to fit a grammar.