GATE CSE 1991 | Question: 10b

Question

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)

Does the grammar allow expressions with redundant parentheses as in $({id}/{id})$ or in $id -({id}/{id})$ ? If so, convert the grammar into one which does not generate expressions with redundant parentheses. Do this with minimum number of changes to the given production rules and adding at most one more production rule.

Comments

@Sachin Mittal 1 Bhai In the question 

If so, convert the grammar into one which does not generate expressions with redundant parentheses. 

But the one generated contains redundant parenthesis and also they asked to consider increasing atmost one production

---

$E \rightarrow E- T $ $|$ $T$

$E'\rightarrow E-T$

$T \rightarrow T/F $ $|$ $ F/F $ $|$ $  id$

$F \rightarrow (E’) $ $|$ $id$

I guess this shall work. Does not generate expression with any redundant parenthesis.  For eg. $id- (id/id)$ or $(id/id)$ or $(id-id)$

If you find any error in it, please do inform me. I shall try to improvise.

---------------------------------------------------------------------------------------

The above grammar which I tried to write is ambiguous due to the $T$ production.

$$T \rightarrow T/F \rightarrow id / F \rightarrow id/id$$

$$T \rightarrow F/F \rightarrow id / F \rightarrow id/id$$

So the modified grammar, with the problem due to $T$ production removed...

$E \rightarrow E- T $ $|$ $T$

$E'\rightarrow E-T$

$T \rightarrow T'/F $  $|$ $  id$

$T' \rightarrow T'/F $ $|$ $ F$

$F \rightarrow (E’) $ $|$ $id$

---

@HitechGa We are allowed to add atmost 1 prod. and you are adding more than that.

Answer 1

Going  by the rules of the grammar, we can clearly see that the precedence of / is more than that of -(minus).

So, any string of the form like (id/id) here parenthesis are redundant because even if we don't use them, our result won't change.

Second string is id-(id/id). Here if we draw parse tree for expression id-id/id, then we come to realize that since / appears at a lower level than - so it will be evaluated first. So, here also we don't need parenthesis for /.

As you can see in the above parse trees, the problem comes when we allow only division inside the parenthesis.

So, we modify our grammar as

E->E-T | T

T->T/F | F

F->id | (E-T).

Now, in this grammar, I only allow minus to appear inside parenthesis in case I want - to be evaluated first rather than / as for expression id/(id-id) which is possible to generate via this grammar.

Comments

@Ayush

E->E-T | T

T->T/F | F

F->id | (E-T).

Now I can generate $E->T->F->(E-T)->(T-T)->(F-T)->(id-T)->(id-F)->(id-id )$

The generated string has redundant braces

---

@ayush will ((E-T)-T) be redundant in ur grammar?

---

E->E-T | T

T->T/F | id

F->id | (E-T)

What about this is this correct?

and the above grammar is generating (id-id) so we are still having redundant parenthesis in above grammar..

Answer 2

If the expression with redundant parentheses is $(id/id)$ or $id-(id/id)$ then it can be generated by the given grammar. 

To generate expression $(id/id)$ we can go through following steps-

1. $E \rightarrow T$
2. $E \rightarrow F$                   $( T \rightarrow F)$
3. $E \rightarrow (E)$               $( F \rightarrow (E) )$
4. $E \rightarrow (T)$               $( E \rightarrow T)$
5. $E \rightarrow (T/F)$         $( T \rightarrow T/F)$
6. $E \rightarrow (F/F)$        $( T \rightarrow F )$
7. $E \rightarrow ( id/id)$       $(F->id) $

Now to generate expression $id- (id/id)$ we can go through following steps-

1. $E \rightarrow E - T$
2. $E \rightarrow E - F$                $( T\rightarrow  F)$
3. $E \rightarrow E - (E)  $            $( F \rightarrow (E) )$ 
4. $E \rightarrow E - (T)$             $(E \rightarrow T  )$
5. $E \rightarrow E - (T/F)$       $(T \rightarrow T/F)$
6. $E \rightarrow E - (F/F)$       $(T \rightarrow F )$
7. $E \rightarrow T - (F/F)$       $(E \rightarrow T)$
8. $E \rightarrow F - (F/F)$       $(T \rightarrow F)$
9. $E \rightarrow id - ( id/id)$     $(F \rightarrow id) $

Comments

please answer remaining part?

---

