<p>The <a href="https://en.wikipedia.org/wiki/Shunting_yard_algorithm" rel="nofollow noreferrer">shunting yard algorithm</a> is used to parse infix expressions into a syntax tree, or prefix/postfix notation. Wikipedia provides pseudocode for how to implement it, but notes:</p>
<blockquote>
<p>This implementation does not implement composite functions, functions with a variable number of arguments, or unary operators.</p>
</blockquote>
<p>Extending it to include functions with a variable number of arguments is fairly straightforward:</p>
<ul>
<li>In the operator stack, store each operator's arity alongside the operator itself.</li>
<li>When you see a comma, after reaching the <code>(</code>, assert that the item in the operator stack immediately below that is a function name, and then increment its arity.</li>
</ul>
<p>However, implementing curried functions is less obvious. Because functions need to be pushed to the operator stack, it's impossible for the result of any subexpression to itself be a function that's called.</p>
<p>Can the shunting yard algorithm be easily extended to handle this? If so, how? If not, what alternatives are there?</p>

<parsing>
How can the shunting yard algorithm be adapted to handle currying?
CC BY-SA 4.0
2023-08-03T00:15:08.437Z
I was about to edit this to eliminate the annoying horizontal scrolling, but it looks like that formatting was very deliberate.  ???
Ray Butterworth
CC BY-SA 4.0
2023-08-03T01:45:54.173Z
@RayButterworth That's where the line break appears in the Wikipedia article, at least on my screen.
Bbrk24
CC BY-SA 4.0
2023-08-03T03:18:58.700Z
Yes, but is that line break significant?  Why not simply quote it using ">" so that it can all be seen without horizontal scrolling.
Ray Butterworth
CC BY-SA 4.0
2023-08-03T18:36:32.230Z
isn't that the case with any partially applied function, or with any function that returns a function??
njzk2
<p>There's generally no reason to use the shunting-yard algorithm for actual parsing from tokens, and it's rare to do so. It doesn't give the opportunity for good error reporting, and on its own it even still accepts invalid syntax for infix expressions. True shunting-yard algorithm parsers have trouble with things like <code>1 2 +</code> (not rejected!) and mistaking grouping parentheses for function-application parentheses, and vice-versa; at the very least you need a covering parser to produce reasonable error messages.</p>
<p>There are extensions that do better, notably <a href="https://en.wikipedia.org/wiki/Operator-precedence_parser" rel="noreferrer">operator-precedence parsers</a>. These delegate recursively to other parsing functions that consume and process expressions, returning parse nodes representing them. Each delegated function takes in a whole expression for as long as the operators it sees have higher precedence than where it started, and then returns what it's produced to the caller. The pure approach here is to treat function application as a very-high-precedence postfix operator; you can legitimately treat it as a separate category of thing too.</p>
<hr />
<p>Another approach is to have functions for parsing an expression excluding any operators — so function or method calls and any literals of the language — and when parsing operator expressions, loop around performing the shunting-yard algorithm <em>on whole terms</em> as you go. This is what I did <a href="https://github.com/mwh/kernan/blob/a176ef4998c9b7541f3f5fb444d6be5e64036ce7/GraceLanguage/Parsing/Parser.cs#L1437" rel="noreferrer">here</a>, for a language where only the four core arithmetic operators could be used together and combining other or user-defined operators was a syntax error. This can be helpful for keeping the logic in one place when you're writing it by hand, and slots into an existing recursive-descent parser.</p>
<hr />
<p>The ideal (but theoretically unprincipled) approach is to produce an interleaved list of terms (AST nodes) and operators, and then apply the shunting-yard algorithm to that. In this approach, function calls are parsed into the appropriate function-call AST node early, as are numeric literals or any other non-operator expression terms, and it's those AST nodes that go onto the value stack during the precedence-resolving phase.</p>
<p>This fits in tidily with an overall recursive-descent approach. Have separate branches for parsing an expression term with and without operators, then when parsing operator expressions, take in a single term and look ahead for an operator after it: if it's there, loop around and take the next term the same way. Once there are no more operators, there is a list of terms (that is, ordinary AST nodes) and operator symbols, and you can perform the shunting-yard algorithm to build the expression tree with the right precedence.</p>
<hr />
<p>Either of these last two ways allows rejecting invalid syntax for the right reasons at the right time, because, for example, arguments are definitively being parsed as arguments. It also allows for more complex user-defined operator situations, like ones whose precedence isn't defined until later. They also provide more help to <em>you</em> as the implementer when you need to debug things, because you have more information and state recorded to diagnose with.</p>
<p>These approaches are a relatively short distance from where you are, but there are whole other families of parser that also deal with operators within their own style.
I would not recommend using the shunting-yard algorithm itself for the actual parsing from tokens in a programming language, though it could be useful in a resource-constrained system that knew all input would be well-formed.</p>

CC BY-SA 4.0
2023-08-02T23:56:47.350Z
2023-08-02T23:56:47.350Z
Michael Homer
CC BY-SA 4.0
2023-08-03T11:35:05.797Z
An edge case worth considering is prefix operators with low precedence, such as `not` in Python. For example, `x + not y` is supposed to be a syntax error because `not` has lower precedence than `+`. I think this would be even more complicated for low-precedence postfix operators, because the parser doesn't even know that `x + y foo` (where `foo` is postfix and lower precedence than `+`) is a single term until it looks past the `+`.
kaya3
<p>I think you could use a a mix of Recursive Descent and Shunting Yard/Pratt/Precedence Climbing (these all are the same algorithm). Also, using Shunting Yard does not mean sacrificing error reporting. Most implementations don't, but there's nothing forcing you to skip it.</p>
<p>I'd have trouble going deep on this, so here are great reads:</p>
<p><em>Simple, but powerful Pratt parsing</em></p>
<ul>
<li><a href="https://matklad.github.io/2020/04/13/simple-but-powerful-pratt-parsing" rel="nofollow noreferrer">https://matklad.github.io/2020/04/13/simple-but-powerful-pratt-parsing</a></li>
<li><a href="https://www.reddit.com/r/rust/comments/g0eusf/blog_post_simple_but_powerful_pratt_parsing/" rel="nofollow noreferrer">https://www.reddit.com/r/rust/comments/g0eusf/blog_post_simple_but_powerful_pratt_parsing/</a></li>
</ul>
<p><em>From Pratt to Dijkstra</em></p>
<ul>
<li><a href="https://matklad.github.io/2020/04/15/from-pratt-to-dijkstra.html" rel="nofollow noreferrer">https://matklad.github.io/2020/04/15/from-pratt-to-dijkstra.html</a></li>
</ul>
<p><em>Pratt Parsing and Precedence Climbing Are the Same Algorithm</em></p>
<ul>
<li><a href="https://www.oilshell.org/blog/2016/11/01.html" rel="nofollow noreferrer">https://www.oilshell.org/blog/2016/11/01.html</a></li>
<li><a href="https://www.reddit.com/r/oilshell/comments/5l70p7/comment/ddv1jdy/" rel="nofollow noreferrer">https://www.reddit.com/r/oilshell/comments/5l70p7/comment/ddv1jdy/</a></li>
</ul>
<p><em>Code for the Shunting Yard Algorithm, and More</em></p>
<ul>
<li><a href="https://www.oilshell.org/blog/2017/04/22.html" rel="nofollow noreferrer">https://www.oilshell.org/blog/2017/04/22.html</a></li>
</ul>
<p><em>Parsing Expressions</em></p>
<ul>
<li><a href="http://craftinginterpreters.com/parsing-expressions.html" rel="nofollow noreferrer">http://craftinginterpreters.com/parsing-expressions.html</a></li>
</ul>
<p><em>Resilient LL Parsing Tutorial</em></p>
<ul>
<li><a href="https://matklad.github.io/2023/05/21/resilient-ll-parsing-tutorial.html" rel="nofollow noreferrer">https://matklad.github.io/2023/05/21/resilient-ll-parsing-tutorial.html</a></li>
</ul>
<p><em>Better operator precedence</em></p>
<ul>
<li><a href="https://www.scattered-thoughts.net/writing/better-operator-precedence/" rel="nofollow noreferrer">https://www.scattered-thoughts.net/writing/better-operator-precedence/</a></li>
</ul>
<p><em>How can I incorporate ternary operators into a precedence climbing algorithm?</em></p>
<ul>
<li><a href="https://stackoverflow.com/questions/13681293/how-can-i-incorporate-ternary-operators-into-a-precedence-climbing-algorithm">https://stackoverflow.com/questions/13681293/how-can-i-incorporate-ternary-operators-into-a-precedence-climbing-algorithm</a></li>
</ul>
<p><em>Top-Down operator precedence (Pratt) parsing</em></p>
<ul>
<li><a href="https://eli.thegreenplace.net/2010/01/02/top-down-operator-precedence-parsing" rel="nofollow noreferrer">https://eli.thegreenplace.net/2010/01/02/top-down-operator-precedence-parsing</a></li>
</ul>

CC BY-SA 4.0
2024-02-22T04:11:27.207Z
2024-02-22T04:11:27.207Z
Szymon Marczak
# How can the shunting yard algorithm be adapted to handle currying?
Posted by: username_0 on 2023-08-02
The [shunting yard algorithm](https://en.wikipedia.org/wiki/Shunting_yard_algorithm) is used to parse infix expressions into a syntax tree, or prefix/postfix notation. Wikipedia provides pseudocode for how to implement it, but notes:

> This implementation does not implement composite functions, functions with a variable number of arguments, or unary operators.

Extending it to include functions with a variable number of arguments is fairly straightforward:

* In the operator stack, store each operator's arity alongside the operator itself.
* When you see a comma, after reaching the `(`, assert that the item in the operator stack immediately below that is a function name, and then increment its arity.

However, implementing curried functions is less obvious. Because functions need to be pushed to the operator stack, it's impossible for the result of any subexpression to itself be a function that's called.

Can the shunting yard algorithm be easily extended to handle this? If so, how? If not, what alternatives are there?
**Tags:** parsing
> **Comments:**
> **username_1**: I was about to edit this to eliminate the annoying horizontal scrolling, but it looks like that formatting was very deliberate.  ???  
> **username_0**: @RayButterworth That's where the line break appears in the Wikipedia article, at least on my screen.  
> **username_1**: Yes, but is that line break significant?  Why not simply quote it using ">" so that it can all be seen without horizontal scrolling.  
> **username_2**: isn't that the case with any partially applied function, or with any function that returns a function??  
---
## 2 answers
### Answer by username_3 on 2023-08-02. Score: 8
There's generally no reason to use the shunting-yard algorithm for actual parsing from tokens, and it's rare to do so. It doesn't give the opportunity for good error reporting, and on its own it even still accepts invalid syntax for infix expressions. True shunting-yard algorithm parsers have trouble with things like `1 2 +` (not rejected!) and mistaking grouping parentheses for function-application parentheses, and vice-versa; at the very least you need a covering parser to produce reasonable error messages.

There are extensions that do better, notably [operator-precedence parsers](https://en.wikipedia.org/wiki/Operator-precedence_parser). These delegate recursively to other parsing functions that consume and process expressions, returning parse nodes representing them. Each delegated function takes in a whole expression for as long as the operators it sees have higher precedence than where it started, and then returns what it's produced to the caller. The pure approach here is to treat function application as a very-high-precedence postfix operator; you can legitimately treat it as a separate category of thing too.

---

Another approach is to have functions for parsing an expression excluding any operators — so function or method calls and any literals of the language — and when parsing operator expressions, loop around performing the shunting-yard algorithm *on whole terms* as you go. This is what I did [here](https://github.com/mwh/kernan/blob/a176ef4998c9b7541f3f5fb444d6be5e64036ce7/GraceLanguage/Parsing/Parser.cs#L1437), for a language where only the four core arithmetic operators could be used together and combining other or user-defined operators was a syntax error. This can be helpful for keeping the logic in one place when you're writing it by hand, and slots into an existing recursive-descent parser.

---

The ideal (but theoretically unprincipled) approach is to produce an interleaved list of terms (AST nodes) and operators, and then apply the shunting-yard algorithm to that. In this approach, function calls are parsed into the appropriate function-call AST node early, as are numeric literals or any other non-operator expression terms, and it's those AST nodes that go onto the value stack during the precedence-resolving phase.

This fits in tidily with an overall recursive-descent approach. Have separate branches for parsing an expression term with and without operators, then when parsing operator expressions, take in a single term and look ahead for an operator after it: if it's there, loop around and take the next term the same way. Once there are no more operators, there is a list of terms (that is, ordinary AST nodes) and operator symbols, and you can perform the shunting-yard algorithm to build the expression tree with the right precedence.

---

Either of these last two ways allows rejecting invalid syntax for the right reasons at the right time, because, for example, arguments are definitively being parsed as arguments. It also allows for more complex user-defined operator situations, like ones whose precedence isn't defined until later. They also provide more help to *you* as the implementer when you need to debug things, because you have more information and state recorded to diagnose with.

These approaches are a relatively short distance from where you are, but there are whole other families of parser that also deal with operators within their own style.
I would not recommend using the shunting-yard algorithm itself for the actual parsing from tokens in a programming language, though it could be useful in a resource-constrained system that knew all input would be well-formed.
> **Comments:**
> **username_4** (2023-08-03): An edge case worth considering is prefix operators with low precedence, such as `not` in Python. For example, `x + not y` is supposed to be a syntax error because `not` has lower precedence than `+`. I think this would be even more complicated for low-precedence postfix operators, because the parser doesn't even know that `x + y foo` (where `foo` is postfix and lower precedence than `+`) is a single term until it looks past the `+`.  
---
### Answer by username_5 on 2024-02-22. Score: 2
I think you could use a a mix of Recursive Descent and Shunting Yard/Pratt/Precedence Climbing (these all are the same algorithm). Also, using Shunting Yard does not mean sacrificing error reporting. Most implementations don't, but there's nothing forcing you to skip it.

I'd have trouble going deep on this, so here are great reads:

*Simple, but powerful Pratt parsing*

* <https://matklad.github.io/2020/04/13/simple-but-powerful-pratt-parsing>
* <https://www.reddit.com/r/rust/comments/g0eusf/blog_post_simple_but_powerful_pratt_parsing/>

*From Pratt to Dijkstra*

* <https://matklad.github.io/2020/04/15/from-pratt-to-dijkstra.html>

*Pratt Parsing and Precedence Climbing Are the Same Algorithm*

* <https://www.oilshell.org/blog/2016/11/01.html>
* <https://www.reddit.com/r/oilshell/comments/5l70p7/comment/ddv1jdy/>

*Code for the Shunting Yard Algorithm, and More*

* <https://www.oilshell.org/blog/2017/04/22.html>

*Parsing Expressions*

* <http://craftinginterpreters.com/parsing-expressions.html>

*Resilient LL Parsing Tutorial*

* <https://matklad.github.io/2023/05/21/resilient-ll-parsing-tutorial.html>

*Better operator precedence*

* <https://www.scattered-thoughts.net/writing/better-operator-precedence/>

*How can I incorporate ternary operators into a precedence climbing algorithm?*

* <https://stackoverflow.com/questions/13681293/how-can-i-incorporate-ternary-operators-into-a-precedence-climbing-algorithm>

*Top-Down operator precedence (Pratt) parsing*

* <https://eli.thegreenplace.net/2010/01/02/top-down-operator-precedence-parsing>
---
