GATE CSE 2026 | Set 1 | Question: 43

Question

​​​​​​Consider the following two syntax-directed definitions $\text{SDD1}$ and $\text{SDD2}$ for type declarations.

 

SDD1
Grammar (G1)	Semantic Rules
$D \rightarrow T\ V$	$D.type = T.type$ $V.type = T.type$
$T \rightarrow \text{int}$	$T.type = \text{int}$
$T \rightarrow \text{float}$	$T.type = \text{float}$
$V \rightarrow V_1\ \text{id}$	$V_1.type = V.type$ $\text{put(id.entry, V.type)}$
$V \rightarrow \text{id}$	$\text{put(id.entry, V.type)}$

 

SDD2
Grammar (G2)	Semantic Rules
$D \rightarrow D_1\ \text{id}$	$D.type = D_1.type$ $\text{put(id.entry, D_1.type)}$
$D \rightarrow T\ \text{id}$	$D.type = T.type$ $\text{put(id.entry, T.type)}$
$T \rightarrow \text{int}$	$T.type = \text{int}$
$T \rightarrow \text{float}$	$T.type = \text{float}$

$D$ is the start symbol, and int, float and id are the three terminals. The non-terminal $V_{1}$ is the same as $V$ and the non-terminal $D_{1}$ is the same as $D$. Here, the subscript is used to differentiate the grammar symbols on the two sides of a production. The function put updates the symbol table with the type information for an identifier.

Let $\text{P}$ and $\text{Q}$ be the languages specified by grammars $\text{G1}$ and $\text{G2}$, respectively.
Which of the following statements is/are true?

• A. The languages $\text{P}$ and $\text{Q}$ are the same
• B. $\text{SDD2}$ is $\text{S}$-attributed and contains only synthesized attributes
• C. $\text{SDD1}$ is $\text{L}$-attributed and contains only inherited attributes
• D. The specifications of $\text{SDD1}$ and $\text{SDD2}$ are such that the same entries get added to the symbol table

Comments

Option D means that for any valid input declaration string, both syntax-directed definitions (SDD1 and SDD2) will insert the exact same identifiers with the exact same data types into the symbol table.

Answer 1

First, analyze the type of SDDs

SDD1:

It is L-attributed, because attributes depend on parent and left sibling

Here, $V.type = T.type$ (from left sibling), in $D \rightarrow T\ V$

and $V_1.type = V.type$ (from parent), in $V \rightarrow V_1\ id$

So inherited attributes are used

Also, $D.type = T.type$, so synthesized attributes are also present

Hence, SDD1 has both inherited and synthesized attributes

Option $C$ is false

---

SDD2:

$D \rightarrow D_1\ id \quad \text{and} \quad D \rightarrow T\ id$

It is S-attributed, since all attributes are computed from children only

No inherited attributes are used

Option $B$ is true

---

Now, language comparison:

So both generate the same language

Option $A$ is true

---

Symbol table entries:

In SDD1, put() is called in productions 4 & 5 of $V$ when $id$ is introduced

In SDD2, put() is called in productions 1 & 2 of $D$ when $id$ is introduced

Option $D$ is true

Comments

very nice explanation!! thanks bro!

Answer 2

First of all, 

put() matlab kuch nahi hai bas table mai entries enter karo so don't consider them now.

 

A -  Grammar ko dekho sirf, Semantic rules ignore karo.

G1 generates 

                      int a 

                      float a 

                      int a b 

                      float a b 

                      int a b c 

                      float a b c 

i.e. (type) (one or more identifiers)

 

G2 generates

                      D id 

                      D id id 

                      T id id id 

                      int id id id / float id id id 

i.e. again (type) (one or more identifiers)

Dono Same hi grammar generate kar rahe hai

So, Statement 1 is true

 

Now, Analyze SDD1

Grammar :          D → TV

Rules :                D.type = T.type  ......child to parent, hence synthesized  

                            V.type = T.type​  ......left sibling to right sibling, hence inherited 

 

Bass, grammar aage check karne ki jarurat nahi hai, 

Synthesized + Inherited = L - attributed

 

But, C - hame bata raha hai ki SDD1 is only inherited attributes, hence WRONG

 

Abb, Let's Analyze SDD2 

jab dyan se dekhoge toh bata chalega, 

every production is child to parent, Hence only Synthesized = S - attributed.

Hence, B - SSD2 is S-attributed and contains only synthesized attributes  is Right 

 

Abb, sirf symbol table mai entries check karni hai 

SDD2 mai     put(id.entry, T.type) ......and T.type can be int/float

Similarly, 

SDD1 mai     put(id.entry, V.type) ......and upar hi likha hai, 

                                                          V.type=T.type   and    again T.type can be int/float

 

Hence, both gets/stores same entries in symbol table

Statement 4 is also Right.