<p>I am interested, is it possible that, in some programming language, two infix operators have the same priority, but different associativity? If so, how is that implemented in the parser?</p>

<operators>
Can two infix operators have the same priority, but different associativity? If so, how would it be implemented in the parser?
<p>The way a shift-reduce infix operator parser works is that you maintain a stack of the form</p>
<pre><code>A + ( B * ( ... ( G @
</code></pre>
<p>(those are unclosed parentheses), and when you encounter <code>H #</code>, you compare the precedence of <code>@</code> and <code>#</code>. If <code>#</code> binds tighter, you shift to</p>
<pre><code>A + ( B * ( ... ( G @ ( H #
</code></pre>
<p>If <code>@</code> binds tighter, you instead reduce to</p>
<pre><code>A + ( B * ( ... ( G' #     where G' = (G @ H)
</code></pre>
<p>If there is no precedence relationship between <code>@</code> and <code>#</code>, you report a parse-time error.</p>
<p>Note that there is no mention of precedence levels or left- and right- associativity of individual operators in that description. There is only the relative precedence of pairs of operators. If you <em>choose</em> to use precedence levels to define those relationships, then the rules for that would normally be:</p>
<ol>
<li>If <code>@</code> and <code>#</code> have different precedence levels, the one with the higher level binds tighter.</li>
<li>If they have the same precedence level and are both left- (resp. both right-) associative, then the one on the left (resp. right) binds tighter.</li>
<li>Otherwise, there is no relationship (parse error).</li>
</ol>
<p>Many languages can never hit case 3 because they define all operators at each level to have the same associativity. But in, e.g., Haskell, which lets you declare your own precedence level and associativity for custom operators, rule 3 can be hit. Haskell allows you to make operators nonassociative, which simply means that rule 2 never applies to them. Built-in operators like <code>&lt;</code> are nonassociative in Haskell so that <code>a &lt; b &lt; c</code> is an error, which is what it should also be in C and Java and every other language that doesn't have chained comparison operators, and I have no clue why it isn't.</p>
<p>There is a case to be made that the linear-precedence-level approach to comparing operators is a bad idea, since it inevitably leads to operator combinations that really should always be parenthesized, like <code>a + b | c</code>, being accepted without parentheses. In comments on kaya3's answer, someone linked <a href="https://www.scattered-thoughts.net/writing/better-operator-precedence/" rel="nofollow noreferrer">an essay on that subject</a>.</p>

CC BY-SA 4.0
2024-05-04T06:01:03.330Z
2024-05-04T06:01:03.330Z
benrg
<p>As far as I can see, this should work using a standard <a href="https://en.wikipedia.org/wiki/Operator-precedence_parser" rel="noreferrer">operator precedence parser</a>. Wikipedia's pseudocode for the &quot;<a href="https://en.wikipedia.org/wiki/Operator-precedence_parser#Pseudocode" rel="noreferrer">precedence climbing method</a>&quot; already accounts for operators having different associativities:</p>
<pre><code>while lookahead is a binary operator whose precedence is greater
        than op's, or a right-associative operator
        whose precedence is equal to op's
    ...
</code></pre>
<p>The hard part seems to be figuring out what a correct result <em>should</em> be. Suppose our two operators are <code>*</code> (left-associative) and <code>@</code> (right-associative). Then a correct parse of <code>a * b @ c</code> could be either:</p>
<ul>
<li><code>(a * b) @ c</code> since <code>*</code> is left-associative,</li>
<li><code>a * (b @ c)</code> since <code>@</code> is right-associative,</li>
</ul>
<p>That is, both operators have an &quot;equal claim&quot; to bind with <code>b</code> and there is no way to decide which takes precedence. Even if you can come up with an unambiguous and clear specification for how the two operators interact when they appear together, most users of your language are likely not going to learn it, and it seems like a bad idea to make your grammar so inscrutable.</p>
<p>On the other hand, if expressions like <code>a * b @ c</code> are invalid for semantic reasons (e.g. their types can never be correct) but they need to have the same precedence regardless, then the syntactic ambiguity is irrelevant since such expressions have no meaning. In that case, a standard approach such as the one above should be fine.</p>
<p>Another situation in which this could be fine is if the two operators together are associative (e.g. scalar multiplication and matrix multiplication), so that both of the above parses would have the same meaning. Although in most such cases, there is no need for the second operator to be right-associative, since it is simply associative anyway.</p>

CC BY-SA 4.0
2024-05-02T14:25:24.143Z
2024-05-02T14:31:34.067Z
2024-05-02T14:31:34.067Z
kaya3
CC BY-SA 4.0
2024-05-02T17:35:31.773Z
Also, it's not necessary to use numerical precedence: one can directly compare two operators with each other to obtain *3* possible results: bind to the left, bind to the right, raise error because of ambiguity, see e.g. https://www.scattered-thoughts.net/writing/better-operator-precedence/
Joker_vD
CC BY-SA 4.0
2024-05-02T17:46:57.683Z
@Joker_vD The argument for that being "better" seems very weak to me. I would rather have a language where the spec for operator precedence gives two pieces of information per operator (i.e. numerical precedence and left vs. right associativity), than one piece of information per pair of operators. It's also not 100% clear that this approach works generally when there are three or more operators in an expression - for `a + b * c | d` we cannot assume that the first two operators bind either like `(a + b) * c` or `a + (b * c)`, because both would make `a + (b * (c | d))` impossible.
kaya3
CC BY-SA 4.0
2024-05-02T18:10:47.237Z
@kaya3: Fortress uses relative operator precedence which only forms a partial order over the operators. If two operators are "not comparable", it is simply illegal to use them in the same expression without parentheses. This allows you to define the "usual" precedences between operators programmers are used to, but avoids strange cases where someone mixes operators that really shouldn't be mixed anyway. For example, clearly, you want defined precedence between arithmetic operators and between logical operators. Also, between assignment and pretty much any other operator.
Jörg W Mittag
CC BY-SA 4.0
2024-05-02T18:12:51.217Z
Defined precedence between arithmetic and relational operators is nice as well since it allows you to compare the result of arithmetic expressions. Relational and logical operators makes sense, too, because you want to perform logical operations on the result of a comparison (not greater than or somesuch). But, e.g., arithmetic and logical operators? If there's really a reason to mix those, adding parentheses isn't the worst thing in the world.
Jörg W Mittag
CC BY-SA 4.0
2024-05-02T18:14:29.230Z
Fortress has another neat trick in that whitespace can *confirm* the precedence, but not *change* it. The compiler will check whether whitespace is consistent with precedence. E.g. `1+2*3` is legal, `1 + 2 * 3` is legal, `1 + 2*3` is legal, but `1+2 * 3` is a compile error.
Jörg W Mittag
CC BY-SA 4.0
2024-05-02T23:27:51.317Z
Fortress has hundreds of operators, though, so their trade-offs are a lot different than your typical C-style language.
Jörg W Mittag
CC BY-SA 4.0
2024-05-03T23:09:05.660Z
@JörgWMittag Hadn't heard of Fortress before, googled it, found a tutorial slide deck. "Parsing this stuff is an interesting research problem"
Barmar
CC BY-SA 4.0
2024-05-04T06:03:09.313Z
@kaya3 Re your comment, the decision is not really between `(a + b) * c` and `a + (b * c)` but between shift and reduce. Even if you use linear precedence levels, the parsing decisions always boil down to comparing pairs of operators. I just wrote another answer expanding on that.
benrg
# Can two infix operators have the same priority, but different associativity? If so, how would it be implemented in the parser?
Posted by: username_0 on 2024-05-02
I am interested, is it possible that, in some programming language, two infix operators have the same priority, but different associativity? If so, how is that implemented in the parser?
**Tags:** operators
---
## 2 answers
### Answer by username_2 on 2024-05-02. Score: 8 | Accepted answer
As far as I can see, this should work using a standard operator precedence parser. Wikipedia's pseudocode for the "precedence climbing method" already accounts for operators having different associativities:
while lookahead is a binary operator whose precedence is greater
        than op's, or a right-associative operator
        whose precedence is equal to op's
    ...

The hard part seems to be figuring out what a correct result should be. Suppose our two operators are * (left-associative) and @ (right-associative). Then a correct parse of a * b @ c could be either:

(a * b) @ c since * is left-associative,
a * (b @ c) since @ is right-associative,

That is, both operators have an "equal claim" to bind with b and there is no way to decide which takes precedence. Even if you can come up with an unambiguous and clear specification for how the two operators interact when they appear together, most users of your language are likely not going to learn it, and it seems like a bad idea to make your grammar so inscrutable.
On the other hand, if expressions like a * b @ c are invalid for semantic reasons (e.g. their types can never be correct) but they need to have the same precedence regardless, then the syntactic ambiguity is irrelevant since such expressions have no meaning. In that case, a standard approach such as the one above should be fine.
Another situation in which this could be fine is if the two operators together are associative (e.g. scalar multiplication and matrix multiplication), so that both of the above parses would have the same meaning. Although in most such cases, there is no need for the second operator to be right-associative, since it is simply associative anyway.
> **Comments:**
> **username_3** (2024-05-02): Also, it's not necessary to use numerical precedence: one can directly compare two operators with each other to obtain *3* possible results: bind to the left, bind to the right, raise error because of ambiguity, see e.g. https://www.scattered-thoughts.net/writing/better-operator-precedence/  
> **username_2** (2024-05-02): @Joker_vD The argument for that being "better" seems very weak to me. I would rather have a language where the spec for operator precedence gives two pieces of information per operator (i.e. numerical precedence and left vs. right associativity), than one piece of information per pair of operators. It's also not 100% clear that this approach works generally when there are three or more operators in an expression - for `a + b * c | d` we cannot assume that the first two operators bind either like `(a + b) * c` or `a + (b * c)`, because both would make `a + (b * (c | d))` impossible.  
> **username_4** (2024-05-02): @kaya3: Fortress uses relative operator precedence which only forms a partial order over the operators. If two operators are "not comparable", it is simply illegal to use them in the same expression without parentheses. This allows you to define the "usual" precedences between operators programmers are used to, but avoids strange cases where someone mixes operators that really shouldn't be mixed anyway. For example, clearly, you want defined precedence between arithmetic operators and between logical operators. Also, between assignment and pretty much any other operator.  
> **username_4** (2024-05-02): Defined precedence between arithmetic and relational operators is nice as well since it allows you to compare the result of arithmetic expressions. Relational and logical operators makes sense, too, because you want to perform logical operations on the result of a comparison (not greater than or somesuch). But, e.g., arithmetic and logical operators? If there's really a reason to mix those, adding parentheses isn't the worst thing in the world.  
> **username_4** (2024-05-02): Fortress has another neat trick in that whitespace can *confirm* the precedence, but not *change* it. The compiler will check whether whitespace is consistent with precedence. E.g. `1+2*3` is legal, `1 + 2 * 3` is legal, `1 + 2*3` is legal, but `1+2 * 3` is a compile error.  
> **username_4** (2024-05-02): Fortress has hundreds of operators, though, so their trade-offs are a lot different than your typical C-style language.  
> **username_5** (2024-05-03): @JörgWMittag Hadn't heard of Fortress before, googled it, found a tutorial slide deck. "Parsing this stuff is an interesting research problem"  
> **username_1** (2024-05-04): @kaya3 Re your comment, the decision is not really between `(a + b) * c` and `a + (b * c)` but between shift and reduce. Even if you use linear precedence levels, the parsing decisions always boil down to comparing pairs of operators. I just wrote another answer expanding on that.  
---
### Answer by username_1 on 2024-05-04. Score: 3
The way a shift-reduce infix operator parser works is that you maintain a stack of the form
A + ( B * ( ... ( G @

(those are unclosed parentheses), and when you encounter H #, you compare the precedence of @ and #. If # binds tighter, you shift to
A + ( B * ( ... ( G @ ( H #

If @ binds tighter, you instead reduce to
A + ( B * ( ... ( G' #     where G' = (G @ H)

If there is no precedence relationship between @ and #, you report a parse-time error.
Note that there is no mention of precedence levels or left- and right- associativity of individual operators in that description. There is only the relative precedence of pairs of operators. If you choose to use precedence levels to define those relationships, then the rules for that would normally be:

If @ and # have different precedence levels, the one with the higher level binds tighter.
If they have the same precedence level and are both left- (resp. both right-) associative, then the one on the left (resp. right) binds tighter.
Otherwise, there is no relationship (parse error).

Many languages can never hit case 3 because they define all operators at each level to have the same associativity. But in, e.g., Haskell, which lets you declare your own precedence level and associativity for custom operators, rule 3 can be hit. Haskell allows you to make operators nonassociative, which simply means that rule 2 never applies to them. Built-in operators like < are nonassociative in Haskell so that a < b < c is an error, which is what it should also be in C and Java and every other language that doesn't have chained comparison operators, and I have no clue why it isn't.
There is a case to be made that the linear-precedence-level approach to comparing operators is a bad idea, since it inevitably leads to operator combinations that really should always be parenthesized, like a + b | c, being accepted without parentheses. In comments on kaya3's answer, someone linked an essay on that subject.
---
