GATE 2018 CS Q.37: solution and answer

GATE 2018 · CSQ.37 · 2 marks · MCQ

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?

(A)
$T_{1} T_{2} T_{3}$
(B)
$T_{1} T_{1} T_{3}$
(C)
$T_{2} T_{1} T_{3}$
(D)
$T_{3} T_{3}$

See the question in the paper

Tap to open full size

Answer and solution

ANSWER

The analyzer outputs $T_{3} T_{3}$ , option (D).

Official answer: DSource: Official answer key, GATE 2018 CS (IIT Guwahati)

The analyzer uses maximal munch: at each point it takes the longest prefix of the remaining input that any one of the three patterns matches. Number the input bbaacabc as positions 1 to 8: b b a a c a b c.
$T_{1} = a ? (b ∣ c)^{*} a$ . Every match ends in a. The input starts with b, so the optional leading a is empty and the part before the final a must lie in $(b ∣ c)^{*}$ . The first a is at position 3, so bba matches (length 3). A longer match would have to end at another a. The next a is at position 4 and would need bba inside $(b ∣ c)^{*}$ , which is impossible. The longest match for $T_{1}$ is bba (length 3).
$T_{2} = b ? (a ∣ c)^{*} b$ . Every match ends in b, and the b symbols are at positions 1, 2 and 7. The prefix b (length 1) and the prefix bb (length 2, with $b ? = b$ , $(a ∣ c)^{*} = ε$ , then b) both match. A match ending at position 7 would need baacca-type text in $(a ∣ c)^{*}$ after at most one leading b, but the prefix bbaacab has a second b at position 2 inside that part, so it fails. The longest match for $T_{2}$ is bb (length 2).
$T_{3} = c ? (b ∣ a)^{*} c$ . Every match ends in c, and the c symbols are at positions 5 and 8. For the prefix bbaac: $c ? = ε$ , $(b ∣ a)^{*} = bbaa$ , then c, so it matches (length 5). For the prefix bbaacabc: the part before the final c is bbaacab, which contains a c at position 5. That c cannot be absorbed by $(b ∣ a)^{*}$ , and the optional leading c is not at the start, so it fails. The longest match for $T_{3}$ is bbaac (length 5).
The longest of the three matches is bbaac (5, against 3 and 2), so the first token is $T_{3}$ . The remaining input is abc.
On abc: $T_{1}$ matches only a (length 1), because ab and abc do not end in a. $T_{2}$ matches ab (length 2): $(a ∣ c)^{*} = a$ , then b. $T_{3}$ matches abc (length 3): $(b ∣ a)^{*} = ab$ , then c.
$T_{3}$ gives the longest match and consumes the whole remaining input. The output is $T_{3} T_{3}$ , which is option (D).

KEY IDEA

A lexer takes the longest prefix matched by any pattern at each step. For each pattern, find the furthest position where the prefix can end in the pattern's required last symbol and the earlier part fits the middle part of the pattern.

WATCH OUT FOR

Stopping at the first place a pattern can close (for example bba for $T_{1}$ ) instead of checking the longest prefix of every pattern. Another slip is letting the middle part $(b ∣ a)^{*}$ or $(b ∣ c)^{*}$ swallow a symbol it does not allow, such as a c inside $(b ∣ a)^{*}$ .

From the GATE 2018 CS paper. Every question of this paper · Download the full paper · All 8 Lexical analysis questions, with notes

GATE 2018 CS Q.37: solution and answer

Answer and solution

More Lexical analysis questions