Alternatively, look to APL (k, j, q), Smalltalk, Forth (factor, postscript), and Lisp: all of these languages offer their own take on uniform operator precedence. It’s always obvious to a reader, without any need to memorize. It’s also simpler for the machine to parse. Solve the problem by removing it.

Despite having written a c parser, I frequently get its precedence confused.

I’ve hit bugs caused by people getting it wrong and (much more often) I’ve had to consult a table to find out which way it works. It’s pretty easy to remember that multiply and divide are higher precedence than add and subtract, since we learned it at school and were tested on it over many years. It’s much harder to remember what the relative precedence of pre-increment and post-increment or bitwise and, and left shift are. I consider a language trying to make me remember these things to be a bit of a usability mistake and generally just put brackets everywhere.

In Verona, we’re experimenting with no operator precedence. a op1 b op2 c is a parse error. You can chain sequences of the same operator but any pair of different operators needs brackets. You can write (a op1 b op1 c) op2 d or a op1 b op1 (c op2 d) and it’s obvious to the reader what the order of application is. This is a bit more important for us because we allow function names to include symbol characters and allow any function to be used infix, so statically defining rules for application order of a append b £$%£ c would lead to confusion.

This is my go-to approach as well not just because I can’t remember some of the less-frequently-used precedence rules, but also because I assume the person maintaining the code after me will be similarly fuzzy on those details and making it explicit will make my code easier to understand. For that reason, I often add parentheses even in cases where I am quite certain of the precedence rules.

That’s true. For a single operator, the evaluation order is exactly the same as for other expressions (left to right) so it should be easy to remember the rule, even if not all evaluation orders would give the same result.

fortress’s operator precedence system is one of my favourite pieces of language design, for the way in which it gets things so obviously right in terms of mathematical design that every other system feels clunky in comparison.

i would not have thought of the point myself before reading a description of fortress, but once I did I felt like of course if you have operator overloading you are essentially using the same symbols as different operators in different contexts, and that an “operator” is actually a combination of a symbol and the context in which its meaning is defined. it is therefore absurd to insist that precedence rules attach to the symbol rather than the operator, the way pretty much every other language that has precedence rules at all does.

because that mirrors their usage in established mathematical or scientific domains. e.g. if you are coding up formulae in a system where * is a low precedence operator, it would be nice not to have to treat it as high precedence and use unnecessary parentheses just because the C world uses it for multiplication.

Swift goes one step further and has a concept of “precedence groups,” which make it easy to define new operators (without needing to write/modify comparePrecedence). It nicely matches the way my brain thinks about operator precedence: “multiplicationy things bind tighter than additiony things.” If you make a new infix operator, you can just say “this should behave like * and /.” And you can, of course, define your own precedence groups.

So there’s like a topological sort thing happening there, and it allows you to say “this operator can only mix and match with these other operators,” and you have to add parens to disambiguate weird expressions. It’s really neat!

The best operator precedence is no operator precedence. The fact that people get hung up on this is nuts to me, although I can obviously understand it.

I like it! Comparing two operators directly is indeed the minimal, core way to make that that choice in the Pratt’s loop, because “left and right operator” is all the data you have. Compressing that to a number (or two) is a lossy operation, which makes it harder to understand.

This approach also makes visualizing what the algorithm does as a whole much more natural:

1 + 2 + 3 * 4
> < > <

Here, arrow between pairs of operators point to which one binds tighter, and the overall task is then to repeatedly fold > <.

In a production parser for an IDE, I would avoid emitting .Ambiguous errors during parsing: it’s more robust to parse with some precedence level, and then emit a dedicated error+fixit in a validating tree traversal.

Couldn’t you just use the existing system but allow operators to share the same precedence numbers so that some combinations are ambiguous? The solution here seems to have a combinatorial explosion of complexity if you increase the number of operators.

How does that work in the current system? If they have different numbers then I would expect a + b - c or a - b + c to have an error message but I don’t see one. The must be some notion of commutativity built in.

