GATE CS 2016 Set 2 Q.29 (CS Q.19): Lexical Analysis

Match the following:

(P) Lexical analysis
(Q) Top down parsing
(R) Semantic analysis
(S) Runtime environments

(i) Leftmost derivation
(ii) Type checking
(iii) Regular expressions
(iv) Activation records

P $\leftrightarrow$ i, Q $\leftrightarrow$ ii, R $\leftrightarrow$ iv, S $\leftrightarrow$ iii

P $\leftrightarrow$ iii, Q $\leftrightarrow$ i, R $\leftrightarrow$ ii, S $\leftrightarrow$ iv

P $\leftrightarrow$ ii, Q $\leftrightarrow$ iii, R $\leftrightarrow$ i, S $\leftrightarrow$ iv

P $\leftrightarrow$ iv, Q $\leftrightarrow$ i, R $\leftrightarrow$ ii, S $\leftrightarrow$ iii

Official answer and solution

Solution

Match each compiler construction phase or runtime concept to its corresponding primary mechanism or artifact.

Examine the pairings between compiler phases and concepts:

(P) Lexical analysis: Uses regular expressions and finite automata to define patterns and produce a stream of tokens. Matches (iii) Regular expressions.

(Q) Top down parsing: Constructs a parse tree starting from the root symbol, which corresponds to building a leftmost derivation of the sentence. Matches (i) Leftmost derivation.

(R) Semantic analysis: Checks whether source program constructs satisfy language definition rules beyond context-free syntax, primarily through static type checking. Matches (ii) Type checking.

(S) Runtime environments: Manages memory allocation during execution, creating and destroying stack frames known as activation records for function calls. Matches (iv) Activation records.

Combining these:
P $\leftrightarrow$ iii, Q $\leftrightarrow$ i, R $\leftrightarrow$ ii, S $\leftrightarrow$ iv.

This matches option (B).

Final answer

Common trap

Confusing top-down parsing (leftmost derivation) with bottom-up parsing (rightmost derivation in reverse).

The answer is the one in the official GATE answer key. The solution is this site's own explanation.

GATE questions are the work of the organising institutes. This site is independent and is not affiliated with them.