Consider the following two sets:
Set X: P. Lexical Analyzer, Q. Syntax Analyzer, R. Intermediate Code Generator, S. Code Optimizer
Set Y: 1. Abstract Syntax Tree, 2. Token, 3. Parse Tree, 4. Constant Folding
Which one of the following options is the CORRECT match from Set X to Set Y?
A. P -> 4, Q -> 1; R -> 3; S -> 2
B. P -> 2, Q -> 3; R -> 1; S -> 4
C. P -> 2, Q -> 1; R -> 3; S -> 4
D. P -> 4, Q -> 2; R -> 1; S -> 3
GATE 2024 · Compiler Design · Compilation Phases · medium
Answer: B. P -> 2, Q -> 3, R -> 1, S -> 4
Match P. Lexical Analyzer: The lexical analyzer (scanner) reads the source program character by character and groups them into meaningful units called tokens (e.g., identifiers, keywords, operators, literals). Output: Token (2). P -> 2.
Match Q. Syntax Analyzer: The syntax analyzer (parser) takes the token stream and checks it against the grammar rules of the language, building a parse tree (also called concrete syntax tree) that shows the complete syntactic derivation. Output: Parse Tree (3). Q -> 3.
Match R. Intermediate Code Generator: The intermediate code generator works with the semantic information and the parse tree to produce an intermediate representation. The Abstract Syntax Tree (AST) is the key data structure at this stage — it strips away unnecessary parse-tree nodes and retains the logical structure for IR generation. Output: Abstract Syntax Tree (1). R -> 1.
Match S. Code Optimizer: The code optimizer applies program transformations to make the code faster or smaller. Constant folding is one of the most fundamental optimization techniques: evaluating constant expressions at compile time. For example, 'x = 2 + 3' becomes 'x = 5'. Technique: Constant Folding (4). S -> 4.
Final matching: P -> 2 (Token), Q -> 3 (Parse Tree), R -> 1 (Abstract Syntax Tree), S -> 4 (Constant Folding). This matches option B.