<p>I've come across the term “Pratt parsing”. The only thing I know is that it's an algorithm (or a pattern, a technique) used to parse expressions.</p>
<p>How does it work? I'd like to see the intuition behind the algorithm, not just a series of steps to perform. What problems does this technique actually solve, and at what cost? How is it different from other well-known traditional/basic parsing strategies? Has it been “superseded” (at least in some aspects) by better techniques?</p>

<parsing>
What exactly is Pratt parsing used for and how does it work?
CC BY-SA 4.0
2023-11-28T17:02:57.797Z
A discussion you might find interesting: https://www.reddit.com/r/ProgrammingLanguages/comments/16vqbey/alternatives_to_the_shunting_yard_algorithm_for/?rdt=56610
Erik Eidt
CC BY-SA 4.0
2023-11-28T18:04:05.730Z
I'm surprised this hadn't already been asked!
kaya3
CC BY-SA 4.0
2023-11-28T21:00:13.770Z
also: https://journal.stuffwithstuff.com/2011/03/19/pratt-parsers-expression-parsing-made-easy/
cody
CC BY-SA 4.0
2023-11-29T21:10:28.437Z
also: https://matklad.github.io/2020/04/13/simple-but-powerful-pratt-parsing.html
Luiz Felipe
<h2>Motivation</h2>
<blockquote>
<p>What problems does this technique actually solve, and at what cost?</p>
</blockquote>
<p>In a BNF grammar, you need a nonterminal for each level of operator precedence.</p>
<p> ⟨<em>additive</em>⟩ =<br />
  ⟨<em>multiplicative</em>⟩ ( (<code>+</code> | <code>-</code>) ⟨<em>multiplicative</em>⟩ )*</p>
<p> ⟨<em>multiplicative</em>⟩ =<br />
  ⟨<em>unary</em>⟩ ( (<code>*</code> | <code>/</code>) ⟨<em>unary</em>⟩ )*</p>
<p> ⟨<em>unary</em>⟩ =<br />
  (<code>+</code> | <code>-</code>) ⟨<em>term</em>⟩</p>
<p> ⟨<em>term</em>⟩ =<br />
  ⟨<em>number</em>⟩ | ⟨<em>variable</em>⟩</p>
<p>If you translate this to a recursive-descent parser, each nonterminal becomes a function. In pseudo-Python:</p>
<pre><code>def accept_additive():
    lhs = accept_multiplicative()
    if lhs is None:
        return None

    while True:
        op = accept_additive_operator()
        if op is None:
            break
        rhs = expect_multiplicative()
        lhs = Binary(op, lhs, rhs)

    return lhs

def accept_additive_operator():
    return accept_token('+') or accept_token('-')

def expect_multiplicative():
    e = accept_multiplicative()
    if e is None:
        raise ParseError()
    return e

def accept_multiplicative():
    ...

def accept_multiplicative_operator():
    ...

def expect_unary():
    ...

def accept_unary():
    ...

def accept_unary_operator():
    ...

def expect_term():
    ...

def accept_term():
    return accept_number() or accept_variable()
