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: Understand how the lexer breaks up each word.
The lexer always tries to build the longest possible token starting at the current position (the usual maximal munch rule). If the current character is a digit, it keeps consuming digits to build a \(number\) token, and stops the instant a letter appears, since \(number\) can only be made of digits. If the current character is a letter, it keeps consuming letters or digits to build a single \(id\) token, since the rule \(id \rightarrow letter\,(letter\,|\,digit)^{*}\) allows digits after the first letter. Blanks between words are \(ws\) tokens and are not counted.

Step 2: Tokenize "x1".
It starts with the letter \(x\), so the whole chunk \(x1\) (letter followed by a digit) matches the \(id\) rule as one token. This gives 1 token.

Step 3: Tokenize "23mm".
It starts with digit \(2\), so the lexer grabs digits only: \(23\) becomes a \(number\) token, stopping at \(m\) because \(number\) cannot include letters. The remaining \(mm\) starts with a letter, so it becomes one \(id\) token. This gives 2 tokens.

Step 4: Tokenize "78".
All characters are digits, so \(78\) is a single \(number\) token. This gives 1 token.

Step 5: Tokenize "y".
A single letter matches \(id\). This gives 1 token.

Step 6: Tokenize "7z".
It starts with digit \(7\), so \(number\) grabs just \(7\) and stops at the letter \(z\). The remaining \(z\) is an \(id\) token. This gives 2 tokens.

Step 7: Tokenize "zz5".
It starts with the letter \(z\), and since \(id\) allows letters or digits after the first letter, the whole chunk \(zz5\) is consumed as one \(id\) token. This gives 1 token.

Step 8: Tokenize "14A".
It starts with digit \(1\), so \(number\) grabs \(14\) and stops at the letter \(A\). The remaining \(A\) becomes an \(id\) token. This gives 2 tokens.

Step 9: Tokenize "8H".
Digit \(8\) forms a \(number\) token, and letter \(H\) forms a separate \(id\) token. This gives 2 tokens.

Step 10: Tokenize "AaYcD".
It starts with the letter \(A\), and every following character is a letter, so the whole chunk matches \(id\) as one token. This gives 1 token.

Step 11: Add up all the tokens.
\[ 1+2+1+1+2+1+2+2+1 = 13 \]

Step 12: Final answer.
\[ \boxed{13} \]