Question

A lexical analyzer uses the following token definitions:

• \(letter \rightarrow [A-Za-z]\)
• \(digit \rightarrow [0-9]\)
• \(id \rightarrow letter\,(letter\,|\,digit)^{*}\)
• \(number \rightarrow digit^{+}\)
• \(ws \rightarrow (blank\,|\,tab\,|\,newline)^{+}\)

For the string given below,
\[ x1\ \ 23mm\ \ 78\ \ y\ \ 7z\ \ zz5\ \ 14A\ \ 8H\ \ AaYcD \]
the number of tokens (excluding \(ws\)) that will be produced by the lexical analyzer is ______.

Hint:

Use maximal munch: a number token can only contain digits and stops the instant a letter appears, while an id can mix letters and digits once it starts with a letter.

Answer 1

Correct Answer: 13

Step 1: Note the two competing rules and how a scanner picks between them.
A $number$ is one or more digits and nothing else, since its rule is just $digit^{+}$. An $id$ starts with a letter, and after that first letter it can mix letters and digits freely, since its rule is $letter\,(letter\,|\,digit)^{*}$. A real scanner reads left to right and always grabs the longest run of characters that still matches a rule (this is maximal munch). So the very first character of a chunk decides which rule takes over: start on a digit and you get a $number$ that stops dead the instant a letter appears, start on a letter and the whole rest of the chunk, letters and digits both, gets swallowed into one $id$.

Step 2: Work through the string in its 9 space separated chunks, using this rule.
$x1$: the scanner starts on the letter $x$, so it keeps going through the digit $1$ as well, since digits are allowed inside an $id$ after the first letter. The whole chunk is one $id$, giving 1 token.
$23mm$: the scanner starts on a digit, so it grabs $2$ then $3$ as a $number$ and stops the moment it hits the letter $m$, since a $number$ cannot contain letters. It then starts fresh at $m$, which begins a new $id$ covering $mm$. That is a $number$ plus an $id$, giving 2 tokens.
$78$: both characters are digits, so the scanner just keeps extending the $number$ to the end of the chunk with nothing left over. One $number$ token.
$y$: a single letter starts and ends an $id$ with nothing more to add. One $id$ token.
$7z$: the scanner starts on digit $7$, builds a $number$, and stops at the letter $z$, exactly like the $23mm$ case. The leftover $z$ becomes its own $id$. That is 2 tokens.
$zz5$: the scanner starts on the letter $z$, so once it commits to building an $id$ it is allowed to keep pulling in more letters and even the digit $5$ at the end. Nothing gets split off, so the whole chunk is a single $id$, 1 token.
$14A$: digits $1$ and $4$ build a $number$ first, stopping at the letter $A$, which then becomes a separate $id$. That is 2 tokens.
$8H$: the lone digit $8$ becomes a $number$, and the lone letter $H$ becomes a separate $id$, since a $number$ can never absorb a trailing letter. That is 2 tokens.
$AaYcD$: the scanner starts on the letter $A$ and every character after it is also a letter, so the whole five character chunk is swallowed into a single $id$. One token.

Step 3: Lay the token counts out chunk by chunk in the order they appear.
$$ 1,\ 2,\ 1,\ 1,\ 2,\ 1,\ 2,\ 2,\ 1 $$
These correspond in order to $x1$, $23mm$, $78$, $y$, $7z$, $zz5$, $14A$, $8H$, $AaYcD$.

Step 4: Sum the list to get the total token count.
$$ 1+2+1+1+2+1+2+2+1 = 13 $$

Step 5: Remember the whitespace is not part of this count.
The blanks between the 9 chunks are matched by the separate rule $ws \rightarrow (blank\,|\,tab\,|\,newline)^{+}$, and the question specifically asks to exclude $ws$ tokens from the count, so those gaps contribute nothing to the answer.

Step 6: Conclude.
$$ \boxed{13} $$