Match the following: P. Lexical analysis Q. Parsing R. Register allocation S.…
2015
Match the following:
P. Lexical analysis
Q. Parsing
R. Register allocation
S. Expression evaluation
1. Graph coloring
2. DFA minimization
3. Post-order traversal
4. Production tree
- A.
P-2, Q-3, R-1, S-4
- B.
P-2, Q-1, R-4, S-3
- C.
P-2, Q-4, R-1, S-3
- D.
P-2, Q-3, R-4, S-1
Attempted by 171 students.
Show answer & explanation
Correct answer: C
Key insight: match each compiler task to the standard technique used to implement or solve it.
Lexical analysis → DFA minimization (P → 2): lexical analyzers convert regular expressions to finite automata and often minimize DFAs to make token recognition efficient.
Parsing → Production tree (Q → 4): parsers build a parse tree or abstract syntax tree from grammar productions to represent program structure.
Register allocation → Graph coloring (R → 1): register assignment is modeled by coloring an interference graph so that simultaneously live variables do not share a register.
Expression evaluation → Post-order traversal (S → 3): evaluating an expression tree uses post-order traversal to evaluate operands before applying operators.
Therefore the correct matching is: P-2, Q-4, R-1, S-3.
A video solution is available for this question — log in and enroll to watch it.