The GATE Grind

GATE 2018 CS – Question 47

Compiler Design · Lexical Analysis · 2 marks · Multiple choice

A lexical analyzer uses the following patterns to recognize three tokens $T_1$, $T_2$, and $T_3$ over the alphabet $\{a,b,c\}$.

$T_1$: $a?(b|c)^*a$

$T_2$: $b?(a|c)^*b$

$T_3$: $c?(b|a)^*c$

Note that '$x$?' means 0 or 1 occurrence of the symbol $x$. Note also that the analyzer outputs the token that matches the longest possible prefix.

If the string $bbaacabc$ is processed by the analyzer, which one of the following is the sequence of tokens it outputs?

  1. $T_1T_2T_3$
  2. $T_1T_1T_3$
  3. $T_2T_1T_3$
  4. $T_3T_3$

Practise this question in The GATE Grind →

Show answer and explanation

Correct answer: (D) $T_3T_3$

Explanation

For the string $bbaacabc$, the longest prefix matched by $T_3$ is $bbaac$ ($c?$ empty, $(b|a)^*=bbaa$, then $c$), which is longer than what $T_1$ or $T_2$ can match from the start. Processing the rest, $abc$ matches $T_3$ via $(b|a)^*c$. So the output is $T_3T_3$ (the official key).