Question

Consider the following two syntax-directed definitions SDD1 and SDD2 for type
declarations.
𝐷 is the start symbol, and 𝑖𝑛𝑡, 𝑓𝑙𝑜𝑎𝑡 and 𝑖𝑑 are the three terminals. The non-terminal
𝑉1 is the same as 𝑉 and the non-terminal 𝐷1 is the same as 𝐷. Here, the subscript is
used to differentiate the grammar symbols on the two sides of a production. The
function 𝑝𝑢𝑡 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?
SDD1
Grammar
(G1)
Semantic Rules
𝐷 →𝑇 𝑉
𝐷. 𝑡𝑦𝑝𝑒 = 𝑇. 𝑡𝑦𝑝𝑒
𝑉. 𝑡𝑦𝑝𝑒 = 𝑇. 𝑡𝑦𝑝𝑒
𝑇 → 𝑖𝑛𝑡
𝑇. 𝑡𝑦𝑝𝑒 = 𝑖𝑛𝑡
𝑇 → 𝑓𝑙𝑜𝑎𝑡
𝑇. 𝑡𝑦𝑝𝑒 = 𝑓𝑙𝑜𝑎𝑡
𝑉→𝑉1 𝑖𝑑
𝑉1. 𝑡𝑦𝑝𝑒= 𝑉. 𝑡𝑦𝑝𝑒
𝑝𝑢𝑡(𝑖𝑑. 𝑒𝑛𝑡𝑟𝑦, 𝑉. 𝑡𝑦𝑝𝑒)
𝑉 → 𝑖𝑑
𝑝𝑢𝑡(𝑖𝑑. 𝑒𝑛𝑡𝑟𝑦, 𝑉. 𝑡𝑦𝑝𝑒)
SDD2
Grammar
(G2)
Semantic Rules
𝐷→𝐷1 𝑖𝑑
𝐷. 𝑡𝑦𝑝𝑒= 𝐷1. 𝑡𝑦𝑝𝑒
𝑝𝑢𝑡(𝑖𝑑. 𝑒𝑛𝑡𝑟𝑦, 𝐷1. 𝑡𝑦𝑝𝑒)
𝐷 → 𝑇 𝑖𝑑
𝐷. 𝑡𝑦𝑝𝑒 = 𝑇. 𝑡𝑦𝑝𝑒
𝑝𝑢𝑡(𝑖𝑑. 𝑒𝑛𝑡𝑟𝑦, 𝑇. 𝑡𝑦𝑝𝑒)
𝑇 →𝑖𝑛𝑡
𝑇. 𝑡𝑦𝑝𝑒 = 𝑖𝑛𝑡
𝑇 → 𝑓𝑙𝑜𝑎𝑡
𝑇. 𝑡𝑦𝑝𝑒 = 𝑓𝑙𝑜𝑎𝑡

• 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:

Check whether the two grammars derive the same set of strings, then classify every attribute in SDD1 and SDD2 as synthesized (computed only from children) or inherited (copied down from a parent or sibling), and finally verify whether both schemes call put() with the same (identifier, type) pairs for any valid declaration.

Answer 1

The Correct Option is A, B, D

A quicker way to settle all four options is to run a concrete declaration, say \(int\ a\ b\ c\), through both grammars and track what each SDD actually computes, rather than staring at the rules in the abstract.

Step 1: Same strings, same language. G1 builds the identifier list bottom-up using \(V \to V_1\ id \mid id\), so it accepts \(T\) followed by any non-empty chain of ids: first \(a\), then \(a\ b\), then \(a\ b\ c\). G2 builds the same list using \(D \to D_1\ id \mid T\ id\), again \(T\) followed by one or more ids. You cannot find a string accepted by one grammar and rejected by the other - both describe exactly 'T followed by a non-empty sequence of ids', so \(P = Q\), which confirms option (A).

Step 2: Where does the type value travel in SDD1? Compute \(T.type = int\) first, bottom-up from the terminal. At \(D \to T\ V\), \(D.type\) is synthesized from \(T\), but \(V.type\) is set equal to \(T.type\) - the value moves from a sibling into a nonterminal that will expand further down, which is exactly what makes it an inherited attribute. The recursive rule \(V \to V_1\ id\) repeats this by setting \(V_1.type = V.type\), again pushing the same value further down the tree. Since \(D.type\) and \(T.type\) are synthesized while \(V.type\) and \(V_1.type\) are inherited, SDD1 is a mixed, L-attributed scheme - not a purely inherited one. So option (C), which claims SDD1 has 'only inherited attributes', overreaches and is false.

Step 3: Where does the type value travel in SDD2? Every rule here computes a value strictly from its children: \(D.type = T.type\) or \(D.type = D_1.type\), and \(T.type\) comes straight from the terminal. No rule ever pushes a value down into an already-expanded child; everything flows upward toward the root. That is precisely the definition of an S-attributed, fully synthesized SDD, so option (B) holds.

Step 4: Does the symbol table end up the same either way? Walking through \(int\ a\ b\ c\): SDD1 fixes the type as \(int\) at the top from \(T\), threads it down through \(V\) and \(V_1\), and fires \(put(id.entry, int)\) once for each of \(a\), \(b\), \(c\). SDD2 fixes \(T.type = int\) at the base of its recursive chain and fires \(put(id.entry, int)\) once as each \(D_1\) layer reduces, again once per identifier. Either way, every identifier in the declaration ends up mapped to \(int\) in the symbol table - the propagation mechanism differs, but the resulting entries are identical, so option (D) is also true.

Putting the four checks together: options (A), (B), and (D) are correct, while (C) is incorrect.

Final answer: (A), (B), (D)