GATE CSE 2000 | Question: 19

Question

Consider the syntax directed translation scheme $\textsf{(SDTS)}$ given in the following. Assume attribute evaluation with bottom-up parsing, i.e., attributes are evaluated immediately after a reduction.

• $E\rightarrow  E_{1} * T \qquad \{E.val = E_{1}.val * T.val\}$
• $E\rightarrow  T \qquad \qquad \{E.val = T.val\}$
• $T\rightarrow  F - T_{1}\qquad \{T.val = F.val - T_{1}.val\}$
• $T\rightarrow F \qquad \qquad \{T.val = F.val\}$
• $F\rightarrow 2 \qquad \qquad \{F.val = 2\}$
• $F\rightarrow 4 \qquad \qquad \{F.val = 4\}$

• A. Using this $\textsf{SDTS},$ construct a parse tree for the expression $4 - 2 - 4 * 2$  and also compute its $E.val$.
• B. It is required to compute the total number of reductions performed to parse a given input. Using synthesized attributes only, modify the $\textsf{SDTS}$ given, without changing the grammar, to find $E.red$, the number of reductions performed while reducing an input to $E$.

Comments

$-$ is farthest from the start symbol, and $*$ is nearest to the start symbol, therefore, $-$ has higher precedence than $*$. $-$ is right associative as if an expression contains more than one $-$ then tree will grow towards right side, and $-$ present at the lower part of the tree towards right side will be evaluated before the $-$ present at the upper part of the tree towards left side, as Production T is right recursive.

So, expression will evaluate to 12.

---

Dont assume precedence of operator by yourself always take care of precedence and associativity given in question.

---

I wonder what would have been different in B section if, instead of using “Synthesized Attribute” we use inherited attribute?

---

Solve by the help of precednce and associativity

parse tree is time taking

---

All questions related to Syntax Directed Translation Scheme(SDTS):

Compiler Design: GATE CSE 1995 | Question: 2.10

Compiler Design: GATE CSE 1996 | Question: 20

Compiler Design: GATE CSE 2000 | Question: 19

Compiler Design: GATE CSE 2016 Set 1 | Question: 46

Compiler Design: GATE CSE 2021 Set 1 | Question: 26

Compiler Design: GATE CSE 2022 | Question: 55

Compiler Design: GATE CSE 2023 | Question: 50

Compiler Design: GATE CSE 2003 | Question: 58

Compiler Design: GATE CSE 2004 | Question: 45

Compiler Design: GATE CSE 2006 | Question: 59

Answer 1

   Given expression $4-2-4*2$

Total reductions = 10

1. Expression value, $E.val = 12$
2. Total number of reductions performed, $E.red = 10$ (number of non-leaf nodes in the parse tree)

Part B Explanation: https://gateoverflow.in/690/gate-cse-2000-question-19?show=136436#a136436 

Comments

number of reductions is nothing but the number of non-leaves in the parse tree ...

---

Please explain part B of the question.

---

@Hira Thakur From the perspective of parsing the input its not necessary to  compute the total number of reductions. 

Answer 2

SDTS to find the number of reductions::

E→ E1 * T {E.red = E1.red+ T.red+1}

E→T {E.red = T.red+1}

T→F - T1 {T.red = F.red + T1.red+1}

T→F {T.red = F.red+1}

F→2 {F.red = 1}

F→4 {F.red = 1}

Comments

@VS ,you can edit the selected answer to include this as part b answer.

Answer 3

A. Given Expression is 4 - 2 - 4 * 2 , which can be rewritten as ((4 - (2 - 4))* 2) which is equal to 12.

Comments

how do we know that minus '-' is right to left?

---

second minus is at lower level than 1st minus so first 2-4=-2 then 4-(-2)=6 then 6*2 since is at higher level