Question

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 → E₁ + E₂ {check that E₁.type = E₂.type = int; set E.type := int}
E → !E₁ {check that E₁.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?

• A. The actions can be used to correctly type-check any syntactically correct program.
• B. The actions can be used to type-check syntactically correct integer variable declarations and integer expressions.
• C. The actions can be used to type-check syntactically correct boolean variable declarations and boolean expressions.
• D. The actions will lead to an infinite loop.

Hint:

Always ensure that identifier type lookup in expressions refers to the symbol table rather than assigning a fixed type.

Answer 1

The Correct Option is B

Step 1: Check type assignment for identifiers.
In the production E → ID, the semantic action always assigns:

E.type := int

This assignment is done irrespective of whether the identifier was declared as int or bool. As a result, boolean identifiers are incorrectly treated as integers when they appear in expressions.

---

Step 2: Verification of integer expression handling.
For the production E → E₁ + E₂, the semantic action correctly checks that both operands have type int and assigns the result type int.

Hence, integer expressions are type-checked properly.

---

Step 3: Limitation in handling boolean expressions.
Although boolean variable declarations are recorded, their use in expressions is not handled correctly.

Since E → ID always assigns type int, expressions involving boolean variables cannot be reliably type-checked.

---

Step 4: Eliminate incorrect options.

Option (A): Incorrect, because boolean expressions are not type-checked correctly.

Option (C): Incorrect for the same reason.

Option (D): Incorrect, since there are no left-recursive or cyclic productions that would cause infinite execution of semantic actions.

---

Final Conclusion:
The given syntax-directed translation scheme correctly type-checks only integer variable declarations and integer expressions.

Final Answer: (B)