</code></pre>
<p>So it takes many nested calls to reach the parsers for the leaves of the AST: before the parser even consumes a character, it must go down the chain of <code>accept_additive()</code> → <code>accept_multiplicative()</code> → <code>accept_unary()</code> → <code>accept_term()</code>, most of which is unproductive.</p>
<h2>Solution</h2>
<blockquote>
<p>How does it work?</p>
</blockquote>
<blockquote>
<p>How is it different from other well-known traditional/basic parsing strategies?</p>
</blockquote>
<p>In <a href="https://dl.acm.org/doi/10.1145/512927.512931" rel="noreferrer">Top-Down Operator Precedence Parsing</a>, Vaughan Pratt devised a method of simplifying this pattern, in a way that integrates well with recursive descent parsing.</p>
<p>The technique is to add a precedence table, which associates each operator token with a few properties:</p>
<ul>
<li><p>“Left binding power” (LBP), an integer precedence level</p>
</li>
<li><p>“Null denotation” (NUD), a function to parse it in prefix position (nothing to its left)</p>
</li>
<li><p>“Left denotation” (LED), a function to parse it in infix position (something to its left)</p>
</li>
</ul>
<p>The chain of calls is replaced by a single loop that uses the token to dispatch to the appropriate parser immediately, skipping over the irrelevant precedence levels. In this case, the precedence levels are these.</p>
<ol start="0">
<li>Literal / Minimum</li>
<li>Additive</li>
<li>Multiplicative / Maximum</li>
</ol>
<p>So the table looks like this. Notice that there’s an extra “end” marker token with minimum precedence.</p>
<div class="s-table-container">
<table class="s-table">
<thead>
<tr>
<th>Token</th>
<th>Precedence (LBP)</th>
<th>Prefix (NUD)</th>
<th>Infix (LED)</th>
</tr>
</thead>
<tbody>
<tr>
<td><code>*</code></td>
<td>Multiplicative (2)</td>
<td><code>None</code></td>
<td><code>mul_led</code></td>
</tr>
<tr>
<td><code>/</code></td>
<td>Multiplicative (2)</td>
<td><code>None</code></td>
<td><code>div_led</code></td>
</tr>
<tr>
<td><code>+</code></td>
<td>Additive (1)</td>
<td><code>add_nud</code></td>
<td><code>add_led</code></td>
</tr>
<tr>
<td><code>-</code></td>
<td>Additive (1)</td>
<td><code>sub_nud</code></td>
<td><code>sub_led</code></td>
</tr>
<tr>
<td>Number</td>
<td>Literal (0)</td>
<td><code>num_nud</code></td>
<td><code>None</code></td>
</tr>
<tr>
<td>Variable</td>
<td>Literal (0)</td>
<td><code>var_nud</code></td>
<td><code>None</code></td>
</tr>
<tr>
<td>End</td>
<td>Minimum (0)</td>
<td><code>None</code></td>
<td><code>None</code></td>
</tr>
</tbody>
</table>
</div>
<p><code>None</code> indicates cases where a parse error could occur, so this also allows context-sensitive error reporting.</p>
<p>The top-level expression parser can now work iteratively. It’s parameterised by a “<em>right</em> binding power” (RBP), which starts at the minimum precedence level when parsing a top-level expression. It grabs a token and tries to parse it as a prefix operator, then repeatedly tries to parse infix expressions above the current precedence level.</p>
<pre><code>def accept_expression(rbp):
    current = next_token()
    lhs = table[current].nud()
    while table[current].lbp &gt; rbp:
        operator = current
        current = next_token()
        lhs = table[operator].led(lhs)
    return lhs
</code></pre>
<p>This is the sense in which it’s “top-down”: like the recursive descent parser, it considers the lowest-precedence operators first, and makes recursive calls at higher precedence levels. The definitions of the individual operator parsers, where this recursion actually happens, are quite mechanical:</p>
<pre><code>def add_nud():
    return expect_expression(PREC_MAX)

def add_led(lhs):
    return Binary('+', lhs, expect_expression(PREC_ADD))
</code></pre>
<p>A right-associative operator would use a lower precedence than the current level; for example, take exponentiation:</p>
<pre><code>def exp_led(lhs):
    return Binary('^', lhs, expect_expression(PREC_EXP - 1))
