Question

Consider the following two syntax-directed definitions SDD1 and SDD2 for type declarations.

SDD1
Grammar (G1): \(D \rightarrow T\,V\); Semantic Rules: \(D.type = T.type;\ V.type = T.type\)
Grammar (G1): \(T \rightarrow int\); Semantic Rules: \(T.type = int\)
Grammar (G1): \(T \rightarrow float\); Semantic Rules: \(T.type = float\)
Grammar (G1): \(V \rightarrow V_1\,id\); Semantic Rules: \(V_1.type = V.type;\ put(id.entry, V.type)\)
Grammar (G1): \(V \rightarrow id\); Semantic Rules: \(put(id.entry, V.type)\)

SDD2
Grammar (G2): \(D \rightarrow D_1\,id\); Semantic Rules: \(D.type = D_1.type;\ put(id.entry, D_1.type)\)
Grammar (G2): \(D \rightarrow T\,id\); Semantic Rules: \(D.type = T.type;\ put(id.entry, T.type)\)
Grammar (G2): \(T \rightarrow int\); Semantic Rules: \(T.type = int\)
Grammar (G2): \(T \rightarrow float\); Semantic Rules: \(T.type = 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 P and Q be the languages specified by grammars G1 and G2, respectively.
Which of the following statements is/are true?

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

Hint:

Both grammars generate (int|float) id+. Check which rules assign INTO a right-hand-side symbol (inherited) versus only read children to set the left-hand-side symbol (synthesized).

Answer 1

The Correct Option is A, B, D

Step 1: Concept.
S-attributed means every attribute used is synthesized (computed bottom-up from children only). L-attributed is the more general class where inherited attributes are allowed, but each inherited attribute of a symbol may only depend on the parent's inherited attributes or on attributes of symbols strictly to its left in the same production (information flows left to right, downward). Every S-attributed SDD is automatically L-attributed, but not conversely.

Step 2: Find the underlying languages P and Q.
In G1, \(V \rightarrow V_1\,id \mid id\) is left recursive and unwinds to one or more concatenated id's: \(id\ id\ \dots\ id\). So \(D \rightarrow T\,V\) generates (int or float) followed by one or more id's, i.e. \(P = \{int, float\}\cdot id^{+}\).
In G2, \(D \rightarrow D_1\,id \mid T\,id\) is also left recursive: the base case \(T\,id\) gives a type followed by one id, and each further \(D_1\,id\) application appends one more id. So \(D\) also generates (int or float) followed by one or more id's, i.e. \(Q = \{int, float\}\cdot id^{+}\).
Both P and Q describe exactly "a type keyword followed by one or more identifiers", so \(P = Q\) as formal languages. Option (A) is TRUE.

Step 3: Classify SDD1's attributes.
\(D.type = T.type\) is synthesized (D gets its value from child T). \(T.type = int/float\) are synthesized (leaf assignments). \(V.type = T.type\) in the D-production assigns V's attribute using a sibling's value - since V is used inside its own subtree as an inherited attribute (passed down from the D-production into the V subtree), this is an INHERITED attribute. Likewise \(V_1.type = V.type\) inside \(V \rightarrow V_1\,id\) passes the parent's inherited value down to the child \(V_1\), again inherited. So SDD1 mixes BOTH synthesized attributes (D.type, T.type) and inherited attributes (V.type). Every rule does respect the left-to-right, parent-to-child flow needed for L-attributedness (each inherited use only depends on the parent or on symbols to the left), so SDD1 IS L-attributed, but it is not true that it contains ONLY inherited attributes - it has synthesized ones too. Option (C)'s claim of "only inherited attributes" is therefore FALSE.

Step 4: Classify SDD2's attributes.
\(D.type = D_1.type\) is synthesized (D gets its value purely from its child \(D_1\)). \(D.type = T.type\) is synthesized (from child T). \(T.type = int/float\) are synthesized. The put(...) actions only ever read a child's already-computed synthesized value (\(D_1.type\) or \(T.type\)); no rule anywhere assigns a value INTO a child from a parent. So every attribute in SDD2 is synthesized, with no inherited attribute at all - SDD2 is S-attributed and uses only synthesized attributes. Option (B) is TRUE.

Step 5: Compare the symbol table entries produced by the two SDDs.
Trace "int id1 id2 id3" through SDD1: \(T.type=int\); this is pushed down as \(V.type=int\) at the outermost V, then re-copied unchanged down through every \(V_1.type=V.type\) step to the innermost V. Every put call therefore uses the same value, int, so \(put(id1,int), put(id2,int), put(id3,int)\) all fire.
Trace the same string through SDD2: base case gives \(D^{(1)} = T\,id1\) with \(T.type=int\), so \(put(id1, T.type=int)\). Then \(D^{(2)} = D^{(1)}\,id2\) with \(D^{(2)}.type = D^{(1)}.type = int\) (a pure copy), so \(put(id2, D^{(1)}.type=int)\). Then \(D^{(3)} = D^{(2)}\,id3\), \(put(id3, D^{(2)}.type=int)\). Since every D.type = D1.type rule is a value-preserving copy chain starting at T.type = int, every put call again uses int.
So for any valid input, both SDDs perform put(id, type) calls with the exact same (identifier, type) pairs - only the direction of information flow (top-down broadcast in SDD1 versus bottom-up relay in SDD2) differs, not the resulting values. Option (D) is TRUE.

Step 6: Conclusion.
(A), (B), (D) are true; (C) is false because SDD1, while correctly L-attributed, is not purely inherited - it also uses synthesized attributes for D.type and T.type.

\[ \boxed{\text{Correct options: (A), (B) and (D)}} \]