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

A) False bcz it only checks Boolean and integer 

for ex : if we've any other arithmatic operation on Integer like multiplication or subtraction or division then it can't be valid .

B) True bcz 

this rule check integer expressions E → E1 + E2 {check if( E1.type = E2.type == int) set E.type = int; } and

this rule checks integer variable declaration E → ID {set E.type:= int}

C) False  bcz this rule  only  check boolean expressions E → !E1 {check if( E1.type == bool) set E.type = bool;}   and what if in the expression we'll have multiplication of booleans or addition of booleans means any expression is given then we these rule will be invalid.

Option C wrong because it says that this grammar is used for type check  synthetically correct Boolean variable  declaration and Boolean expression

But in given grammar we have only rule to check  Boolean expressions 

(E = !E1 it only check Boolean expression)

If this rule also given in grammar  E= ID( set E.type:= Boolean) then option C also correct 

D) False 

bcz  its simply declaration and expression rules so not any infinite looping here.

 

 

Comments

Thank You for the Video @Rohit139

---

hi, i am having trouble with option c. you say what if it was multiplication or addition of two booleans but what multiplication of integers is not given as a production either. can u help me understand please

---

Archana 1   The issue lies in the last production rule  $$E\to \text{ID}\{\text{set}E.\text{type}:=\text{int}\}$$

this rule unconditionally assigns the type int to every identifier (ID) it evaluates in an expression. It completely ignores the symbol table (the records created by the D productions) where the actual declared type of the identifier is stored.

For ex,  if your expression was !x  the parser would use the rule: E→!E1 ​{check that E1​.type ==bool;…}

Since forced $E1.\text{type}$ (which is x) to be int , the check int == bool will fail . The compiler will throw a type error on a perfectly valid boolean expression, which is why the SDT cannot correctly type-check boolean declarations and expressions.

When an addition happens E→ E1​+E2​  both E1​ and E2​ will evaluate to int the check E1​.type ==E2​.type == int will pass, and the resulting type will be correctly set to int

Answer 2

Answer (A) The actions can be used to correctly type-check any syntactically correct program

 

SHORT ANSWER:

A grammar is given with the SDT actions on it.

Now, the option A:

“ The actions can be used to correctly type-check any syntactically correct program “

• syntactically correct program: so we have to do SDT TYPE-CHECKING on any SYNTACTICALLY CORRECT PROGRAM

                     this means the PROGRAM (string) is legally generated by the grammar                             

(so syntactically correct programs ensured)

• now correctly type-check: the SDT defined can  ONLY TELL what the CORRECT SYNTAX is!

        Thus, the SDT that defines the semantics of the declarations and expressions IS USED TO type-check the declaration and expressions of integer and boolean type

this will ensure that correct type-checking of any syntactically correct program is happening!

 

---

 

---

Long Answer:

 

OFFICIAL KEY says option (B) The actions can be used to type-check syntactically correct integer variable declarations and integer expressions

So, as said above, we have already a SYNTACTICALLY CORRECT program (string generated by the grammar)

The KEY thing for me while answering this question would always be to see

• GRAMMAR   : syntactically correct programs
• SDT             : type-checking

both separately.

First Grammar will generate SYNTACTICALLY correct programs (as always if grammar is used to generate the strings, THOSE STRINGS WILL BELONG to the grammar and thus THOSE PROGRAMS WOULD BE SYNTACTICALLY CORRECT)

Second step, the program is passed to the SDT and it type-checks it for both

• declarations
• expressions

Now, the program generated by grammar  be like:

ID

 

So, after generating the string (program) :    ID

we perform SEMANTIC ACTIONS.

So, our example: string: ID

Now the program is having integer expressions or boolean expression can NOT BE DETERMINED IN syntax analyzer phase, and ONLY THE SDT ACTIONS will determine the nature of expression (integer or boolean)

Thus, never this SDT could fail to correctly type-check  boolean variable expressions: as there be none.

All the expressions are of INTEGER VARIABLE only.

And integer variables too are being correctly type-checked as per the specified SDT rules, as the actions seem to correctly propagate and check type-meaning of the variables.

 

 

