in Compiler Design edited by
17 votes

Consider the following grammar for arithmetic expressions using binary operators $-$ and $/$ which are not associative

  • $E \rightarrow E -T\mid T$
  • $T \rightarrow T/F\mid F$  
  • $F \rightarrow (E) \mid id$

($E$ is the start symbol)

Is the grammar unambiguous? Is so, what is the relative precedence between  $-$ and $/$? If not, give an unambiguous grammar that gives $/$ precedence over $-$.

in Compiler Design edited by


how to prove unambiguous ?

@set2018 to prove if a grammar is unambiguous is undecidable. we can try to see if the given grammar is LL(k) or LR(k) since they are unambiguous. note that unambiguity does not imply the grammar is LL(k) or LR(k). The grammar in the question is not LR(1). so unambiguity should be concluded by careful observation. 


Recursion handles associativity

Level handles precedence.

2 Answers

17 votes
Best answer

Yes. It is unambiguous grammar since for any string no more than $1$ parse tree is possible.

For precedency draw the parse tree and find the depth of operator -   and  

Here "/" having more depth than " - " operator so precedency of" /"  is higher than "-".

edited by


can u plzz show how did u decide d precedency of - and /
Sunita.. We don't decide the precedence.. We can check this by seeing the grammar given above..

See the grammar is always written in such a way that the operator which have high precedence must lie in the lower part of grammar.  As you can see in above grammar operator / lies below the operator - which means / has high precedence than -  

Similarly you will always see Id comes in last because it is operand which has highest precedence above operators also..
It doesn't define precedence, bcoz of last production, (-) can go deeper than (/) in the parse tree.
Precedence of - and / are changing for different strings. e.g., For id-id/id, here if we draw a tree then we find '/' below '-', it means here '/' has higher precedence than '-'. But if we draw a tree for id/(id-id), in this case the precedence of '-' is higher than '/'.

So how we can say that the precedence of '/' is always higher than '-'?? Please explain.
@aditya precedence of any operator will not be determine by input strings ,it will be determine by given grammar ,,,operator in any production will have higher precedence than all operators which are present in above level production in given grammar
Thanks...I got it...
yes unambigous as precedence and Associativity both taken care of
For the string "id1 - ( id2 / (id3-id4))" second "-" operator has more precedence than "/" operator. Now how can we say surely that "/" has more precedence than "-"?
@commenter commenter

actually, ( ) is having higher precedence than both - or / because in any parse tree, () will always come at bottom. So in your example, since () is evaluated first,  within () again alwz / will have higher precedence than -.

@Raas Star As you said let us say that / has higher precedence as it is within () then how is "id2/(id3-id4))" evaluated? We just know left operand we dont know the value of right operand. For that we surely need to evaluate - first instead of /. The issue is because of last grammar production where 1st Non terminal is again called. So I think there is no concept of precedence here. We can make parse tree where - has more precedence than / and another where / has more precedence than -.  

3 votes
It is unambiguous grammar and the precedence of / is higher than -.

Related questions