5
$\begingroup$

The 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?

$\endgroup$
4
  • $\begingroup$ I was about to edit this to eliminate the annoying horizontal scrolling, but it looks like that formatting was very deliberate. ??? $\endgroup$ Aug 3, 2023 at 0:15
  • $\begingroup$ @RayButterworth That's where the line break appears in the Wikipedia article, at least on my screen. $\endgroup$
    – Bbrk24
    Aug 3, 2023 at 1:45
  • $\begingroup$ Yes, but is that line break significant? Why not simply quote it using ">" so that it can all be seen without horizontal scrolling. $\endgroup$ Aug 3, 2023 at 3:18
  • 1
    $\begingroup$ isn't that the case with any partially applied function, or with any function that returns a function?? $\endgroup$
    – njzk2
    Aug 3, 2023 at 18:36

2 Answers 2

8
$\begingroup$

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. 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, 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.

$\endgroup$
1
  • $\begingroup$ 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 +. $\endgroup$
    – kaya3
    Aug 3, 2023 at 11:35
1
$\begingroup$

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

From Pratt to Dijkstra

Pratt Parsing and Precedence Climbing Are the Same Algorithm

Code for the Shunting Yard Algorithm, and More

Parsing Expressions

Resilient LL Parsing Tutorial

Better operator precedence

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

Top-Down operator precedence (Pratt) parsing

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .