GATE CSE 2019 | Question: 36

Question

Consider the following grammar and the semantic actions to support the inherited type declaration attributes. Let $X_1, X_2, X_3, X_4, X_5$, and $X_6$ be the placeholders for the non-terminals $D, T, L$ or $L_1$ in the following table:

$$\begin{array}{|l|l|} \hline  \text{Production rule} & \text{Semantic action} \\ \hline D \rightarrow T L & X_1.\text{type} = X_2.\text{type} \\ \hline T \rightarrow \text{int} & T.\text{type} = \text{int} \\ \hline T \rightarrow \text{float} & T.\text{type} = \text{float} \\ \hline
L \rightarrow L_1, id & X_3.\text{type}= X_4.\text{type}  \\ 
&\text{addType}(id. \text{entry}, X_5.\text{type})\\ \hline
L \rightarrow id & \text{addType}(id. \text{entry}, X_6.\text{type}) \\ \hline \end{array}$$

Which one of the following are appropriate choices for $X_1, X_2, X_3$ and $X_4$?

• A. $X_1=L, \: X_2=T, \: X_3=L_1, \: X_4 = L$
• B. $X_1=T, \: X_2=L, \: X_3=L_1, \: X_4 = T$
• C. $X_1=L, \: X_2=L, \: X_3=L_1, \: X_4 = T$
• D. $X_1=T, \: X_2=L, \: X_3=T, \: X_4 = L_1$

Comments

same question gate-cse-1992-question-11a

---

All questions related to Syntax Directed Definitions(SDD):

Compiler Design: GATE CSE 1992 | Question: 11a

Compiler Design: GATE CSE 2003 | Question: 18

Compiler Design: GATE CSE 2003 | Question: 59

Compiler Design: GATE CSE 2019 | Question: 36

Compiler Design: GATE CSE 2020 | Question: 33

Compiler Design: GATE CSE 2024 | Set 1 | Question: 27

Compiler Design: GATE CSE 2024 | Set 2 | Question: 19

Compiler Design: GATE CSE 2025 | Set 2 | Question: 12

---

https://youtu.be/VC4wpru1yRE?si=rmGbgWpVv47X01s9&t=6899

 

Answer 1

A node in a parse tree can $\text{INHERIT}$ an attribute either from its parent or its siblings. This means for a production
$$S \to AB,$$ $A$ can inherit values from either $S$ or $B$ and similarly $B$ can inherit values from either $S$ or $A.$

In the given productions, for

$L \to L_1, id,$

$L_1$ can inherit from $L$ or $,$ or $id$ with only $L$ being a non-terminal.

So, this means $X_3$ must be $L_1$ and $X_4$ must be $L$ as $X_i$ is a placeholder for non-terminals. 

Only option A matches this. 

Comments

@samarpita you are confusing inherited attributed grammar with L-attributed grammar . 
In case of L-attributed grammar A can take value only from inherited attributes of S but in case of inherited attributes A can take values from  S or B .

note :- every L attributed grammar is inherited attributed grammar but every inherited grammar is not L-attributed.

---

can we calculate X5 and X6 from given information?

---

Can we also say that except option A, all the other options use assign T to either L3 or L4, but T is not used in the fourth production rule so we can discard those options and A becomes correct?

Answer 2

Inherited attributes :a attribute that gets its values from the attributes attached to the parent (or siblings) of its non-terminal.

Now in question first semantics $X1 \cdot \text{Type} = X2 \cdot \text{Type}$. $X1$ inherit value from $X2$  it means $X1$ can be $L$ or $T$ same for $X2$. Option C ruled out.

$X3 \cdot \text{type}=X4 \cdot \text{type} X3$ should be  $L1$  and $X4$ should be $L$ according to definition. Option B,D ruled out

So answer is A

https://en.m.wikipedia.org/wiki/Attribute_grammar

Comments

Very good explanation. Cleared all my doubts :)

---

Thanks ,Easy way to approach the question

Answer 3

See might be it works. PLZ view page 1 then page 2 for better understanding. Also take a input example and yrself verify the situation :

Comments

what's the source for images ?

---

myself ….

Answer 4

option 1 

see given example https://www.geeksforgeeks.org/s-attributed-and-l-attributed-sdts-in-syntax-directed-translation/

Answer 5

The production
L → L1, id {X3.type = X4.type } ,

Above production has L and L1, hence X3 and X4 can not be T.
So option 1, 3 and 4 cannot be correct.
Hence, A is the correct answer.

Answer 6

Since the production,

L → L1, id {X3.type = X4.type } , this production has L and L1, hence X3 and X4 cannot be T.

So option B, C and D cannot be correct.

Hence, A is correct answer.