Friday, March 30, 2012

Operator Precedence And Associativity


  • Operator Precedence And Associativity

http://www.youtube.com/watch?v=n_eDAzzgzkA



Two characteristics of operators determine how they will group with operands:
precedence Precedence is the priority for grouping different types of operators with their operands.
associativity Associativity is the left-to-right or right-to-left order for grouping operands to operators that have the same precedence.

For example, in the following statements, the value of 5 is assigned to both a and b because of the right-to-left associativity of the = operator. The value of c is assigned to b first, and then the value of b is assigned to a.

b = 9;
c = 5;
a = b = c;

the * and / operations are performed before the + because of precedence. Further, b is multiplied by c before it is divided by d because of associativity.

a + b * c / d

http://northstar-www.dartmouth.edu/doc/ibmcxx/en_US/doc/language/concepts/cuexppre.htm




  • Operator Precedence in Java

For example, multiplication and division have a higher precedence than addition and subtraction. Precedence rules can be overridden by explicit parentheses

Precedence Order. When two operators share an operand the operator with the higher precedence goes first. For example, 1 + 2 * 3 is treated as 1 + (2 * 3), whereas 1 * 2 + 3 is treated as (1 * 2) + 3 since multiplication has a higher precedence than addition.

Associativity. When two operators with the same precendence the expression is evaluated according to its associativity
For example x = y = z = 17 is treated as x = (y = (z = 17)), leaving all three variables with the value 17, since the = operator has right-to-left associativty
 72 / 2 / 3 is treated as (72 / 2) / 3 since the / operator has left-to-right associativity.

What is the result of the following code fragment? Explain.

System.out.println("1 + 2 = " + 1 + 2);
 1 + 2 = 12 and 1 + 2 = 3, respectively. If either (or both) of the operands of the + operator is a string, the other is automatically cast to a string. String concatenation and addition have the same precedence. Since they are left-associative, the operators are evaluated left-to-right.

System.out.println("1 + 2 = " + (1 + 2));
  The parentheses in the second statement ensures that the second + operator performs addition instead of string concatenation
 
 
What does the following code fragment print?
System.out.println(1 + 2 + "abc");
System.out.println("abc" + 1 + 2);
Answer: 3abc and abc12, respectively. The + operator is left associative, whether it is string concatenation or arithmetic plus.

http://introcs.cs.princeton.edu/java/11precedence/



  • Operator Precedence and Associativity

Operator precedence is why the expression 5 + 3 * 2 is calculated as 5 + (3 * 2), giving 11, and not as (5 + 3) * 2, giving 16.
We say that the multiplication operator (*) has higher "precedence" or "priority" than the addition operator (+), so the multiplication must be performed first.

Operator associativity is why the expression 8 - 3 - 2 is calculated as (8 - 3) - 2, giving 3, and and not as 8 - (3 - 2), giving 7.
We say that the subtraction operator (-) is "left associative", so the left subtraction must be performed first. When we can't decide by operator precedence alone in which order to calculate an expression, we must use associativity.


Since the operators + and - have the same precedence, and are left-associative, the following expressions are all equivalent:
x + 3 - y + 5
(x + 3) - y + 5
((x + 3) - y) + 5
((x + 3) - y + 5)

Since the operators =, += and -= have the same precedence, and are right-associative, the following expressions are all equivalent:
x = y += z -= 4
x = y += (z -= 4)
x = (y += (z -= 4))
(x = y += (z -= 4))


http://docs.roxen.com/pike/7.0/tutorial/expressions/operator_tables.xml





  • Operator associativity

In programming languages and mathematical notation, the associativity (or fixity) of an operator is a property that determines how operators of the same precedence are grouped in the absence of parentheses.

The choice of which operations to apply the operand to, is determined by the "associativity" of the operators. Operators may be left-associative (meaning the operations are grouped from the left), right-associative (meaning the operations are grouped from the right) or non-associative (meaning there is no defined grouping).

Consider the expression a ~ b ~ c.
If the operator ~ has left associativity, this expression would be interpreted as (a ~ b) ~ c and evaluated left-to-right
If the operator has right associativity, the expression would be interpreted as a ~ (b ~ c) and evaluated right-to-lef

Many programming language manuals provide a table of operator precedence and associativity

Associativity is only needed when the operators in an expression have the same precedence.
Usually + and - have the same precedence.

Consider the expression 7 - 4 + 2.
The result could be  (7 - 4) + 2 = 5
result corresponds to the case when + and - are left-associative

or 7 - (4 + 2) = 1.
+ and - are right-associative.


Usually the addition, subtraction, multiplication, and division operators are left-associative, while the exponentiation, assignment and conditional operators are right-associative.

To prevent cases where operands would be associated with two operators, or no operator at all, operators with the same precedence must have the same associativity.

A detailed example
Consider the expression 5^4^3^2. A parser reading the tokens from left to right would apply the associativity rule to a branch, because of the right-associativity of ^, in the following way:

Term 5 is read.
Nonterminal ^ is read. Node: "5^".
Term 4 is read. Node: "5^4".
Nonterminal ^ is read, triggering the right-associativity rule. Associativity decides node: "5^(4^".
Term 3 is read. Node: "5^(4^3".
Nonterminal ^ is read, triggering the re-application of the right-associativity rule. Node "5^(4^(3^".
Term 2 is read. Node "5^(4^(3^2".
No tokens to read. Apply associativity to produce parse tree "5^(4^(3^2))".

A left-associative evaluation would have resulted in the parse tree ((5^4)^3)^2


http://en.wikipedia.org/wiki/Operator_associativity

No comments:

Post a Comment