computer science

Operator-precedence parser

Operator-precedence parser is a computer science topic covered in the lgStudy science library. This page brings together a partial reference excerpt, illustrations, worked examples, real-world applications and a short study plan, so you can understand Operator-precedence parser rather than just read about it. In short: 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).

Key takeaways

Operator-precedence parser belongs to computer science; place it in that map before memorising details.
Learn the definition first, then one example that makes the definition concrete.
Connect Operator-precedence parser to a quantity you can measure, compute or draw — that is where exam questions come from.
Reproduce the core statement of Operator-precedence parser from memory before moving on to harder problems.

Reference excerpt

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.

Relationship to other 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.

Precedence climbing method 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. An infix-notation expression grammar in EBNF format will usually look like this:

With many levels of precedence, implementing this grammar with a predictive recursive-descent parser can become inefficient. Parsing a number, for example, can require five function calls: one for each non-terminal in the grammar until reaching primary. An operator-precedence parser can do the same more efficiently. The idea is that we can left associate the arithmetic operations as long as we find operators with the same precedence, but we have to save a temporary result to evaluate higher precedence operators. The algorithm that is presented here does not need an explicit stack; instead, it uses recursive calls to implement the stack. The algorithm is not a pure operator-precedence parser like Edsger Dijkstra's shunting yard algorithm. It assumes that the primary nonterminal is parsed in a separate subroutine, like in a recursive descent parser.

Pseudocode The pseudocode for the algorithm is as follows. The parser starts at function parse_expression. Precedence levels are greater than or equal to 0.

parse_expression() return parse_expression_1(parse_primary(), 0)

parse_expression_1(lhs, min_precedence) lookahead := peek next token while lookahead is a binary operator whose precedence is >= min_precedence op := lookahead advance to next token rhs := parse_primary () lookahead := peek next token while lookahead is a binary operator whose precedence is greater than op's, or a right-associative operator whose precedence is equal to op's rhs := parse_expression_1 (rhs, precedence of op + (1 if lookahead precedence is greater, else 0)) lookahead := peek next token lhs := the result of applying op with operands lhs and rhs return lhs

Note that in the case of a production rule like this (where the operator can only appear once):

the algorithm must be modified to accept only binary operators whose precedence is > min_precedence.

Example execution of the algorithm An example execution on the expression 2 + 3 * 4 + 5 == 19 is as follows. We give precedence 0 to equality expressions, 1 to additive expressions, 2 to multiplicative expressions. parse_expression_1 (lhs = 2, min_precedence = 0)

the lookahead token is +, with precedence 1. the outer while loop is entered. op is + (precedence 1) and the input is advanced rhs is 3 the lookahead token is *, with precedence 2. the inner while loop is entered.parse_expression_1 (lhs = 3, min_precedence = 2) the lookahead token is *, with precedence 2. the outer while loop is entered. op is * (precedence 2) and the input is advanced rhs is 4 the next token is +, with precedence 1. the inner while loop is not entered. lhs is assigned 3*4 = 12 the next token is +, with precedence 1. the outer while loop is left. 12 is returned. the lookahead token is +, with precedence 1. the inner while loop is not entered. lhs is assigned 2+12 = 14 the lookahead token is +, with precedence 1. the outer while loop is not left. op is + (precedence 1) and the input is advanced rhs is 5 the next token is ==, with precedence 0. the inner while loop is not entered. lhs is assigned 14+5 = 19 the next token is ==, with precedence 0. the outer while loop is not left. op is == (precedence 0) and the input is advanced rhs is 19 the next token is end-of-line, which is not an operator. the inner while loop is not entered. lhs is assigned the result of evaluating 19 == 19, for example 1 (as in the C standard). the next token is end-of-line, which is not an operator. the outer while loop is left. 1 is returned.

Pratt parsing

Another precedence parser known as Pratt parsing was first described by Vaughan Pratt in the 1973 paper "Top Down Operator Precedence", based on recursive descent. Though it predates precedence climbing, it can be viewed as a generalization of precedence climbing. 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. Tutorials and implementations:

… excerpt ends here. Continue reading the full article.

Worked examples

Example 1 — a first encounter with Operator-precedence parser

Start with the simplest possible case. Write down what Operator-precedence parser claims or describes in one sentence, then invent the smallest concrete situation in which that sentence is true. In computer science, the smallest case is usually a single object, a single equation or a single measurement. Check that every symbol or term in your sentence has a meaning in that case.

Example 2 — changing one variable

Take the situation from Example 1 and change exactly one quantity: double it, halve it, or set it to zero. Predict what should happen to Operator-precedence parser before you calculate. Comparing your prediction with the result is the fastest way to find out whether you understand the idea or only the words.

Example 3 — an exam-style question

Typical questions about Operator-precedence parser ask you to (a) state it precisely, (b) apply it to given data, and (c) explain a limitation. Practise writing all three answers in under five minutes; the third part is what separates a full-mark answer from an average one.

Applications of Operator-precedence parser

In research: Operator-precedence parser appears in computer science research whenever the underlying quantities have to be modelled precisely. Papers usually cite it as a starting assumption and then explore where it breaks down.
In technology and industry: Engineering practice reuses Operator-precedence parser in design rules, simulations and safety margins. Knowing the idea lets you read a specification sheet and understand why the numbers look the way they do.
In the classroom: Operator-precedence parser is common in secondary-school and first-year university syllabi. It links to neighbouring topics Parsing algorithms, so understanding it makes those chapters shorter.
In everyday life: Look for Operator-precedence parser outside the textbook — in sport, cooking, traffic, electronics or the sky above you. An example you found yourself is remembered far longer than one you were given.

Affiliate

Preply — study more efficiently by working with a personal tutor. 50% off.

How to study Operator-precedence parser in 20 minutes

Read the reference excerpt below once, without taking notes.
Close the page and write down what Operator-precedence parser means in your own words.
Compare your version with the excerpt and mark what you missed.
Work through the three examples above with pen and paper.
Explain Operator-precedence parser out loud to somebody else — or to Teacher Smith in the lgStudy chat.

Frequently asked questions

What is Operator-precedence parser in simple terms?

Why does Operator-precedence parser matter?

Because it connects several computer science ideas at once: it gives you a definition you can apply, a quantity you can calculate, and a way to check whether a result is plausible.

How should I study Operator-precedence parser?

Read the excerpt, restate it from memory, then work through the examples and applications listed on this page. The five-step study plan above takes about twenty minutes.

What does this page cover?

It gives you a compact reference excerpt plus original lgStudy explanations, examples, applications and study material on Operator-precedence parser.