Operator-precedence parser

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.

3 more chapters are free with a Lably account.

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:

<span id="mwLQ"></span><span class="nc" id="mwLg">expression</span><span class="w" id="mwLw"> </span>::<span class="o" id="mwMA">=</span><span class="w" id="mwMQ"> </span><span class="nc" id="mwMg">equality-expression</span> <span class="nc" id="mwMw">equality-expression</span><span class="w" id="mwNA"> </span>::<span class="o" id="mwNQ">=</span><span class="w" id="mwNg"> </span><span class="nc" id="mwNw">additive-expression</span><span class="w" id="mwOA"> </span><span class="p" id="mwOQ">(</span><span class="w" id="mwOg"> </span><span class="p" id="mwOw">(</span><span class="w" id="mwPA"> </span>'<span class="o" id="mwPQ">==</span>'<span class="w" id="mwPg"> </span>|<span class="w" id="mwPw"> </span>'!<span class="o" id="mwQA">=</span>'<span class="w" id="mwQQ"> </span><span class="p" id="mwQg">)</span><span class="w" id="mwQw"> </span><span class="nc" id="mwRA">additive-expression</span><span class="w" id="mwRQ"> </span><span class="p" id="mwRg">)</span><span class="w" id="mwRw"> </span><span class="o" id="mwSA">*</span> <span class="nc" id="mwSQ">additive-expression</span><span class="w" id="mwSg"> </span>::<span class="o" id="mwSw">=</span><span class="w" id="mwTA"> </span><span class="nc" id="mwTQ">multiplicative-expression</span><span class="w" id="mwTg"> </span><span class="p" id="mwTw">(</span><span class="w" id="mwUA"> </span><span class="p" id="mwUQ">(</span><span class="w" id="mwUg"> </span>'+'<span class="w" id="mwUw"> </span>|<span class="w" id="mwVA"> </span>'-'<span class="w" id="mwVQ"> </span><span class="p" id="mwVg">)</span><span class="w" id="mwVw"> </span><span class="nc" id="mwWA">multiplicative-expression</span><span class="w" id="mwWQ"> </span><span class="p" id="mwWg">)</span><span class="w" id="mwWw"> </span><span class="o" id="mwXA">*</span> <span class="nc" id="mwXQ">multiplicative-expression</span><span class="w" id="mwXg"> </span>::<span class="o" id="mwXw">=</span><span class="w" id="mwYA"> </span><span class="nc" id="mwYQ">primary</span><span class="w" id="mwYg"> </span><span class="p" id="mwYw">(</span><span class="w" id="mwZA"> </span><span class="p" id="mwZQ">(</span><span class="w" id="mwZg"> </span>'<span class="o" id="mwZw">*</span>'<span class="w" id="mwaA"> </span>|<span class="w" id="mwaQ"> </span>'<span class="o" id="mwag">/</span>'<span class="w" id="mwaw"> </span><span class="p" id="mwbA">)</span><span class="w" id="mwbQ"> </span><span class="nc" id="mwbg">primary</span><span class="w" id="mwbw"> </span><span class="p" id="mwcA">)</span><span class="w" id="mwcQ"> </span><span class="o" id="mwcg">*</span> <span class="nc" id="mwcw">primary</span><span class="w" id="mwdA"> </span>::<span class="o" id="mwdQ">=</span><span class="w" id="mwdg"> </span>'<span class="p" id="mwdw">(</span>'<span class="w" id="mweA"> </span><span class="nc" id="mweQ">expression</span><span class="w" id="mweg"> </span>'<span class="p" id="mwew">)</span>'<span class="w" id="mwfA"> </span>|<span class="w" id="mwfQ"> </span><span class="nc" id="mwfg">NUMBER</span><span class="w" id="mwfw"> </span>|<span class="w" id="mwgA"> </span><span class="nc" id="mwgQ">VARIABLE</span><span class="w" id="mwgg"> </span>|<span class="w" id="mwgw"> </span>'-'<span class="w" id="mwhA"> </span><span class="nc" id="mwhQ">primary</span>

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.

<u id="mwlQ">parse_expression()</u> <b id="mwlg">return</b> parse_expression_1(parse_primary(), 0)

