Operator-precedence parser

In computer science, an operator precedence parser is a bottom-up parser that interprets an operator-precedence grammar. For example, most calculators use operator precedence parsers to convert from the human-readable infix notation relying on order of operations to a format that is optimized for evaluation such as Reverse Polish notation (RPN).

Edsger Dijkstra's shunting yard algorithm is commonly used to implement operator precedence parsers. Other algorithms include the precedence climbing method and the top down operator precedence method.

An operator-precedence parser is a simple shift-reduce parser that is capable of parsing a subset of LR(1) grammars. 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.

Operator-precedence parsers are not used often in practice; however they do have some properties that make them useful within a larger design. First, they are simple enough to write by hand, which is not generally the case with more sophisticated right shift-reduce parsers. Second, they can be written to consult an operator table at run time, which makes them suitable for languages that can add to or change their operators while parsing. (An example is Haskell, which allows user-defined infix operators with custom associativity and precedence; consequentially, an operator-precedence parser must be run on the program after parsing of all referenced modules.)

Perl 6 sandwiches an operator-precedence parser between two Recursive descent parsers in order to achieve a balance of speed and dynamism. This is expressed in the virtual machine for Perl 6, Parrot, as the Parser Grammar Engine (PGE). GCC's C and C++ parsers, which are hand-coded recursive descent parsers, are both speed up by an operator-precedence parser that can quickly examine arithmetic expressions. Operator precedence parsers are also embedded within compiler compiler-generated parsers to noticeably speed up the recursive descent approach to expression parsing.

...
Wikipedia