Skip to content
GATETECH
Official PYQ · 2015Set 2 · Q19Lexical AnalysisMCQ1 mark

GATE CS 2015 Set 2 Q19 — Lexical Analysis

Explain with AI

Match the following:P.Lexical analysis1.Graph coloringQ.Parsing2.DFA minimizationR.Register allocation3.Post-order traversalS.Expression evaluation4.Production tree\begin{array}{|ll|ll|}\hline \text{P.} & \text{Lexical analysis} & \text{1.} & \text{Graph coloring} \\ \hline \text{Q.} & \text{Parsing} & \text{2.}& \text{DFA minimization} \\ \hline \text{R.}& \text{Register allocation} & \text{3.} & \text{Post-order traversal} \\ \hline \text{S.} & \text{Expression evaluation} &\text{4.} & \text{Production tree} \\ \hline \end{array}

Choose one option
View worked solution

Answer: C

To find the correct match, let us analyze each phase of the compiler and its associated concept:

  • P. Lexical analysis → 2. DFA minimization
    Lexical analyzers identify tokens using regular expressions, which are implemented via Finite Automata. Minimizing the resulting Deterministic Finite Automata (DFA) ensures optimal state transitions and memory efficiency.
  • Q. Parsing → 4. Production tree
    Parsing (syntax analysis) verifies the structure of the token stream against the grammar rules of the language, producing a parse tree or production tree.
  • R. Register allocation → 1. Graph coloring
    In code generation, register allocation is mapped to the NP-complete K-graph coloring problem, where variables that are active simultaneously (interfering) cannot be assigned to the same register (color).
  • S. Expression evaluation → 3. Post-order traversal
    An expression represented as a syntax tree is evaluated by first computing the values of its sub-expressions (children) before applying the operator (parent). This bottom-up evaluation corresponds to a post-order traversal of the tree.

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

Free practice · Your answers on this page are not saved.

Published
Report a correction
Keep exploringMore Lexical Analysis questions