Associativity of Operators
Introduction: By convention, 9 5 2 is equivalent to (9 5) 2 and 9-5-2 is equivalent to ( 9 - 5 ) - 2 . When an operand like 5 has operators to its left and right, conventions are needed for deciding which operator applies to that operand. We say that the operator associates to the left, because an operand with plus signs on both sides of it belongs to the operator to its left. In most programming languages the four arithmetic operators, addition, subtraction, multiplication, and division are left-associative.
Some common operators such as exponentiation are right-associative. As another example, the assignment operator = in C and its descendants is right associative; that is, the expression a=b=c is treated in the same way as the expression a=(b=c).
Strings like a=b=c with a right-associative operator are generated by the following grammar:
Example: A grammar for arithmetic expressions can be constructed from a table showing the associativity and precedence of operators. We start with the four common arithmetic operators and a precedence table, showing the operators in order of increasing precedence. Operators on the same line have the same associativity and precedence:
left-associative: * /
We create two non-terminals expr and term for the two levels of precedence, and an extra nonterminal factor for generating basic units in expressions. The basic units in expressions are presently digits and parenthesized expressions.
factor —> digit | ( expr)
Now consider the binary operators, * and /, that have the highest precedence. Since these operators associate to the left, the productions are similar to those for lists that associate to the left.
term —> term * factor
| term / factor
Similarly, expr generates lists of terms separated by the additive operators.
expr —> expr term
| expr - term
The resulting grammar is therefore
expr -» expr term \ expr - term \ term
term -> term * factor | term / factor | factor
factor ->• digit | ( expr)
Generalizing the Expression Grammar of above Example :We can think of a factor as an expression that cannot be "torn apart" by any operator. By "torn apart," we mean that placing an operator next to any factor, on either side, does not cause any piece of the factor, other than the whole, to become an operand of that operator. If the factor is a parenthesized expression, the parentheses protect against such "tearing," while if the factor is a single operand, it cannot be torn apart.
A term (that is not also a factor) is an expression that can be torn apart by operators of the highest precedence: * and /, but not by the lower-precedence operators. An expression (that is not a term or factor) can be torn apart by any operator.
We can generalize this idea to any number n of precedence levels. We need n 1 non-terminal. The first, like factor in Example 2.6, can never be torn apart. Typically, the production bodies for this nonterminal are only single operands and parenthesized expressions. Then, for each precedence level, there is one nonterminal representing expressions that can be torn apart only by operators at that level or higher. Typically, the productions for this nonterminal have bodies representing uses of the operators at that level, plus one body that is just the nonterminal for the next higher level.
With this grammar, an expression is a list of terms separated by either or - signs, and a term is a list of factors separated by * or / signs. Notice that any parenthesized expression is a factor, so with parentheses we can develop expressions that have arbitrarily deep nesting (and arbitrarily deep trees).