GATE CS 2009 Q42 — Parsing (LL, LR)

Let us analyze each statement individually to determine its validity:

• Statement I: True. General context-free grammar parsing algorithms (like CYK or Earley's) have a worst-case complexity of $O(n^3)$. However, programming languages are designed to be deterministic context-free languages (DCFLs), which can be parsed in linear time, i.e., $\Theta(n)$, using LL or LR parsing algorithms. Since $\Theta(n) < \Theta(n^3)$, this statement is true.
• Statement II: False. Recursion requires multiple activation records of the same function to coexist in memory simultaneously (each with its own local variables and return address). Static storage allocation assigns a single fixed memory location for each variable, which cannot support multiple active instances of a recursive function. Thus, recursion requires dynamic storage allocation (specifically, stack-based allocation).
• Statement III: False. While L-attributed definitions are naturally suited for top-down parsing, many L-attributed definitions can indeed be evaluated during bottom-up parsing. This is achieved either because the definition is S-attributed (which is a subset of L-attributed) or by transforming the grammar using marker non-terminals to compute inherited attributes on the LR parser stack.
• Statement IV: True. Code-improving transformations (optimizations) can be performed at various stages of compilation. For example, high-level optimizations like loop unrolling or function inlining can be done at the source/AST level, while common subexpression elimination, constant folding, and dead code elimination are routinely performed on intermediate code (IR).

Since statements I and IV are true, the correct option is B.