View source for 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|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 <code>a + b * c</code> parses as <code>a + (b * c)</code> 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 parser|LR]] state machine. An operator precedence parser is essentially a degenerate [[Shift-Reduce Conflict|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 [[compiler]]s use full [[LR parser|LR]] or [[LALR parser|LALR]] parsing for expressions and reserve operator precedence tables as a shorthand for resolving [[Shift-Reduce Conflict|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.''

See also: [[Parser]], [[Shift-Reduce Conflict]], [[LR parser]], [[LALR parser]], [[Compiler]], [[Context-Free Grammar]], [[Grammar]], [[Parser Generator]], [[Expression Grammar]]

[[Category:Computer Science]]
[[Category:Compilers]]
[[Category:Formal Languages]]