Operator-precedence parser

Edsger Dijkstra's shunting yard algorithm is commonly used to implement operator-precedence parsers.

More precisely, the operator-precedence parser can parse all LR(1) grammars where two consecutive nonterminals and epsilon never appear in the right-hand side of any rule.

(An example is Haskell, which allows user-defined infix operators with custom associativity and precedence; consequently, an operator-precedence parser must be run on the program after parsing of all referenced modules.)

[1] The precedence climbing method is a compact, efficient, and flexible algorithm for parsing expressions that was first described by Martin Richards and Colin Whitby-Strevens.

Parsing a number, for example, can require five function calls: one for each non-terminal in the grammar until reaching primary.

It assumes that the primary nonterminal is parsed in a separate subroutine, like in a recursive descent parser.

[4] Pratt designed the parser originally to implement the CGOL programming language, and it was treated in much more depth in a Masters Thesis under his supervision.

Instead, tokens can be stored in flat structures, such as tables, by simultaneously building a priority list which states what elements to process in which order.