3

Say I have an expression as follows (where ⨁ and ⨂ are binary operators which have the same precedence level but not the same associativity):

x ⨁ y ⨂ z

Would y belong to ⨁ or ⨂, and based on what criteria?

Aadit M Shah
  • 72,912
  • 30
  • 168
  • 299
  • You should try this in Haskell. – Matt Fenwick Jul 12 '13 at 03:04
  • @MattFenwick - The only operators that I know of in Haskell with the same precedence level and different associativity are the `>>=` operator (`infixl 1`) and the `=<<` operator (`infixr 1`). I'll test it out as soon as I get the chance but in all probability type inference rules in Haskell would trump associativity resulting in the expression being evaluated unambiguously without the need for the Edsgar Dijkstra's rules as specified in the Shunting-yard algorithm. – Aadit M Shah Jul 12 '13 at 03:30

1 Answers1

1

According to the Edsgar Dijkstra's Shunting-yard algorithm if neighboring two operators in an expressions have the same precedence level then the expression is disambiguated based on the associativity of the second operator.

  1. If the second operator is left associative then the operand belongs to the first operator.
  2. If the second operator is right associative then the operand belongs to the second operator.

Case 1: ⨂ is left associative. The expression evaluates to:

(x ⨁ y) ⨂ z

Case 2: ⨂ is right associative. The expression evaluates to:

x ⨁ (y ⨂ z)
Aadit M Shah
  • 72,912
  • 30
  • 168
  • 299