edited by
3,977 views
14 votes
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)

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.

edited by

5 Answers

14 votes
14 votes

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.

6 votes
6 votes

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) $
edited by
0 votes
0 votes

E->E-T | T

E' → E - T 

T->T/F | F

F->id | (E’).

 

i hope this would also work

0 votes
0 votes

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

 

 

Related questions

22 votes
22 votes
3 answers
3