Парсеры на основе приоритета операторов

Bottom up parser that interprets an operator precedence grammar
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.

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; consequently, an operator precedence parser must be run on the program after parsing of all referenced modules.) Raku sandwiches an operator precedence parser between two recursive descent parsers in order to achieve a balance of speed and dynamism. GCC's C and C++ parsers, which are hand coded recursive descent parsers, are both sped 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.

There are other ways to apply operator precedence rules. One is to build a tree of the original expression and then apply tree rewrite rules to it. Such trees do not necessarily need to be implemented using data structures conventionally used for trees. 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.