The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+14 votes
846 views
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 $-$.
asked in Compiler Design by Veteran (59.4k points) | 846 views
0
how to prove unambiguous ?
+2

@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. 

2 Answers

+12 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 "-".

answered by Boss (25.6k points)
edited by
+1
can u plzz show how did u decide d precedency of - and /
+3
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..
+1
It doesn't define precedence, bcoz of last production, (-) can go deeper than (/) in the parse tree.
+3 votes
It is unambiguous grammar and the precedence of / is higher than -.
answered by Junior (569 points)

Related questions



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

34,781 questions
41,758 answers
118,934 comments
41,400 users