GATE CS 1994 Q1.18 — Parsing (LL, LR)

To determine which feature cannot be captured by a context-free grammar (CFG), let us analyze each option:

• A. Syntax of if-then-else statements: This can be easily defined using a CFG. For example: $$S \rightarrow \text{if } E \text{ then } S \mid \text{if } E \text{ then } S \text{ else } S \mid \text{other}$$
• B. Syntax of recursive procedures: CFGs naturally support recursion (self-nested structures), making them perfectly suited to define recursive procedure structures.
• C. Whether a variable has been declared before its use: This is a semantic check rather than a purely syntactic one. Formally, verifying that a variable of any arbitrary name $w$ is declared before it is used is equivalent to recognizing the language: $$L = \{ w c w \mid w \in \Sigma^* \}$$ By the pumping lemma, $L$ is a well-known non-context-free language. Thus, this feature cannot be captured by a CFG and is instead handled during the semantic analysis phase using a symbol table.
• D. Variable names of arbitrary length: This can be defined even by a regular grammar (which is a subset of CFGs). For example: $$\text{Identifier} \rightarrow \text{letter } \text{Rest}$$ $$\text{Rest} \rightarrow \text{letter } \text{Rest} \mid \text{digit } \text{Rest} \mid \epsilon$$

Therefore, the feature that cannot be captured by context-free grammars is C.