The GATE Grind

GATE 2021 CS – Question 36

Compiler Design · Syntax-Directed Translation · 2 marks · Multiple choice

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$ int ID {record that ID.lexeme is of type int}
$D \rightarrow$ bool ID {record that ID.lexeme is of type bool}
$E \rightarrow E_1 + E_2$ {check that $E_1$.type = $E_2$.type = int; set $E$.type := int}
$E \rightarrow !E_1$ {check that $E_1$.type = bool; set $E$.type := bool}
$E \rightarrow$ ID {set $E$.type := int}
With respect to the above grammar, which one of the following choices is correct?

  1. The actions can be used to correctly type-check any syntactically correct program.
  2. The actions can be used to type-check syntactically correct integer variable declarations and integer expressions.
  3. The actions can be used to type-check syntactically correct boolean variable declarations and boolean expressions.
  4. The actions will lead to an infinite loop.

Practise this question in The GATE Grind →

Show answer and explanation

Correct answer: (B) The actions can be used to type-check syntactically correct integer variable declarations and integer expressions.

Explanation

The rule E -> ID always sets type int, ignoring the recorded declaration, so boolean variables cannot be type-checked. Only integer declarations and expressions are handled correctly.