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: Restart from first principles on each of the four claims, using the formal definitions of synthesized/inherited/S-attributed/L-attributed directly rather than tracing an example first.

Step 2: Language equality (A). Strip both grammars down to their bare terminal-generating skeletons, ignoring the semantic actions entirely (they do not affect the language, only the actions attached to it). G1: \(D \to T\,V\), \(T \to int \mid float\), \(V \to V\,id \mid id\) - this is a standard left-recursive list grammar equivalent to the regular expression \((int\mid float)\,id^{+}\). G2: \(D \to D\,id \mid T\,id\), \(T \to int \mid float\) - unwinding the recursion, the base \(T\,id\) forces exactly one type keyword then one id, and each subsequent \(D\,id\) appends exactly one more id, with no way to introduce a second type keyword; this is also exactly \((int\mid float)\,id^{+}\). Two grammars generating the identical regular expression generate the identical language, so \(P=Q\): (A) holds.

Step 3: Attribute typing by definition. An attribute is synthesized if its rule computes it from the attributes of the symbols on the RIGHT-hand side of the SAME production where it is the LEFT-hand-side symbol's attribute (children -> parent, or terminal -> itself). An attribute is inherited if the rule assigns a value to a RIGHT-hand-side occurrence of a symbol, using the parent's or a left sibling's attributes (parent/left-sibling -> a child).

Step 4: Apply this test to SDD2 rule by rule. \(D.type = D_1.type\): LHS is D (the production's head), RHS reference is \(D_1\) (a right-hand-side child) - value flows child to parent, synthesized. \(D.type = T.type\): same shape, synthesized. \(T.type = int\) / \(= float\): constant assigned to the head with no RHS symbols at all (T is a terminal-only production), trivially synthesized. No rule in SDD2 ever assigns to a RHS occurrence using the parent - so there are zero inherited attributes; SDD2 is S-attributed. (B) holds.

Step 5: Apply the same test to SDD1. \(D.type = T.type\) and \(T.type=int/float\) are synthesized exactly as before. But \(V.type = T.type\) in production \(D \to T\,V\): here V is a RIGHT-hand-side symbol of THIS production (whose head is D), and its attribute is being set using T (a left sibling) - this is precisely the inherited-attribute pattern (assigning into a RHS occurrence). Similarly \(V_1.type = V.type\) in \(V \to V_1\,id\) assigns into the RHS occurrence \(V_1\) using the parent V's value - inherited again. So SDD1 provably contains both kinds: synthesized (D.type, T.type) and inherited (V.type at every level). Because every inherited assignment here only ever uses the parent's inherited value or a strictly-left sibling's synthesized value, and every synthesized rule only reads RHS children, the ordering constraint for L-attributedness is satisfied throughout, so SDD1 is L-attributed - but NOT purely inherited. This directly falsifies (C).

Step 6: Symbol table entries (D), verified by unfolding the copy-chains abstractly rather than a specific example. In SDD1, V.type is set once at the top from T.type and then relayed unchanged down every \(V_1.type=V.type\) link to every id in the list; every put therefore stores T.type for every id. In SDD2, D.type is likewise a straight copy chain \(D.type = D_1.type = \dots = T.type\) all the way down to the base case, and every put call reads the type at the point of that copy chain, which is always T.type, since copying never changes a value. Both SDDs therefore always store T.type against every id in the declaration, so they add identical entries to the symbol table for any valid declaration. (D) holds.

Step 7: Final tally: (A) true by direct language derivation, (B) true because SDD2's rules never assign into a right-hand-side occurrence, (C) false because SDD1 demonstrably has synthesized attributes too, (D) true because both copy-chains always deliver the same T.type value to every put call.

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