GateAI
Syntax-Directed Translation

GATE CSE 2021 Set 1 · Q26

MCQ2 marksMedium

Time

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

Select one answerSingle correct

Pick an option to check

Solution

Step-by-step verified solution

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

Syntax-Directed Translation

Let's analyze the semantic rules in the given Syntax Directed Translation (SDT):

  1. Declarations (DD):

    • Variable types (int or bool) are recorded in the symbol table when declared.

  2. Expressions (EE):

    • In the base production E→IDE \rightarrow \text{ID}, the semantic action is: set E.type := int.

    • This hardcodes the type of any identifier appearing in an expression to int, completely bypassing the symbol table lookup.

  3. Evaluation for Integer Expressions:

    • For any integer variable ID\text{ID}, E→IDE \rightarrow \text{ID} sets E.type=intE.\text{type} = \text{int}.

    • For addition E→E1+E2E \rightarrow E_1 + E_2, it verifies that both operands are int and sets the result type to int. This works correctly for integer variables and expressions.

  4. Evaluation for Boolean Expressions:

    • For any boolean variable ID\text{ID}, E→IDE \rightarrow \text{ID} sets E.type=intE.\text{type} = \text{int} instead of bool.

    • When evaluating E→!E1E \rightarrow !E_1, the condition check that E_1.type = bool will fail because E1.typeE_1.\text{type} is int. Therefore, boolean expressions involving variables will fail type checking.

Hence, the actions can only be used to type-check syntactically correct integer variable declarations and integer expressions.

Therefore, (B) is the correct choice.

Try the question first, then check your work.

Think the official key or this write-up is wrong?

Report error or challenge

Examiner trap

The misconception this question tests

This Syntax-Directed Translation previous year question is Q26 of the GATE CSE 2021 Set 1 paper. Find more GATE CSE PYQs on Syntax-Directed Translation in Compiler Design, or browse all GATE CSE PYQs.

Free diagnostic

Where do you stand for GATE?

Take the 20-minute diagnostic: the 3 topics that cost you the most marks, and a rank range. Or sit 5 related Syntax-Directed Translation PYQs now with no account.

One GATE CSE PYQ every morning

An official question by email at 7 AM IST, with a link to its verified solution. Unsubscribe in one click.

Syntax-Directed Translation in GATE CSE

Syntax-Directed Translation has 9 GATE CSE PYQs across 9 papers from 2016 to 2026. 4 of them are 2-mark MCQs like this one, and it is the only one in GATE CSE 2021 Set 1.

How GATE tests Syntax-Directed Translation

More from GATE CSE 2021 Set 1

Share this solution

A plain-text card for WhatsApp or Telegram study groups.

GateAI solution cardGATE CSE 2021 Set 1 · Q26 · MCQ

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

Topic-wise GATE CS PYQs with verified steps

Independent practice explanation verified by the GateAI team. GATE is conducted by the IITs; question text follows the official paper.