how to prove unambiguous ?

The Gateway to Computer Science Excellence

First time here? Checkout the FAQ!

x

+14 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 $-$.

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

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

+12 votes

Best answer

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

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

- All categories
- General Aptitude 1.2k
- Engineering Mathematics 4.9k
- Digital Logic 2k
- Programming & DS 3.6k
- Algorithms 3k
- Theory of Computation 3.9k
- Compiler Design 1.5k
- Databases 2.9k
- CO & Architecture 2.5k
- Computer Networks 2.9k
- Non GATE 949
- Others 1.3k
- Admissions 409
- Exam Queries 419
- Tier 1 Placement Questions 17
- Job Queries 55
- Projects 9

34,781 questions

41,758 answers

118,934 comments

41,400 users