How is this dealt with in the solution proposed by the article? Maybe I am a bit dense but I can’t see any examples there that answer this. Are + and - ambigous or do they have a defined precedence?

+ and - are left-associative (if we ignore precedence, then the issue here is associativity, not commutativity). Your grammar may have a rule like:

additive-expression ::= term | additive-expression [‘+’ | ‘-’] term

Given ‘a + b - c’, we have a top-level additive expression comprising the term ‘c’, the operator ‘-’, and another additive expression; the latter comprises the term ‘b’, the operator ‘+’, and another additive expression consisting only of the term ‘a’.

In other words, + and - are specified by the same grammar rule, and it is defined to be left-associative, such that a full parenthesization of ‘a + b - c’ is ‘(a + b) - c’.

(Floating-point issues aside, addition is associative, such that even if we had redundant syntactical rules, ‘a + b + c’ would be semantically unambiguous—we will get the same answer no matter which parse we choose. The same does not apply to subtraction. So really the same problem applies to ‘a - b - c’; is that ‘(a - b) - c’ or ‘a - (b - c)’?)

Thanks for the clarification. So (bear with my lack of understanding of operator precedence systems) that means that in the current norm of most programming languages, + and - are both left associative and are treated as having the same precedence, so a - b - c is in fact processed as (a - b) - c. Is that correct? I think I also see the flaw in my initial question. If bitwise expressions are ambiguous with multiplicative, and also with additive expressions, then all three would need the same precedence. This would mean that additive and multiplicative are also ambiguous which is obviously wrong.

John Earnest says on reddit (I agree):

Despite having written a c parser, I frequently get its precedence confused.

I’ve hit bugs caused by people getting it wrong and (much more often) I’ve had to consult a table to find out which way it works. It’s pretty easy to remember that multiply and divide are higher precedence than add and subtract, since we learned it at school and were tested on it over many years. It’s much harder to remember what the relative precedence of pre-increment and post-increment or bitwise and, and left shift are. I consider a language trying to make me remember these things to be a bit of a usability mistake and generally just put brackets everywhere.

In Verona, we’re experimenting with no operator precedence.

`a op1 b op2 c`

is a parse error. You can chain sequences of the same operator but any pair of different operators needs brackets. You can write`(a op1 b op1 c) op2 d`

or`a op1 b op1 (c op2 d)`

and it’s obvious to the reader what the order of application is. This is a bit more important for us because we allow function names to include symbol characters and allow any function to be used infix, so statically defining rules for application order of`a append b £$%£ c`

would lead to confusion.This is my go-to approach as well not just because I can’t remember some of the less-frequently-used precedence rules, but also because I assume the person maintaining the code after me will be similarly fuzzy on those details and making it explicit will make my code easier to understand. For that reason, I often add parentheses even in cases where I

amquite certain of the precedence rules.Not all binary operators are associative, though.

That’s true. For a single operator, the evaluation order is exactly the same as for other expressions (left to right) so it should be easy to remember the rule, even if not all evaluation orders would give the same result.

This makes operator precedence a partial order rather than a total order. And Guy Steele mentioned that the Fortress language behaved like this:

https://www.youtube.com/watch?v=EZD3Scuv02g

mentioned briefly here: https://www.oilshell.org/blog/2016/11/01.html

fortress’s operator precedence system is one of my favourite pieces of language design, for the way in which it gets things so obviously right in terms of mathematical design that every other system feels clunky in comparison.

i would not have thought of the point myself before reading a description of fortress, but once I did I felt like of

courseif you have operator overloading you are essentially using the same symbols as different operators in different contexts, and that an “operator” is actually a combination of a symbol and the context in which its meaning is defined. it is therefore absurd to insist that precedence rules attach to the symbol rather than the operator, the way pretty much every other language that has precedence rules at all does.I dunno, letting

`a + b * c`

resolve as`(a + b) * c`

or`a + (b * c)`

