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?
$\begingroup$
$\endgroup$
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
8
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) @ csince*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.
-
2$\begingroup$ 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. scattered-thoughts.net/writing/better-operator-precedence $\endgroup$– Joker_vDCommented May 2 at 17:35
-
$\begingroup$ @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 | dwe cannot assume that the first two operators bind either like(a + b) * cora + (b * c), because both would makea + (b * (c | d))impossible. $\endgroup$– kaya3Commented May 2 at 17:46 -
3$\begingroup$ @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. $\endgroup$ Commented May 2 at 18:10
-
3$\begingroup$ 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. $\endgroup$ Commented May 2 at 18:12
-
5$\begingroup$ 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*3is legal,1 + 2 * 3is legal,1 + 2*3is legal, but1+2 * 3is a compile error. $\endgroup$ Commented May 2 at 18:14
$\begingroup$
$\endgroup$
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.
