GATE CSE 1991 | Question: 10c

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.

Convert the grammar obtained above into one that is not left recursive.

Comments

plz explain  expressions with redundant parentheses ....????

---

Thanks @Rajesh Pradhan ji

Refer 

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

Read Page No. 8 -Exercise-4

Answer 1

Here we have to convert the grammar into one which does not generate expressions with redundant parentheses.So the grammar which does not generate expressions with redundant parentheses

• $E\rightarrow E-T\mid T$
• $E'\rightarrow E-T$
• $T\rightarrow id\mid T'/F$
• $T'\rightarrow F\mid T'/F$
• $F\rightarrow id\mid \left ( E' \right )$

Now equivalent grammar after removing left recursion

• $E\rightarrow TX'$
• $X'\rightarrow -TX'\mid \epsilon$
• $E'\rightarrow E-T$
• $T\rightarrow id\mid T'/F$
• $T'\rightarrow FY'$
• $Y'\rightarrow /FY'\mid \epsilon$
• $F\rightarrow id\mid \left ( E' \right )$

Comments

what is redundant i did not get it .

"parentheses are redundant in id + (id * id) or id * (id) but not in (id + id) * id."

please explain 

---

E → T E’

E’ → -TE’ | ͼ

T → FT’

T’ → / FT’ | ͼ

F→ (E) | id

Isn’t it correct?

---

Adding X’ is enough for ans. We don’t need to add new production T’. In question also it is given that we can add at most one production. Please correct me if I am wrong.