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

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