GATE CS 2021 Set 1 Q.36 (CS Q.26): Syntax-Directed Translation

Consider the following grammar (that admits a series of declarations, followed by expressions) and the associated syntax directed translation (SDT) actions, given as pseudo-code:

P \rightarrow D^* E

D \rightarrow \text{int } ID \quad \{\text{record that } ID.\text{lexeme is of type int}\}

D \rightarrow \text{bool } ID \quad \{\text{record that } ID.\text{lexeme is of type bool}\}

E \rightarrow E_1 + E_2 \quad \{\text{check that } E_1.\text{type} = E_2.\text{type} = \text{int}; \text{ set } E.\text{type} := \text{int}\}

E \rightarrow !E_1 \quad \{\text{check that } E_1.\text{type} = \text{bool}; \text{ set } E.\text{type} := \text{bool}\}

E \rightarrow ID \quad \{\text{set } E.\text{type} := \text{int}\}

With respect to the above grammar, which one of the following choices is correct?

The actions can be used to correctly type-check any syntactically correct program.

The actions can be used to type-check syntactically correct integer variable declarations and integer expressions.

The actions can be used to type-check syntactically correct boolean variable declarations and boolean expressions.

The actions will lead to an infinite loop.

Official answer and solution

Official answer: B
From: Official GATE 2021 answer key

Solution

Trace how type attributes are assigned and verified for integer versus boolean identifiers.

Inspect the semantic rule associated with the identifier production $E \rightarrow ID$ :

\{ \text{set } E.\text{type} := \text{int} \}

Notice that this action unconditionally assigns $E.\text{type} = \text{int}$ to any variable reference, without looking up the declared type of $ID$ in the symbol table.

If a boolean variable $b$ is declared (bool b;) and subsequently used in an expression such as !b, the rule $E \rightarrow ID$ sets $E.\text{type} := \text{int}$ . Then the rule $E \rightarrow !E_1$ checks whether $E_1.\text{type} == \text{bool}$ , which fails because $E_1.\text{type}$ was forced to int! Thus boolean expressions cannot be correctly type-checked.

However, for integer variable declarations (int a, c;) and expressions (a + c), $E \rightarrow ID$ sets $E.\text{type} := \text{int}$ , and $E \rightarrow E_1 + E_2$ correctly checks $E_1.\text{type} = E_2.\text{type} = \text{int}$ . Thus, the actions can correctly type-check syntactically correct integer declarations and integer expressions (option B).

Final answer

The answer is the one in the official GATE answer key. The solution is this site's own explanation.

Source

Paper: GATE 2021 Computer Science and Information Technology (CS, Set-1)
Question: 36 of 65, printed as CS Q.26
Section: Computer Science and Information Technology

Report an error in this question

GATE questions are the work of the organising institutes. This site is independent and is not affiliated with them.

Question

Solution

Source