@Kapilp, @ManojK sir, @Praveen sir, @Arjun Sir, need your help in the 2nd part of the above question ..

---

A pair of parentheses is redundant if its removal does not algebraically change the expression, 

Given grammar is 

$\large E\rightarrow E-T |T$

$\large T\rightarrow T/F |F$

$\large F\rightarrow \left ( E \right ) |id$

So changinging this to grammar with no redundant parentheses:

$\large E\rightarrow E-T |T$

$\large E'\rightarrow E-T $

$\large T\rightarrow T'/F |id$

$\large T'\rightarrow T'/F |F$

$\large F\rightarrow \left ( E' \right ) |id$

---

Thanks, Now check this please -

L = (Id - id )    // here are have redundant parentheses and can work even without parentheses but above grammar is generating this language too.

E -> T

E -> F

E - > ( E' )

E -> ( E - T )

----

----

 

E - > ( id - id )

 

Am I correct sir.  ?

---

You are saying  ( id - id ) can work even without parentheses .Then how it is redundant parentheses ?

 refunded parentheses ? it is typo rt ? :P

---

yes, my bad ,, that was typo... 

Sir, Read these lines again -

Does the grammar allow expressions with redundant parentheses as in (id/id)(id/id) or in id−(id/id)id−(id/id) ? If so, convert the grammar into one which does not generate expressions with redundant parentheses. 

But, the grammar you explained above generates string (id -id ) which contains redundant parentheses. right ??

Hope you get what I mean...

---

@Manoj it is generating id-(id/id),rt?

By the way , which rule u r following here?

---

What is redundant parathesis?

If you change the parentheses in any expression so if your result is voilating then we can  say there are redundant parathesis.

For example  the parentheses are redundant in $\large id+(id\times id)$ .

but here are $\large (id+id)\times id$ no redundant parentheses .

---

Sir, what about this -  (id/id)    ??

Given in question itself - 

Does the grammar allow expressions with redundant parentheses as in (id/id).

---

@srestha These are the rules:

Parentheses can be redundant for three reasons:

(i) they embrace a division or an atomic id, or

(ii) they embrace the entire expression, or

(iii) they embrace a - that is not preceded or followed by a /.

---

@Vijay No need of sir.

(id/id) is not accpting by changinging this to grammar with no redundant parentheses:you can check.

However it is not creating problem if it is simply (id/id).

But will create problem id-(id/id).Means it will create when in any expression - that is not preceded or followed by a /.

---

https://gateoverflow.in/?qa=blob&qa_blobid=3841078254152065180

Vijay you can check the same think here.

Exercise 4 Page 8.

---

Thanks, got the point ... :)

---

@Manoj E is not derived in your production.

$T\rightarrow T'/F | F$

$T\rightarrow (E) | id$

$E\rightarrow id-id$

$F\rightarrow id$

it is also possible right?

---

@Manojk @sachin mittal 1 can u  explain how did u make the grammar? what logic u used?

---

For example  the parentheses are redundant in id+(id×id)id+(id×id) .

but here are (id+id)×id(id+id)×id no redundant parentheses .

 @Shrestha pls explain this

---

(id-id) is generated by the above grammer,but this is reduntant paranthesis as it is embracing the entire expression.@srestha please check

Removal of the paranthesis here,does not changing the meaning,

---

@rahul sharma 5, Can you please show the derivation for $(id-id)$ ?

Answer 3

E->E-T | T

E' → E - T 

T->T/F | F

F->id | (E’).

 

i hope this would also work

Answer 4

Here the Grammar is modified in a such way to prevent the following configuration that it should prevent (id/id)

 so initially (E) we  will replace the access that id/id  can be  within brackets

so lets change the grammar to 

E->E-T | T

E' → E - T 

T->T/F | F

F->id | (E’).

so adding further more depth

 

 

if we clearly observe it can generate (id-id) which is again redundant so now we should make sure that () will be accessible to the string if there is an  ‘/’  in the string 

 

so to not allow it directly acess the level is pushed even more further 

 

 

E → E - T | T
E' → E - T 
T → T'/ F |  id
T' →   T' / F | F 
F →  (E') | id 

 

Here the  (id-id) is  only possible if there is atleast an  ‘/ ‘  int the string  the 

derivations  

T → T'/ F |  id
T' →   T' / F | F 

prevent (id-id) generated  directly