GATE CSE 2014 Set 2 | Question: 17

Question

Consider the grammar defined by the following production rules, with two operators $∗$ and $+$

• $S\:\to\:T∗P$
• $T\:\to\:U\mid T∗U$
• $P\:\to\:Q+P\mid Q$
• $Q\:\to Id$
• $U\:\to Id$

Which one of the following is TRUE?

• A. $ +$ is left associative, while $∗$ is right associative
• B. $ +$ is right associative, while $∗$ is left associative
• C. Both $+$ and $∗$ are right associative
• D. Both $+$ and $∗$ are left associative

Answer 1

$P \rightarrow Q+P$ here  $P$ is to right of $+$  

So, $+$ is right associative

Similarly, for  $T \rightarrow T *U$    $*$ is left associative as $T$ is to left of $*$

So, answer is B

Comments

Systematic, way to check associativity and precedence for any operator precedence grammar is using "operator precedence table".
To construct operator precedence table, we first find out "leading" and "trailing" of every Nonterminal then we use these for table construction.

---

But

S ------> T * P

So how can say that * is Left Associative???

---

S -> T * P isn't a recursive production, so it won't define the associativity.

T→T∗U is a recursive production Hence defines left associativity.

---

For leading and trailing:

Ref: here and here

Answer 2

Let us consider the 2nd production
T -> T * U
T is generating T*U recursively (left recursive) so * is 
left associative.

Similarly
P -> Q + P
Right recursion so + is right associative.
So option B is correct.