GATE CS 2026 Set 1 Q32 — Parsing (LL, LR)

An expression $E$ is a redundant (common) subexpression at a basic block if it is guaranteed to be previously computed along all paths leading to that block, and none of its operand variables have been modified since their last computation (i.e., the expression is available).

Analyzing the control flow graph:

• At Basic Block B4: The expression $g * k$ is computed in $B_1$ and its operands $g$ and $k$ are not modified along any path leading to $B_4$. Thus, $g * k$ is redundant. However, $b + i$ is not redundant because $b$ is modified in block $B_2$ along the path $B_1 \rightarrow B_2 \rightarrow B_4$, killing the expression.
• At Basic Block B5: The expression $c + m$ is not redundant because $c$ is modified in block $B_3$ along the path $B_1 \rightarrow B_3 \rightarrow B_5$, killing the expression. Thus, the set of redundant expressions at $B_5$ is empty, i.e., $\{\}$.

Therefore, the correct option is D.