<u id="mwmA">parse_expression_1(lhs, min_precedence)</u> <i id="mwmQ">lookahead</i> := peek next token <b id="mwmg">while</b> <i id="mwmw">lookahead</i> is a binary operator whose precedence is >= <i id="mwnA">min_precedence</i> <i id="mwnQ">op</i> := <i id="mwng">lookahead</i> advance to next token <i id="mwnw">rhs</i> := <i id="mwoA">parse_primary</i> () <i id="mwoQ">lookahead</i> := peek next token <b id="mwog">while</b> <i id="mwow">lookahead</i> is a binary operator whose precedence is greater than <i id="mwpA">op</i><span typeof="mw:Nowiki" id="mwpQ">'</span>s, or a right-associative operator whose precedence is equal to <i id="mwpg">op'</i>s <i id="mwpw">rhs</i> := <i id="mwqA">parse_expression_1</i> (<i id="mwqQ">rhs</i>, precedence of <i id="mwqg">op</i> + (1 if <i id="mwqw">lookahead</i> precedence is greater, else 0)) <i id="mwrA">lookahead</i> := peek next token <i id="mwrQ">lhs</i> := the result of applying <i id="mwrg">op</i> with operands <i id="mwrw">lhs</i> and <i id="mwsA">rhs</i> <b id="mwsQ">return</b> <i id="mwsg">lhs</i>

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

<span id="mwtg"></span><span class="nc" id="mwtw">equality-expression</span><span class="w" id="mwuA"> </span>::<span class="o" id="mwuQ">=</span><span class="w" id="mwug"> </span><span class="nc" id="mwuw">additive-expression</span><span class="w" id="mwvA"> </span><span class="p" id="mwvQ">(</span><span class="w" id="mwvg"> </span>'<span class="o" id="mwvw">==</span>'<span class="w" id="mwwA"> </span>|<span class="w" id="mwwQ"> </span>'!<span class="o" id="mwwg">=</span>'<span class="w" id="mwww"> </span><span class="p" id="mwxA">)</span><span class="w" id="mwxQ"> </span><span class="nc" id="mwxg">additive-expression</span>

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:

Douglas Crockford based the JavaScript parser in JSLint on Pratt parsing.
Comparison between Python implementations of precedence climbing and Pratt parsing: "Pratt Parsing and Precedence Climbing Are the Same Algorithm" (2016) by Andy Chu
Tutorial using Rust: "Simple but Powerful Pratt Parsing" (2020) by Aleksey Kladov
Tutorial using Rust: "The Pratt Parsing Technique" (2024) by William Rågstad
Tutorial using Python: "Simple Top-Down Parsing in Python" (2008) by Fredrik Lundh Archived 2015-02-28 at the Wayback Machine
Tutorial using Java: "Pratt Parsers: Expression Parsing Made Easy" (2011) by Bob Nystrom
Implementation in C: "Crafting Interpreters" (2021), also by Bob Nystom
Implementation in C#: "Gratt: A Generic Vaughn Pratt's top-down operator precedence parser for .NET Standard" (a generic version inspired by the Java implementation presented by Bob Nystrom in "Pratt Parsers: Expression Parsing Made Easy")

Alternative methods

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.

Full parenthesization

Another approach is to first fully parenthesize the expression, inserting a number of parentheses around each operator, such that they lead to the correct precedence even when parsed with a linear, left-to-right parser. This algorithm was used in the early FORTRAN I compiler:

The Fortran I compiler would expand each operator with a sequence of parentheses. In a simplified form of the algorithm, it would

