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
- With respect to a TCP connection between a client and a server, which of the following is true?
- GATE CS - 2026
- Computer Networks
- Let $P, Q, R, S$ be relational schemas. Let ``$\rightarrow$'' indicate a functional dependency (FD) in this context. Which of the following best describes the meaning of a functional dependency?
- GATE CS - 2026
- Database Management Systems
- Let a Non-deterministic Finite Automaton (NFA) have 6 states over a finite alphabet. Which of the following cannot be the number of states in a minimal Deterministic Finite Automaton (DFA) that is equivalent to this NFA?
- GATE CS - 2026
- Theory of Computations
- A certain processor uses a fully associative cache of size 16 kB. The cache block size is 16 bytes. Assume that the main memory is byte addressable and uses a 32-bit address. How many bits are required for the Tag and the Index fields respectively in the addresses generated by the processor?
- GATE CS - 2026
- Computer Organization and Architecture
- Consider $Z = X - Y$, where $X$, $Y$ and $Z$ are all in sign-magnitude form. $X$ and $Y$ are each represented in $n$ bits. To avoid overflow, the representation of $Z$ would require a minimum of:
- GATE CS - 2026
- Computer Organization and Architecture