</code></pre>
<h2>Conclusion</h2>
<blockquote>
<p>Has it been “superseded” (at least in some aspects) by better techniques?</p>
</blockquote>
<p>Mostly it hasn’t. Parser generators like <a href="https://monlih.github.io/happy-docs/" rel="noreferrer">Happy</a> and parser combinator libraries like <a href="https://hackage.haskell.org/package/megaparsec" rel="noreferrer">Megaparsec</a> do have some facilities for handling operator precedence automatically. However, you may still need to write a recursive descent parser by hand in order to gracefully recover from errors and produce helpful feedback. In that case, Pratt parsing is a nice technique for simplifying the parser and improving its performance compared to naïve RD. It readily admits user-defined operators, by just allowing the precedence table to be extended, and it works equally well in imperative and functional style.</p>
<p>Finally, operator-precedence grammars can describe a fairly large class of languages, too, so it’s also quite possible to parse a language <em>entirely</em> with this technique, or only modest extensions. For example, I once wrote a language where <code>if</code> was considered a prefix binary operator and <code>else</code> an infix binary operator, with precedence and associativity defined so that <code>if A B else if C D else E</code> would parse as <code>(if A B) else ((if C D) else E)</code>.</p>

CC BY-SA 4.0
2023-12-01T03:11:39.743Z
2023-12-01T03:11:39.743Z
Jon Purdy
CC BY-SA 4.0
2023-12-17T15:26:19.410Z
There is currently an effort in the Ruby community to replace the aging "Flex/Bison-with-lots-of-hand-written-code" parser of YARV, which due to Ruby's complex syntax also ended up being used by every other Ruby implementation (despite the fact it is not designed for re-use and intimately tied to YARV), with a new parser that is designed for re-use, has no dependencies on YARV, and can be used by all other Ruby implementations as well as refactoring tools, IDEs, linters, syntax highlighters, etc. It is called Prism and is a hand-written Pratt-style TDOP parser: https://github.com/ruby/prism/
Jörg W Mittag
# What exactly is Pratt parsing used for and how does it work?
Posted by: username_0 on 2023-11-28
I've come across the term “Pratt parsing”. The only thing I know is that it's an algorithm (or a pattern, a technique) used to parse expressions.

How does it work? I'd like to see the intuition behind the algorithm, not just a series of steps to perform. What problems does this technique actually solve, and at what cost? How is it different from other well-known traditional/basic parsing strategies? Has it been “superseded” (at least in some aspects) by better techniques?
**Tags:** parsing
> **Comments:**
> **username_1**: A discussion you might find interesting: https://www.reddit.com/r/ProgrammingLanguages/comments/16vqbey/alternatives_to_the_shunting_yard_algorithm_for/?rdt=56610  
> **username_2**: I'm surprised this hadn't already been asked!  
> **username_3**: also: https://journal.stuffwithstuff.com/2011/03/19/pratt-parsers-expression-parsing-made-easy/  
> **username_4**: also: https://matklad.github.io/2020/04/13/simple-but-powerful-pratt-parsing.html  
---
## 1 answers
### Answer by username_5 on 2023-12-01. Score: 13 | Accepted answer
Motivation

What problems does this technique actually solve, and at what cost?

In a BNF grammar, you need a nonterminal for each level of operator precedence.
 ⟨additive⟩ =
  ⟨multiplicative⟩ ( (+ | -) ⟨multiplicative⟩ )*
 ⟨multiplicative⟩ =
  ⟨unary⟩ ( (* | /) ⟨unary⟩ )*
 ⟨unary⟩ =
  (+ | -) ⟨term⟩
 ⟨term⟩ =
  ⟨number⟩ | ⟨variable⟩
If you translate this to a recursive-descent parser, each nonterminal becomes a function. In pseudo-Python:
def accept_additive():
    lhs = accept_multiplicative()
    if lhs is None:
        return None

    while True:
        op = accept_additive_operator()
        if op is None:
            break
        rhs = expect_multiplicative()
        lhs = Binary(op, lhs, rhs)

    return lhs

def accept_additive_operator():
    return accept_token('+') or accept_token('-')

def expect_multiplicative():
    e = accept_multiplicative()
    if e is None:
        raise ParseError()
    return e

def accept_multiplicative():
    ...

def accept_multiplicative_operator():
    ...

def expect_unary():
    ...

def accept_unary():
    ...

def accept_unary_operator():
    ...

def expect_term():
    ...

def accept_term():
    return accept_number() or accept_variable()

