The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
+12 votes

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?

  1. $ +$ is left associative, while $∗$ is right associative
  2. $ +$ is right associative, while $∗$ is left associative
  3. Both $+$ and $∗$ are right associative
  4. Both $+$ and $∗$ are left associative
asked in Compiler Design by Veteran (101k points) | 1.1k views

3 Answers

+23 votes
Best answer

$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

answered by Boss (31.6k points)
edited by
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.

S ------> T * P

So how can say that * is Left Associative???
+3 votes
answer - B
answered by Loyal (9k points)
+3 votes
Let us consider the 2nd production
T -> T * U
T is generating T*U recursively (left recursive) so * is 
left associative.

P -> Q + P
Right recursion so + is right associative.
So option B is correct. 
answered by Loyal (8.4k points)

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

39,439 questions
46,623 answers
57,017 users