replace + and – with ))+(( and ))-((, respectively;
replace * and / with )*( and )/(, respectively;
add (( at the beginning of each expression and after each left parenthesis in the original expression; and
add )) at the end of the expression and before each right parenthesis in the original expression.

Although not obvious, the algorithm was correct, and, in the words of Knuth, “The resulting formula is properly parenthesized, believe it or not.”

Example code of a simple C application that handles parenthesisation of basic math operators (+, -, *, /, ^, ( and )):

<span id="mwAWM"></span><span class="cp" id="mwAWQ">#include</span><span class="w" id="mwAWU"> </span><span class="cpf" id="mwAWY"><stdio.h></span> <span class="cp" id="mwAWc">#include</span><span class="w" id="mwAWg"> </span><span class="cpf" id="mwAWk"><string.h></span> <span class="c1" id="mwAWo">// The command-line argument boundary is our lexer.</span> <span class="kt" id="mwAWs">int</span><span class="w" id="mwAWw"> </span><span class="nf" id="mwAW0">main</span><span class="p" id="mwAW4">(</span><span class="kt" id="mwAW8">int</span><span class="w" id="mwAXA"> </span><span class="n" id="mwAXE">argc</span><span class="p" id="mwAXI">,</span><span class="w" id="mwAXM"> </span><span class="kt" id="mwAXQ">char</span><span class="w" id="mwAXU"> </span><span class="o" id="mwAXY">*</span><span class="n" id="mwAXc">argv</span><span class="p" id="mwAXg">[])</span><span class="w" id="mwAXk"> </span><span class="p" id="mwAXo">{</span> <span class="w" id="mwAXs"> </span><span class="kt" id="mwAXw">int</span><span class="w" id="mwAX0"> </span><span class="n" id="mwAX4">i</span><span class="p" id="mwAX8">;</span> <span class="w" id="mwAYA"> </span><span class="n" id="mwAYE">printf</span><span class="p" id="mwAYI">(</span><span class="s" id="mwAYM">"(((("</span><span class="p" id="mwAYQ">);</span> <span class="w" id="mwAYU"> </span><span class="k" id="mwAYY">for</span><span class="w" id="mwAYc"> </span><span class="p" id="mwAYg">(</span><span class="n" id="mwAYk">i</span><span class="o" id="mwAYo">=</span><span class="mi" id="mwAYs">1</span><span class="p" id="mwAYw">;</span><span class="w" id="mwAY0"> </span><span class="n" id="mwAY4">i</span><span class="o" id="mwAY8">!=</span><span class="n" id="mwAZA">argc</span><span class="p" id="mwAZE">;</span><span class="w" id="mwAZI"> </span><span class="n" id="mwAZM">i</span><span class="o" id="mwAZQ">++</span><span class="p" id="mwAZU">)</span><span class="w" id="mwAZY"> </span><span class="p" id="mwAZc">{</span> <span class="w" id="mwAZg"> </span><span class="c1" id="mwAZk">// strlen(argv[i]) == 2</span> <span class="w" id="mwAZo"> </span><span class="k" id="mwAZs">if</span><span class="w" id="mwAZw"> </span><span class="p" id="mwAZ0">(</span><span class="n" id="mwAZ4">argv</span><span class="p" id="mwAZ8">[</span><span class="n" id="mwAaA">i</span><span class="p" id="mwAaE">]</span><span class="w" id="mwAaI"> </span><span class="o" id="mwAaM">&&</span><span class="w" id="mwAaQ"> </span><span class="o" id="mwAaU">!</span><span class="n" id="mwAaY">argv</span><span class="p" id="mwAac">[</span><span class="n" id="mwAag">i</span><span class="p" id="mwAak">][</span><span class="mi" id="mwAao">1</span><span class="p" id="mwAas">])</span><span class="w" id="mwAaw"> </span><span class="p" id="mwAa0">{</span> <span class="w" id="mwAa4"> </span><span class="k" id="mwAa8">switch</span><span class="w" id="mwAbA"> </span><span class="p" id="mwAbE">(</span><span class="o" id="mwAbI">*</span><span class="n" id="mwAbM">argv</span><span class="p" id="mwAbQ">[</span><span class="n" id="mwAbU">i</span><span class="p" id="mwAbY">])</span><span class="w" id="mwAbc"> </span><span class="p" id="mwAbg">{</span> <span class="w" id="mwAbk"> </span><span class="k" id="mwAbo">case</span><span class="w" id="mwAbs"> </span><span class="sc" id="mwAbw">'('</span><span class="p" id="mwAb0">:</span><span class="w" id="mwAb4"> </span><span class="n" id="mwAb8">printf</span><span class="p" id="mwAcA">(</span><span class="s" id="mwAcE">"(((("</span><span class="p" id="mwAcI">);</span><span class="w" id="mwAcM"> </span><span class="k" id="mwAcQ">continue</span><span class="p" id="mwAcU">;</span> <span class="w" id="mwAcY"> </span><span class="k" id="mwAcc">case</span><span class="w" id="mwAcg"> </span><span class="sc" id="mwAck">')'</span><span class="p" id="mwAco">:</span><span class="w" id="mwAcs"> </span><span class="n" id="mwAcw">printf</span><span class="p" id="mwAc0">(</span><span class="s" id="mwAc4">"))))"</span><span class="p" id="mwAc8">);</span><span class="w" id="mwAdA"> </span><span class="k" id="mwAdE">continue</span><span class="p" id="mwAdI">;</span> <span class="w" id="mwAdM"> </span><span class="k" id="mwAdQ">case</span><span class="w" id="mwAdU"> </span><span class="sc" id="mwAdY">'^'</span><span class="p" id="mwAdc">:</span><span class="w" id="mwAdg"> </span><span class="n" id="mwAdk">printf</span><span class="p" id="mwAdo">(</span><span class="s" id="mwAds">")^("</span><span class="p" id="mwAdw">);</span><span class="w" id="mwAd0"> </span><span class="k" id="mwAd4">continue</span><span class="p" id="mwAd8">;</span> <span class="w" id="mwAeA"> </span><span class="k" id="mwAeE">case</span><span class="w" id="mwAeI"> </span><span class="sc" id="mwAeM">'*'</span><span class="p" id="mwAeQ">:</span><span class="w" id="mwAeU"> </span><span class="n" id="mwAeY">printf</span><span class="p" id="mwAec">(</span><span class="s" id="mwAeg">"))*(("</span><span class="p" id="mwAek">);</span><span class="w" id="mwAeo"> </span><span class="k" id="mwAes">continue</span><span class="p" id="mwAew">;</span> <span class="w" id="mwAe0"> </span><span class="k" id="mwAe4">case</span><span class="w" id="mwAe8"> </span><span class="sc" id="mwAfA">'/'</span><span class="p" id="mwAfE">:</span><span class="w" id="mwAfI"> </span><span class="n" id="mwAfM">printf</span><span class="p" id="mwAfQ">(</span><span class="s" id="mwAfU">"))/(("</span><span class="p" id="mwAfY">);</span><span class="w" id="mwAfc"> </span><span class="k" id="mwAfg">continue</span><span class="p" id="mwAfk">;</span> <span class="w" id="mwAfo"> </span><span class="k" id="mwAfs">case</span><span class="w" id="mwAfw"> </span><span class="sc" id="mwAf0">'+'</span><span class="p" id="mwAf4">:</span> <span class="w" id="mwAf8"> </span><span class="c1" id="mwAgA">// unary check: either first or had an operator expecting secondary argument</span> <span class="w" id="mwAgE"> </span><span class="k" id="mwAgI">if</span><span class="w" id="mwAgM"> </span><span class="p" id="mwAgQ">(</span><span class="n" id="mwAgU">i</span><span class="w" id="mwAgY"> </span><span class="o" id="mwAgc">==</span><span class="w" id="mwAgg"> </span><span class="mi" id="mwAgk">1</span><span class="w" id="mwAgo"> </span><span class="o" id="mwAgs">||</span><span class="w" id="mwAgw"> </span><span class="n" id="mwAg0">strchr</span><span class="p" id="mwAg4">(</span><span class="s" id="mwAg8">"(^*/+-"</span><span class="p" id="mwAhA">,</span><span class="w" id="mwAhE"> </span><span class="o" id="mwAhI">*</span><span class="n" id="mwAhM">argv</span><span class="p" id="mwAhQ">[</span><span class="n" id="mwAhU">i</span><span class="mi" id="mwAhY">-1</span><span class="p" id="mwAhc">]))</span> <span class="w" id="mwAhg"> </span><span class="n" id="mwAhk">printf</span><span class="p" id="mwAho">(</span><span class="s" id="mwAhs">"+"</span><span class="p" id="mwAhw">);</span> <span class="w" id="mwAh0"> </span><span class="k" id="mwAh4">else</span> <span class="w" id="mwAh8"> </span><span class="n" id="mwAiA">printf</span><span class="p" id="mwAiE">(</span><span class="s" id="mwAiI">")))+((("</span><span class="p" id="mwAiM">);</span> <span class="w" id="mwAiQ"> </span><span class="k" id="mwAiU">continue</span><span class="p" id="mwAiY">;</span> <span class="w" id="mwAic"> </span><span class="k" id="mwAig">case</span><span class="w" id="mwAik"> </span><span class="sc" id="mwAio">'-'</span><span class="p" id="mwAis">:</span> <span class="w" id="mwAiw"> </span><span class="k" id="mwAi0">if</span><span class="w" id="mwAi4"> </span><span class="p" id="mwAi8">(</span><span class="n" id="mwAjA">i</span><span class="w" id="mwAjE"> </span><span class="o" id="mwAjI">==</span><span class="w" id="mwAjM"> </span><span class="mi" id="mwAjQ">1</span><span class="w" id="mwAjU"> </span><span class="o" id="mwAjY">||</span><span class="w" id="mwAjc"> </span><span class="n" id="mwAjg">strchr</span><span class="p" id="mwAjk">(</span><span class="s" id="mwAjo">"(^*/+-"</span><span class="p" id="mwAjs">,</span><span class="w" id="mwAjw"> </span><span class="o" id="mwAj0">*</span><span class="n" id="mwAj4">argv</span><span class="p" id="mwAj8">[</span><span class="n" id="mwAkA">i</span><span class="mi" id="mwAkE">-1</span><span class="p" id="mwAkI">]))</span> <span class="w" id="mwAkM"> </span><span class="n" id="mwAkQ">printf</span><span class="p" id="mwAkU">(</span><span class="s" id="mwAkY">"-"</span><span class="p" id="mwAkc">);</span> <span class="w" id="mwAkg"> </span><span class="k" id="mwAkk">else</span> <span class="w" id="mwAko"> </span><span class="n" id="mwAks">printf</span><span class="p" id="mwAkw">(</span><span class="s" id="mwAk0">")))-((("</span><span class="p" id="mwAk4">);</span> <span class="w" id="mwAk8"> </span><span class="k" id="mwAlA">continue</span><span class="p" id="mwAlE">;</span> <span class="w" id="mwAlI"> </span><span class="p" id="mwAlM">}</span> <span class="w" id="mwAlQ"> </span><span class="p" id="mwAlU">}</span> <span class="w" id="mwAlY"> </span><span class="n" id="mwAlc">printf</span><span class="p" id="mwAlg">(</span><span class="s" id="mwAlk">"%s"</span><span class="p" id="mwAlo">,</span><span class="w" id="mwAls"> </span><span class="n" id="mwAlw">argv</span><span class="p" id="mwAl0">[</span><span class="n" id="mwAl4">i</span><span class="p" id="mwAl8">]);</span> <span class="w" id="mwAmA"> </span><span class="p" id="mwAmE">}</span> <span class="w" id="mwAmI"> </span><span class="n" id="mwAmM">printf</span><span class="p" id="mwAmQ">(</span><span class="s" id="mwAmU">"))))</span><span class="se" id="mwAmY">\n</span><span class="s" id="mwAmc">"</span><span class="p" id="mwAmg">);</span> <span class="w" id="mwAmk"> </span><span class="k" id="mwAmo">return</span><span class="w" id="mwAms"> </span><span class="mi" id="mwAmw">0</span><span class="p" id="mwAm0">;</span> <span class="p" id="mwAm4">}</span>

First, you need to compile your program. Assuming your program is written in C and the source code is in a file named program.c, you would use the following command:

gcc program.c -o program

The above command tells gcc to compile program.c and create an executable named program.

Command to run the program with parameters, For example; a * b + c ^ d / e

./program a '*' b + c '^' d / e

it produces

((((a))*((b)))+(((c)^(d))/((e))))

as output on the console.

A limitation to this strategy is that unary operators must all have higher precedence than infix operators. The "negative" operator in the above code has a higher precedence than exponentiation. Running the program with this input

- a ^ 2

produces this output

((((-a)^(2))))

which is probably not what is intended.