CODEWITHSUNDEEP
associative
FloydChen
FloydChen

Reputation: 445

associativity of parentheses

This msdn link says that '(' and ')' has left to right associativity.

How does that make sense? Can someone give me a example?

Upvotes: 0

Views: 2229

Answers (2)

Jesus is Lord
Jesus is Lord

Reputation: 15399

In formal grammars an operator with left-to-right precedence is left recursive. So with binary addition:

S -> E
E -> E + a
E -> a

So the tree would look like:

    S
    |
    E
    |
  E + a
  |
E + a
|
a

As you can see the first two a's are added before the second two.

For a right-associative operator, your grammar would contain right-recursion. So with binary exponentiation:

S -> E
E -> a ** E
E -> a

Subsequently your parse tree would look like:

    S
    |
    E
    |
  a ** E
       |
     a ** E
          |
          a

As you can see the last two a's are exponentiated, first, and the result of that is the power of the first a (this is the proper associativity for exponentiation, by the way).

For ternary and greater operators the same pattern is applied, the recursive rule is either the left-most nonterminal or the right-most nonterminal. In the case of unary operators, though, whether or not it's left- or right-recursive depends on whether or not the nonterminal s on the left or right, respectively. In the case of ( E ) there is a terminal on either side, and the nonterminal, although recursive, is neither left- nor right-recursive from a grammatical point of view so I think the MSDN article has arbitrarily declared it to be "left to right."

The associativity of parenthesis has no bearing on the fact that d is evaluated prior to a+b+c in d+(a+b+c) and has no bearing on the associativity of a+b+c as well, so I have no idea what the other Jared is talking about.

Upvotes: 2

Jared
Jared

Reputation: 6060

What is unclear? They come in a pair whenever you have a ( you will have a ). Once inside of them you work the arythmatic from left to right so if you have d+(a+b+c) you will do a+b then the sum of a+b added to c then the total sum of a,b,c added d

Upvotes: 0

Related Questions