GATE CS 2009 Q17 — Lexical Analysis

We can match each concept from Group 1 to its corresponding compiler phase or technique in Group 2 as follows:

• P. Regular Expression $\rightarrow$ 3. Lexical analysis: Regular expressions are used to define the patterns of tokens (such as identifiers, keywords, and operators). The lexical analyzer uses these patterns to scan and tokenize the source code.
• Q. Pushdown automata $\rightarrow$ 1. Syntax analysis: Programming language syntax is typically defined using Context-Free Grammars (CFGs). Since pushdown automata (PDA) are the theoretical models that recognize context-free languages, they form the basis of parsers used in syntax analysis.
• R. Dataflow analysis $\rightarrow$ 4. Code optimization: Dataflow analysis is a technique used to gather information about the flow of data values along the execution paths of a program. This information is crucial for performing optimizations such as constant folding, dead-code elimination, and common subexpression elimination.
• S. Register allocation $\rightarrow$ 2. Code generation: During the code generation phase, the compiler translates intermediate code into target machine code. Register allocation is the process of assigning a limited number of CPU registers to an arbitrary number of program variables to minimize memory accesses.

Thus, the correct mapping is P-3, Q-1, R-4, S-2, which corresponds to Option B.