Question
Match the following compiler phases / tasks with their underlying algorithmic techniques:
List-I
P. Lexical analysis
Q. Parsing
R. Register allocation
S. Expression evaluation
List-II
- Graph coloring
- DFA minimization
- Post-order traversal
- Production tree
Official answer and solution
- Official answer
- C
- From
- Official GATE 2015 answer key
Solution
Match each compiler construction phase to its standard underlying algorithmic formalism.
Examine the pairings:
- P. Lexical analysis: Token patterns are specified by regular expressions and implemented using Deterministic Finite Automata (DFAs). Minimizing these state machines uses DFA minimization (2).
- Q. Parsing: Syntax analysis derives the hierarchical grammatical structure of the program based on Context-Free Grammars, constructing a Production tree (parse tree) (4).
- R. Register allocation: Chaitin's formulation maps variable live-range interference to an undirected graph, solving allocation via Graph coloring (1).
- S. Expression evaluation: An expression tree is evaluated by traversing children before computing the parent operator, corresponding to a Post-order traversal (3).
Matching: P-2, Q-4, R-1, S-3 (option C).
Final answer
C
Common trap
Associating Parsing with DFA minimization instead of context-free production trees.
The answer is the one in the official GATE answer key. The solution is this site's own explanation.
Source
- Paper
- GATE 2015 Computer Science and Information Technology (CS) Session 2
- Question
- 29 of 65, printed as CS Q.19
- Section
- Computer Science and Information Technology
Report an error in this question
GATE questions are the work of the organising institutes. This site is independent and is not affiliated with them.