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 ?
P – 4; Q – 1; R – 3; S – 2
P – 2; Q – 3; R – 1; S – 4
P – 2; Q – 1; R – 3; S – 4
P – 4; Q – 3; R – 2; S – 1
ANSWER
The correct match is P – 2; Q – 3; R – 1; S – 4, which is option (B).
Official answer: BSource: Official answer key, GATE 2024 CS2 (IISc Bengaluru)
The lexical analyzer reads the character stream and groups it into lexemes, each reported as a token. So P matches 2 (Token).
The syntax analyzer (parser) checks the token stream against the grammar and builds the parse tree. So Q matches 3 (Parse Tree).
The intermediate code generator works from the abstract syntax tree that the front end passes on, a compact form of the parse tree. So R matches 1 (Abstract Syntax Tree).
The code optimizer applies transformations such as constant folding, which evaluates constant expressions at compile time. So S matches 4 (Constant Folding).
The matching is P – 2; Q – 3; R – 1; S – 4. Option (A) pairs P with 4 and option (C) pairs Q with 1. Option (D) pairs P with 4. Only option (B) has all four pairs right.
KEY IDEA
Each compiler phase has its own characteristic output or operation. The lexer produces tokens, the parser produces a parse tree, the intermediate code generator takes the syntax tree (AST), and the optimizer performs transformations such as constant folding.
WATCH OUT FOR
Matching the parse tree to the intermediate code generator, or the abstract syntax tree to the parser, because the two trees look alike. The parser's own output is the parse tree, and the AST is the compact tree the later phases use.
From the GATE 2024 CS2 paper. Every question of this paper · Download the full paper · All 8 Lexical analysis questions, with notes
