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

This question compares two syntax directed definitions (SDDs) for type-declaration statements and asks which claims about the generated languages, the nature of the attributes used, and the resulting symbol-table entries are correct.

Step 1: Language generated by G1 and G2. In G1, \(D \to T\ V\) with \(V \to V_1\ id \mid id\). Since \(V\) recursively appends one \(id\) at a time, \(V\) derives one or more identifiers, so \(D\) derives \(T\) followed by one or more \(id\)'s. In G2, \(D \to D_1\ id \mid T\ id\), which is again left recursive: the base case \(T\ id\) gives a single identifier, and each further application of \(D \to D_1\ id\) appends one more identifier. Both grammars therefore generate exactly the language \(\{T\ id^n : n \geq 1\}\), so \(P = Q\). Statement (A) is true.

Step 2: Attribute classification in SDD1. For \(T \to int\) and \(T \to float\), \(T.type\) is computed purely from the terminal, so it is synthesized. For \(D \to T\ V\), \(D.type = T.type\) is synthesized from the child \(T\), but \(V.type = T.type\) copies a value from the sibling \(T\) down into \(V\), which makes \(V.type\) an inherited attribute. The recursive rule \(V \to V_1\ id\) sets \(V_1.type = V.type\), pushing this inherited value further down. So SDD1 mixes synthesized attributes (\(T.type\), \(D.type\)) with inherited attributes (\(V.type\), \(V_1.type\)); it is L-attributed overall but does not contain only inherited attributes. Statement (C) is false.

Step 3: Attribute classification in SDD2. Here \(D.type = T.type\) or \(D.type = D_1.type\), and \(T.type\) is set directly from the terminal. Every attribute value comes strictly from the children of the production - no value is ever pushed from a parent down into an already-expanded child. This means SDD2 uses only synthesized attributes, i.e. it is S-attributed. Statement (B) is true.

Step 4: Symbol table entries. In SDD1 the single declared type is fixed once from \(T\), threaded down as an inherited attribute through every \(V\)/\(V_1\), and \(put(id.entry, V.type)\) inserts each identifier with that same type. In SDD2 the same declared type is synthesized upward through the chain of \(D_1\) reductions, and \(put(id.entry, D_1.type)\) or \(put(id.entry, T.type)\) again inserts each identifier with that type. For a declaration such as \(int\ a\ b\ c\), both SDDs end up calling \(put\) once per identifier, mapping every identifier to the same declared type. So the entries placed in the symbol table are identical between the two definitions. Statement (D) is true.

Hence the correct statements are (A), (B), and (D).

\[\boxed{\text{Answer: (A), (B), (D)}}\]