Match each compiler task in Group I with the most closely associated technique…

Concept

A compiler task is matched to the mathematical model, data structure, or processing order that directly represents its work.

Finite automata model token recognition, grammar derivations model parsing, interference constraints model register assignment, and bottom-up traversal models expression evaluation.

Application

1. Lexical analysis recognizes tokens described by regular expressions. A DFA implements that recognizer, and DFA minimization can reduce its states without changing the recognized language; hence P → 2.

2. Parsing applies grammar productions to obtain the syntactic structure of the input. That structure is represented by a production tree or parse tree; hence Q → 4.

3. Register allocation creates an interference graph in which simultaneously live values are adjacent. Assigning registers is modeled as graph coloring; hence R → 1.

4. Expression evaluation must evaluate each operand subtree before applying its parent operator. Post-order traversal visits children before the parent; hence S → 3.

Cross-check and contrast

The four matches use four different roles: automata optimization for tokens, a grammar-derived tree for syntax, graph coloring for constrained resources, and post-order traversal for bottom-up computation.

• P-2, Q-3, R-1, S-4 exchanges the roles of the production tree and post-order traversal: parsing constructs syntax, whereas evaluation processes an existing expression tree.

• P-2, Q-1, R-4, S-3 assigns the interference-graph model to parsing and the grammar-derived structure to register allocation.

• P-2, Q-3, R-4, S-1 assigns a traversal to parsing, a production tree to register allocation, and graph coloring to expression evaluation.

Therefore, the matching is P-2, Q-4, R-1, S-3.