So it takes many nested calls to reach the parsers for the leaves of the AST: before the parser even consumes a character, it must go down the chain of accept_additive() → accept_multiplicative() → accept_unary() → accept_term(), most of which is unproductive.
Solution

How does it work?


How is it different from other well-known traditional/basic parsing strategies?

In Top-Down Operator Precedence Parsing, Vaughan Pratt devised a method of simplifying this pattern, in a way that integrates well with recursive descent parsing.
The technique is to add a precedence table, which associates each operator token with a few properties:

“Left binding power” (LBP), an integer precedence level

“Null denotation” (NUD), a function to parse it in prefix position (nothing to its left)

“Left denotation” (LED), a function to parse it in infix position (something to its left)


The chain of calls is replaced by a single loop that uses the token to dispatch to the appropriate parser immediately, skipping over the irrelevant precedence levels. In this case, the precedence levels are these.

Literal / Minimum
Additive
Multiplicative / Maximum

So the table looks like this. Notice that there’s an extra “end” marker token with minimum precedence.




Token
Precedence (LBP)
Prefix (NUD)
Infix (LED)




*
Multiplicative (2)
None
mul_led


/
Multiplicative (2)
None
div_led


+
Additive (1)
add_nud
add_led


-
Additive (1)
sub_nud
sub_led


Number
Literal (0)
num_nud
None


Variable
Literal (0)
var_nud
None


End
Minimum (0)
None
None




None indicates cases where a parse error could occur, so this also allows context-sensitive error reporting.
The top-level expression parser can now work iteratively. It’s parameterised by a “right binding power” (RBP), which starts at the minimum precedence level when parsing a top-level expression. It grabs a token and tries to parse it as a prefix operator, then repeatedly tries to parse infix expressions above the current precedence level.
def accept_expression(rbp):
    current = next_token()
    lhs = table[current].nud()
    while table[current].lbp > rbp:
        operator = current
        current = next_token()
        lhs = table[operator].led(lhs)
    return lhs

This is the sense in which it’s “top-down”: like the recursive descent parser, it considers the lowest-precedence operators first, and makes recursive calls at higher precedence levels. The definitions of the individual operator parsers, where this recursion actually happens, are quite mechanical:
def add_nud():
    return expect_expression(PREC_MAX)

def add_led(lhs):
    return Binary('+', lhs, expect_expression(PREC_ADD))

A right-associative operator would use a lower precedence than the current level; for example, take exponentiation:
def exp_led(lhs):
    return Binary('^', lhs, expect_expression(PREC_EXP - 1))

Conclusion

Has it been “superseded” (at least in some aspects) by better techniques?

Mostly it hasn’t. Parser generators like Happy and parser combinator libraries like Megaparsec do have some facilities for handling operator precedence automatically. However, you may still need to write a recursive descent parser by hand in order to gracefully recover from errors and produce helpful feedback. In that case, Pratt parsing is a nice technique for simplifying the parser and improving its performance compared to naïve RD. It readily admits user-defined operators, by just allowing the precedence table to be extended, and it works equally well in imperative and functional style.
Finally, operator-precedence grammars can describe a fairly large class of languages, too, so it’s also quite possible to parse a language entirely with this technique, or only modest extensions. For example, I once wrote a language where if was considered a prefix binary operator and else an infix binary operator, with precedence and associativity defined so that if A B else if C D else E would parse as (if A B) else ((if C D) else E).
> **Comments:**
> **username_6** (2023-12-17): There is currently an effort in the Ruby community to replace the aging "Flex/Bison-with-lots-of-hand-written-code" parser of YARV, which due to Ruby's complex syntax also ended up being used by every other Ruby implementation (despite the fact it is not designed for re-use and intimately tied to YARV), with a new parser that is designed for re-use, has no dependencies on YARV, and can be used by all other Ruby implementations as well as refactoring tools, IDEs, linters, syntax highlighters, etc. It is called Prism and is a hand-written Pratt-style TDOP parser: https://github.com/ruby/prism/  
---
