GATE CSE 2015 Set 2 | Question: 19

Question

Match the following:$$\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}$$

• A. $\text{P-2, Q-3, R-1, S-4}$
• B. $\text{P-2, Q-1, R-4, S-3}$
• C. $\text{P-2, Q-4, R-1, S-3}$
• D. $\text{P-2, Q-3, R-4, S-1}$

Answer 1

1. Regular expression uses FA & Regular Sets.
2. Expression can be evaluated with postfix Traversals.
3. Register allocation can be modeled by graph coloring.
4. The parser constructs a production tree.

So, answer is C.

Comments

For Minimum no of registers required problem we can estimate it by graph coloring method

---

Register allocation by graph coloring - Citizendium

Answer 2

Answer: C

Comments

Answer is C.

Answer 3

Answer Is C

Simple way to eliminating We Know that

Expression evaluation Is stack Based So we Analyses Post Order so we Left With Two Options C and B

For Production Tree We Get  Parsing

So Answer Is C

Comments

In that case you can directly eliminate all by seeing that for Q-4 , there is only 1 option C :