Consider the following grammar (that admits a series of declarations,… — GATE CS 2021 Set 1 Q26

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

$\begin{array}{lll} P & \rightarrow & D^* E^* \\ D & \rightarrow & \textsf{int ID} \{ \text{record that } \textsf{ID.} \text{lexeme is of type} \textsf{ int\}} \\ D & \rightarrow & \textsf{bool ID} \{ \text{record that } \textsf{ID.} \text{lexeme is of type} \textsf{ bool\}} \\ E& \rightarrow & E_1 +E_2 \{ \text{check that } E_1. \text{type}=E_2. \text{type} = \textsf{int}; \text{set } E.\text{type }:= \textsf{int} \} \\ E & \rightarrow & !E_1 \{ \text{check that } E_1. \text{type} = \textsf{bool}; \text{ set } E.\text{type} := \textsf{bool} \} \\ E & \rightarrow & \textsf{ID} \{ \text{set } E. \text{type } := \textsf{int} \} \end{array}$

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

View worked solution

Answer: B

To determine the correctness of the given Syntax-Directed Translation (SDT) actions, let us analyze the semantic rules associated with the production rules.

1. Analysis of the Identifier Rule

Consider the production rule for reducing an identifier to an expression:

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

This rule unconditionally sets the type of the expression $E$ to $\textsf{int}$ , completely ignoring the actual type recorded for the identifier in the symbol table during the declaration phase ( $D \rightarrow \textsf{int ID}$ or $D \rightarrow \textsf{bool ID}$ ).

2. Evaluating Boolean Expressions

Suppose we have a syntactically correct program with a boolean declaration and a boolean expression:

bool x
!x

During declaration, the rule $D \rightarrow \textsf{bool ID}$ correctly records that x is of type $\textsf{bool}$ .
During expression evaluation, the identifier x is reduced to $E$ using $E \rightarrow \textsf{ID}$ . This action unconditionally sets $E.\text{type} := \textsf{int}$ .
Next, the expression !x is evaluated using $E \rightarrow !E_1$ . The semantic action checks if $E_1.\text{type} = \textsf{bool}$ . Since $E_1.\text{type}$ was set to $\textsf{int}$ , this check fails.

Thus, the SDT cannot correctly type-check valid boolean expressions.

3. Evaluating Integer Expressions

Suppose we have an integer declaration and an integer expression:

int y
y + y

The identifier y is reduced to $E$ using $E \rightarrow \textsf{ID}$ , setting $E.\text{type} := \textsf{int}$ .
The expression y + y is evaluated using $E \rightarrow E_1 + E_2$ . The semantic action checks if $E_1.\text{type} = E_2.\text{type} = \textsf{int}$ , which is satisfied. It then sets $E.\text{type} := \textsf{int}$ .

Since the default fallback type assigned by $E \rightarrow \textsf{ID}$ is $\textsf{int}$ , all integer declarations and expressions are type-checked correctly.

Conclusion

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

Therefore, the correct option is B.

Free practice · Your answers on this page are not saved.

GATE CS 2021 Set 1 Q26 — Syntax-directed Translation

1. Analysis of the Identifier Rule

2. Evaluating Boolean Expressions

3. Evaluating Integer Expressions

Conclusion

Related questions