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?
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?
Show Hint
- The actions can be used to correctly type-check any syntactically correct program.
- The actions can be used to type-check syntactically correct integer variable declarations and integer expressions.
- The actions can be used to type-check syntactically correct boolean variable declarations and boolean expressions.
- The actions will lead to an infinite loop.
The Correct Option is B
Solution and Explanation
Step 1: Examine type assignment for identifiers.
In the production \(E \rightarrow ID\), the action always sets \(E.\text{type} := \text{int}\), regardless of whether the identifier was declared as \texttt{int} or \texttt{bool}. This ignores boolean declarations when identifiers are used in expressions.
Step 2: Analyze integer expressions.
The production \(E \rightarrow E_1 + E_2\) correctly checks that both operands are of type \texttt{int} and assigns type \texttt{int} to the result. Hence, integer expressions are type-checked correctly.
Step 3: Analyze boolean expressions.
Although boolean declarations are recorded, boolean identifiers used in expressions are incorrectly typed as \texttt{int}. Therefore, expressions involving boolean variables cannot be reliably type-checked.
Step 4: Eliminate incorrect options.
Option (A) is incorrect because boolean expressions are not correctly handled.
Option (C) is incorrect for the same reason.
Option (D) is incorrect since the grammar does not contain left-recursive or cyclic productions that cause infinite looping in SDT actions.
Step 5: Conclusion.
The given actions correctly type-check only syntactically correct integer variable declarations and integer expressions.
Final Answer: (B)
Top Questions on Syntax-directed translation
Consider the following grammar along with translation rules. \[ S \rightarrow S_1 \# T \,\,\,\,\,\,\{S_{\centerdot\text{val}} = S_{1\centerdot\text{val}}* T_{\centerdot\text{val}}\} \] \[ S \rightarrow T \,\,\,\,\,\,\{S_{\centerdot\text{val}} = T_{\centerdot\text{val}}\} \] \[ T \rightarrow T_1 \% R \,\,\,\,\,\, \{T_{\centerdot\text{val}} = T_{1\centerdot\text{val}} \div R_{\centerdot\text{val}}\} \] \[ T \rightarrow R \,\,\,\,\,\,\{T_{\centerdot\text{val}} = R_{\centerdot\text{val}}\} \] \[ R \rightarrow \text{id} \,\,\,\,\,\,\{R_{\centerdot\text{val}} = \text{id}_{\centerdot\text{val}}\} \] Here \(\#\) and % are operators and id is a token that represents an integer and \( \text{id}_{\text{val}} \) represents the corresponding integer value. The set of non-terminals is {S, T, R, P}, and a subscripted non-terminal indicates an instance of the non-terminal.
Using this translation scheme, the computed value of} \( S_{\text{val}} \) for root of the parse tree for the expression \(20\#10%5\#8%2\#2 \) is- GATE CS - 2022
- Compiler Design
- Syntax-directed translation
Questions Asked in GATE CS exam
In a 4-bit ripple counter, if the period of the waveform at the last flip-flop is 64 microseconds, then the frequency of the ripple counter in kHz is ______________. {(Answer in integer)}
- GATE CS - 2025
- Flip-Flop
Consider the following C code segment:
int x = 126, y = 105; do { if (x > y) x = x - y; else y = y - x; } while (x != y); printf("%d", x);The output of the given C code segment is ____________. (Answer in integer)
- GATE CS - 2025
- Programming in C
The following two signed 2’s complement numbers (multiplicand \( M \) and multiplier \( Q \)) are being multiplied using Booth’s algorithm:
Multiplicand (\( M \)) Multiplier (\( Q \)) 1100 1101 1110 1101 1010 0100 1010 1010 The total number of addition and subtraction operations to be performed is __________. (Answer in integer)
- GATE CS - 2025
- Complementation
The maximum value of \(x\) such that the edge between the nodes B and C is included in every minimum spanning tree of the given graph is __________ (answer in integer).
- GATE CS - 2025
- Programming and Data Structures
Consider the following C program
The value printed by the given C program is __________ (Answer in integer).- GATE CS - 2025
- Programming in C