Precedence of function in Shunting-yard algorithm

Question

I am working through the Shunting-yard algorithm, as described by wikipedia.

The description of the algorithm when dealing with operators is as follows:

If the token is an operator, o1, then:

while there is an operator token, o2, at the top of the operator stack, and either

o1 is left-associative and its precedence is less than or equal to
that of o2, or

o1 is right associative, and has precedence less than that of o2,

then pop o2 off the operator stack, onto the output queue;

push o1 onto the operator stack.

However, they give the following example:

Input: sin max 2 3 / 3 * 3.1415

When the algorithm hits the / token, the description of what should happen is as follows:

Token |        Action       |   Output (in RPN) |   Operator Stack
...
/     | Pop token to output | 2 3 max           | / sin 
...

They are popping the function token max off the stack and putting into the queue. According to their algorithm, this would seem to mean the function token is both an operator, and has a precedence less than that of the / operator.

There is no explanation as to whether or not this is the case. So, for the Shunting-yard algorithm, what is the precedence of a function? Are functions right or left associative? Or is wikipedia just incomplete/inaccurate?

Answer 1

I believe the direct answer is simply that functions are not operators. From the page you linked:

If the token is a function token, then push it onto the stack.

This is all it needs to say, since the function case (prefix to postfix) is much simpler than the operator case (infix to postfix).

For the follow-up questions: The notions of precedence and associativity are only needed because of the inherit ambiguity in any expression with multiple infix operators. Function tokens are already using prefix notation, so they simply don't have that problem. You don't need to know whether sin or max has "higher precedence" to figure out that max needs to be evaluated first; it's already clear from the order of the tokens. That's why computers prefer pre/postfix notation to begin with, and why we have this algorithm for converting infix to pre/postfix.

You do need to have some kind of rule for where a function's arguments start and end when no parenthesis are present, so you could say that functions "take precedence" over operators or vice versa. But unlike infix operators, a single consistent rule for all functions is enough to make their compositions completely unambiguous.

Answer 2

There are two different cases to consider, depending on your language syntax. If your language uses parenthesis to indicate function application (eg f(2+1)) then precedence is irrelevant. The function should be pushed onto the stack and popped out after (for the example above, the result is 2 1 + f). Alternatively you can treat the function as a value and output it immediately, and output a function invocation operation after the close parenthesis (which should otherwise be treated the same as any other parenthesis), eg f 2 1 + $, where $ is the function invocation operation.

If your language, however, does not use parenthesis to indicate function invocation, but instead places the argument directly after the function without any special punctuation (eg f 2 + 1), as is apparently the case for Wikipedia's example, then things are a little more complicated. Note that the expression I just gave ás an example is ambiguous: is f applied to 2 and 1 added to the result, or do we add 2 and 1 together and then call f with the result?

Again, there are two approaches. You can simply push the function to the operator stack when you encounter it and assign it whatever precedence you want. This is the simplest approach, and is apparently what the quoted example has done. There are practical issues, however. Firstly, how do you identify a function? If you have a finite set it's easy, but if you have user defined functions, this means your parser needs too feed back into your environment, which can get messy quickly. And how do you handle functions with multiple arguments?

My feeling is that for this style of syntax, using functions as values that are handier by a function application operator makes a lot more sense. Then, you can simply inject the application operator whenever you read a value and the last thing you read was also a value, so you don't need any special way of telling which identifiers are functions. You can also work with expressions that return functions (which is difficult or impossible with the function-as-operation style). And this means you can use currying to handle multiple argument functions, which is a massive simplification over trying to handle them directly.

The only thing you need to decide then is what the precedence of function application is. The choice is up to you, but in every language I've used that works like this, it has been the most strongly binding operator in the language, and has been right associative. (The only interesting variation being Haskell, which as well as having the strongly binding version described, also has a synonym for it with the symbol $ which is the most weakly binding operator in the language, allowing expressions like f 2 + 1 to apply f to 2 and f $ 2 + 1 to apply it to the whole of the rest of the expression)

Answer 3

I implemented the asked for "functions in shunting yard" after reading Dijkstra's original thinking (Pages 7-11 in the Algol 60 compiler paper, https://ir.cwi.nl/pub/9251), and needing a robust solution, I did the following:

parsing:

• Push the function descriptor
• Push a start-of-args left bracket "[" just like his start of subexpression parenthesis.
• Read a "(" to ")" balanced argument list sequence from the input
• Push this to the output token stream
• Push an end-of-args right bracket "]" just like his "compensating closing bracket"

Infix-to-postfix (shunting yard):

• Add another stack, the function stack, just like the operator stack
• When scanning a function name, push the function info to the function stack
• When an end-of-args right bracket is seen, pop the function stack to output

Works perfectly in robust testing and complicated scenarios. In my application (a command line arguments-containing-expressions expander), I support multi argument functions and a comma "," token to separate them, and these flow through the whole process.

Examples look like "sqrt(3^2+4^2)" which becomes "3 2 ^ 4 2 ^ + sqrt" and ultimately "5" which is what the program thinks is the argument. It is bignum, so ""binomial(64, 32)/gcd(binomial(64, 32),binomial(63, 31))" ==> big things ==> "2" is helpful. "123456^789" is 40,173 digits and the timing shows "evaluation = 0.000390 sec" on my MacBookPro, so quick.

I also use this to expand data in tables, and find that handy. Anyway, this my tip on my way to carefully handle function calls, multiple arguments, and deep nesting in a Dijkstra shunting-yard context. Just did it today from independent thinking. Don't know if there may be better ways.