Operator precedence parsing refers to a family of parsing techniques used to handle expressions containing operators with different precedence and associativity. Notable algorithms in this family include:
These algorithms share similarities and can be considered variations of the same fundamental approach with different formulations and implementations. 1 2
Motivation
We can describe the structure of our language using context-free grammar (often using BNF notation) and parse it with recursive descent parsers. However, for infix operators, this approach can be really cumbersome. Consider the following grammar:
Expr ::=
Expr '+' Expr
| Expr '*' Expr
| '(' Expr ')'
| 'number'
This grammar is ambiguous to parse, as it doesn’t express the precedence and associativity of the operators. We can fix the grammar with the following change:
Expr ::=
Factor
| Expr '+' Factor
Factor ::=
Atom
| Factor '*' Atom
Atom ::=
'number'
| '(' Expr ')'
This can quickly become unwieldy with more operators and more complicated precedence rules. The above fix also haven’t address the issue that some of the non-terminal in the grammar is left recursive, which can cause trouble for pure recursive-descent parsing 3.