Comments

@ankit3009

 

If rule E1+E2 won't be there then it would be checking for both bool and int data types … correctly.

---

Yes Sir, understood. Thank you :)

---

Why option A is not true , as it says it can type check ANY program. If we see this option from preposition logic pov so isn't it giving feeling of THERE EXIST SOME program to which this can give correct result?

 

Answer 3

Answer (B)

---

Understanding the Grammar & SDT Actions

The grammar consists of:

1. Declarations (D): It allows declaration of variables as either int or bool, and records the type information.
2. Expressions (E): Expressions support:
   • Addition (E1 + E2), which requires both operands to be int and sets the result as int.
   • Logical negation (!E1), which requires E1 to be bool and sets the result as bool.
   • Simple usage of identifiers (ID), which takes their previously declared type.

---

Analysis of the Given Options

(A) The actions can be used to correctly type-check any syntactically correct program.

• Incorrect because:
  • The grammar only supports integer and boolean types.
  • It does not handle mixed-type expressions (e.g., int + bool or bool + int are not accounted for).
  • Other common operations like multiplication (*), division (/), relational comparisons (==, >, etc.), and logical operations (&&, ||) are not covered.
  • No handling of function calls, conditionals, loops, or arrays.

Thus, this SDT cannot handle all syntactically correct programs, making (A) incorrect.

---

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

• Correct because:
  • Integer variable declarations (int ID) are explicitly supported.
  • The only supported arithmetic operation (E1 + E2) ensures both operands are of type int, and the result remains int.
  • Fetching an identifier (ID) sets E to int if the identifier was declared as such.

Since integer declarations and integer expressions are properly handled, (B) is correct.

---

(C) The actions can be used to type-check syntactically correct boolean variable declarations and boolean expressions.

• Incorrect because:
  • Boolean variables (bool ID) can be declared, but:
  • Boolean expressions are incomplete:
    • !E1 (logical NOT) is supported, but no support for other boolean operations like && (AND) or || (OR).
    • This means expressions like bool x = true; y = !x; will work, but y = x && z; is not supported.
  • There is no way to use boolean variables in expressions beyond !E1.

Thus, boolean expressions are not fully supported, making (C) incorrect.

---

(D) The actions will lead to an infinite loop.

• Incorrect because:
  • The grammar is well-defined with clear production rules.
  • There is no recursion that leads to an infinite loop.
  • Expressions and declarations are processed in a structured manner.

Since there is no infinite loop, (D) is incorrect.

Answer 4

The Correct answer is B. 

As the given grammar does type checking and also it syntactically checks integer expressions.

Comments

Sir,

the declaration:bool id_1 int id_1

P →D1D2

D1 – > bool id_1

D2 – > bool id_1

 

is a very fine string (program) that is syntactically correct as it could be generated by the grammar BUT on passing it to SDT and type-checking will record:

id_1.lexeme = boolean

then overwriting it by

id_1.lexeme = INTEGER

 

which seems a type-checking error in integer declarations and hence NOT ALL INTEGER VARIABLE DECLARATIONS are correctly type-checked by given SDT

 

So, could option B too can be wrong?

---

dear Bhartendu Kumar bool + bool is a boolean expression not an integer expression

---

Sherrinford03, yes you are correct. We can’t reduce Boolean expression, since there is no rule for the boolean identifier.

Answer 5

To answer this question,

Let's number productions given in the question from 1 to 6.

• Now, it can be inferred that productions 2 and 3 are being used for the entry into the symbol table.
• 4 is being used for type checking of integer expression.
• 5 is being used for type checking of Boolean expression.
• But from 6th production it can be concluded that only integer type is set.

So we can conclude that the action are being used to type check syntactically correct integer variable declarations and integer expessions.

Answer: B

 

 

Answer 6

P can produce any no of D followed by any no of E's

D is produccing any no of int or boolean

but looking at E it is only able to do the arithmetic operation on E not on the boolean

so the parser can syntactically can only correct integer and boolean declarations but only correct integer expressions not boolean