dependent on the types of the operands seems pretty confusing to me.There’s plenty of unicode symbols that are suitable for infix operators, why not just use some of those if you want different precedences?

because that mirrors their usage in established mathematical or scientific domains. e.g. if you are coding up formulae in a system where * is a low precedence operator, it would be nice not to have to treat it as high precedence and use unnecessary parentheses just because the C world uses it for multiplication.

It begins at this timestamp: https://youtu.be/EZD3Scuv02g?t=1884. He doesn’t go into detail, though.

This is how operators work in Swift, and it

isbetter.https://docs.swift.org/swift-book/LanguageGuide/AdvancedOperators.html#ID46

Swift goes one step further and has a concept of “precedence groups,” which make it easy to define new operators (without needing to write/modify

`comparePrecedence`

). It nicely matches the way my brain thinks about operator precedence: “multiplicationy things bind tighter than additiony things.” If you make a new infix operator, you can just say “this should behave like`*`

and`/`

.” And you can, of course, define your own precedence groups.https://docs.swift.org/swift-book/ReferenceManual/Declarations.html#ID550

So there’s like a topological sort thing happening there, and it allows you to say “this operator can only mix and match with these other operators,” and you have to add parens to disambiguate weird expressions. It’s really neat!

The best operator precedence is no operator precedence. The fact that people get hung up on this is nuts to me, although I can obviously understand it.

I like it! Comparing two operators directly is indeed the minimal, core way to make that that choice in the Pratt’s loop, because “left and right operator” is all the data you have. Compressing that to a number (or two) is a lossy operation, which makes it harder to understand.

This approach also makes visualizing what the algorithm does as a whole much more natural:

Here, arrow between pairs of operators point to which one binds tighter, and the overall task is then to repeatedly fold

`> <`

.In a production parser for an IDE, I would avoid emitting

`.Ambiguous`

errors during parsing: it’s more robust to parse with some precedence level, and then emit a dedicated error+fixit in a validating tree traversal.Couldn’t you just use the existing system but allow operators to share the same precedence numbers so that some combinations are ambiguous? The solution here seems to have a combinatorial explosion of complexity if you increase the number of operators.

How does that work? If you say

`a + b - c`

is ambiguous because + an - share the same precedence people won’t like that.How does that work in the current system? If they have different numbers then I would expect

`a + b - c`

or`a - b + c`

to have an error message but I don’t see one. The must be some notion of commutativity built in.How is this dealt with in the solution proposed by the article? Maybe I am a bit dense but I can’t see any examples there that answer this. Are + and - ambigous or do they have a defined precedence?

+ and - are left-associative (if we ignore precedence, then the issue here is

associativity, not commutativity). Your grammar may have a rule like:Given ‘a + b - c’, we have a top-level additive expression comprising the term ‘c’, the operator ‘-’, and another additive expression; the latter comprises the term ‘b’, the operator ‘+’, and another additive expression consisting only of the term ‘a’.

In other words, + and - are specified by the same grammar rule, and it is defined to be left-associative, such that a full parenthesization of ‘a + b - c’ is ‘(a + b) - c’.

(Floating-point issues aside, addition is associative, such that even if we had redundant syntactical rules, ‘a + b + c’ would be

semanticallyunambiguous—we will get the same answer no matter which parse we choose. The same does not apply to subtraction. So really the same problem applies to ‘a - b - c’; is that ‘(a - b) - c’ or ‘a - (b - c)’?)Thanks for the clarification. So (bear with my lack of understanding of operator precedence systems) that means that in the current norm of most programming languages, + and - are both left associative and are treated as having the same precedence, so

`a - b - c`

is in fact processed as`(a - b) - c`

. Is that correct? I think I also see the flaw in my initial question. If bitwise expressions are ambiguous with multiplicative, and also with additive expressions, then all three would need the same precedence. This would mean that additive and multiplicative are also ambiguous which is obviously wrong.I stand corrected.

Proof by contradiction is a very strange way to convince yourself of something, but if it works for you… :)