GATE CSE 2021 | Set 1 | Question: 26

Question

​​​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?

• 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

Comments

This grammar isnt handeling all integer expression like multiplication division then how come ans is b

---

okay yeahh same question !!?

---

The last line E -> ID  {set E.type := int } this is overwriting the Varible's type as the Int even if it's a boolean .

Answer 1

The answer should be option “B” as its checking if the string produced will  be of int type only and not BOOLEAN. Hence option “B” is correct.

Answer 2

Ans is B, because E->E1+E2 (for Integer Expression )checks that E1 and E2 should be int,

and E->E1(Integer Declaration) checks it should not be bool value so they both saying that it won't be anything other than int .

Answer 3

https://youtu.be/5D1tCJlyGoI?si=0BubVlJY6J_hvxcy&t=138

Answer 4

Option A : The actions can be used to correctly type-check any syntactically correct program is false bcoz it cannot work with programs which are other than int or bool

Option B : The actions can be used to type-check syntactically correct integer variable declarations and integer expressions is True as it can work well with both integer variable and integer expression

                              E -> E1+E2     it is also evaluating the expression

Option C : The actions can be used to type-check syntactically correct boolean variable declarations and boolean expressions This is false as it can work for bool variable but cannot bool expression.

Option D : The actions will lead to an infinite loop This is also false as it has simply declaration and expression rules and no condition for infinite looping.

Answer 5

The Grammar:

• Declarations: int ID or bool ID (records type in symbol table)
• Expressions: E + E (needs int), !E (needs bool), ID (returns type)

The Flaw:

E → ID {set E.type := int} ← Always sets int, ignores symbol table!

What Breaks:

bool b; // declares b as bool !b // should work, right?

But:

1. E → ID sets b's type to int (ignores that b is bool)
2. E → !E₁ checks if E₁ is bool... but it's int!
3. Type check fails ❌

What Works:

int a; a + a

Since E → ID hardcodes int, integer programs accidentally work correctly.

Answer: B - Only integer declarations and integer expressions type-check correctly.

Answer 6

I didn't find any answer satisfactory.
We are given a grammar and we only should care about programs that can be generated by the given grammar.
There is only int type addition and negation of bool operations in the grammar. so we dont have to worry about any other type of operations like (float or division etc.)
Option D can be eliminated easily.
The semantic rule E → ID { set E.type := int } ignores the symbol table and forces all identifiers to be of type int in expressions.

So a program like
bool B
!B 
wont be correct. Because in lexical phase B is assigned a bool and stored in symbol table. but while type checking B is recorded to be Int because of the above line of grammar. And hence we cant type check this bool program even though its syntactically correct.
Therefore option C is wrong. And thereby option A is wrong.
while option B is correct. as we can type check any syntactically correct int programs.