GATE CSE 2022 | Question: 55

Question

Consider the following grammar along with translation rules.
$$\begin{aligned} & S \rightarrow S_{1} \# T \qquad \{S._{\text{val}} =S_{1}. _{\text{val}} \; ^{\ast} T._{\text{val}}\}\\ & S \rightarrow T \qquad \qquad \{S._{\text{val}} = T._{\text{val}}\}\\  & T \rightarrow T_{1} \% R \qquad  \{T._{\text{val}} =T_{1}._{\text{val}} ÷ R._{\text{val}}\}\\  & T \rightarrow R \qquad \qquad \{T._{\text{val}} = R._{\text{val}}\} \\ & R \rightarrow \text{id} \qquad \qquad \{R._{\text{val}} = \text{id}._{\text{val}}\} \end{aligned}$$
Here $\#$ and $\%$ are operators and $\text{id}$ is a token that represents an integer and $\text{id}._{\text{val}}$ represents the corresponding integer value. The set of non-terminals is $\{\text{S, T, R, P}\}$ and a subscripted non-terminal indicates an instance of the non-terminal.

Using this translation scheme, the computed value of $S._{\text{val}}$ for root of the parse tree for the expression $20 \# 10 \% 5 \# 8 \% 2 \% 2$ is ________________.

Comments

plz sir  in question also mention how much mark the given question

---

just simple rule 

which operator  is more away from start symbol  its  have high precedence 

and associtivity checked by  given production of the terminal if it is begining of  the RHS side of the  production  then it is left associativity  and end  side  of the  given RHS side production then it is  right associativity

According to given Question  

seeing grammer 

# operator come before % operator from the start symbol 

so precedence of % operator is > # operator 

and associativity of % is left and # is also left

given semantic action % equivalent to devision

and                           # equivalent to  product

lets  given string 

20#10%5#8%2%2

lets parenthesis according to precedence and associativity

[{20#(10%5)}#{((8%2)%2)}]

[{20#2}#{(4%2)}]

[{20#2}#2}]

80

---

1.Replace the symbols with the Actions here;   # ---> *   and    % ----> /
2.Check the productions if Left recursive or Right recursive , accordingly apply brackets left associative or right associative. respectively.
 

Here * and / are left associative

So, => 20 * 10 / 5 * 8 / 2 / 2 

      => [ { 20 * (10 / 5) } * ( (8 / 2) / 2 ) ]   

      =>  [ {20 * 2} * 2 ] =  80   Ans

---

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

 

Final Answer: $80$

---

General Rules

Operators which are deeper in the parse tree have higher precedence, since they are tried by the parser first.

• Left-recursive rules indicate left associativity.
• Right-recursive rules indicate right associativity.

---

Mapping of Operators

$\#$ corresponds to operation $*$
$\%$ corresponds to operation $\div$

Both $*$ and $\div$ are left associative, and $\div$ has higher precedence.

---

Given Expression

$20\#10\%5\#8\%2\%2$

Replacing operators with their actual meanings:

$\equiv 20 * (10 \div 5) * ((8 \div 2) \div 2)$

---

Evaluation using Precedence and Associativity

$\equiv 20 * \underbrace{(10 \div 5)}_{\text{= 2}} * \underbrace{((8 \div 2) \div 2)}_{\text{= (4 ÷ 2) = 2}}$

$\Rightarrow 20 * 2 * 2$

$\Rightarrow \underbrace{(20 * 2)}_{\text{= 40}} * 2$

$\Rightarrow 80$

---

Final Computed Value

$\boxed{S.val = 80}$

Hence, the value of the given expression is $80$.

---

Concept Summary

• Operator precedence is governed by depth in the parse tree.
• Left recursion ⟶ Left associativity
• Right recursion ⟶ Right associativity
• $\div$ binds tighter than $*$, hence evaluated first.

Comments

how devide operator has higher precedance sir? don't multiply and devide has same priority? (As per operator precedance charts)?

Answer 2

Given that, 20#10%5#8%2%2

if we observe the grammar, we can understand the following points

1. # has less priority than %
2. % has left associative.
3. # has left associative.

So we have to evaluate the given expression as : $\underbrace{\color{red}{(} \color{blue}{(}\underbrace{20\#(\underbrace{10\%5}}) \color{blue}{)} \# \underbrace{\color{green}{(} \color{cyan}{(}\underbrace{8\%2\color{cyan}{)}} \%2\color{green}{)}}\color{red}{)}}$

$= \underbrace{\color{red}{(} \underbrace{\color{blue}{(}20\#2\color{blue}{)}}\#2\color{red}{)}}=80$

Comments

plz sir correct ur  given string in the question

Answer 3

just simple rule 

which operator  is more away from start symbol  its  have high precedence 

and associtivity checked by  given production of the terminal if it is begining of  the RHS side of the  production  then it is left associativity  and end  side  of the  given RHS side production then it is  right associativity

According to given Question  

seeing grammer 

# operator come before % operator from the start symbol 

so precedence of % operator is > # operator 

and associativity of % is left and # is also left

given semantic action % equivalent to devision

and                           # equivalent to  product

lets  given string 

20#10%5#8%2%2

lets parenthesis according to precedence and associativity

[{20#(10%5)}#{((8%2)%2)}]

[{20#2}#{(4%2)}]

[{20#2}#2}]

80

Answer 4

Associativity decreases Top to Down  OR  Increases  Down to Top

1.Replace the symbols with the Actions ;   here   # ---> *   and    % ----> /
2.Check the productions if Left recursive or Right recursive , accordingly apply brackets left associative or right associative respectively.
 

Here  *  and  /   both are left associative since left recursive grammar.

So, => 20 * 10 / 5 * 8 / 2 / 2 

      => [ { 20 * (10 / 5) } * ( (8 / 2) / 2 ) ]   

      =>  [ {20 * 2} * 2 ] =  80   Ans