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

@Sachin Sir

E → E-T | T

T → T/F | F

F →  (G) | G

G → G-id | id

By this we can reduce the redundancy

Comments

@samarpita But it generates redundant string such as: $(id-id)$

Eg: $E→ T → F→ (G) → (G-id) → (id-id)$