Tokenization Problem

Question

Yes, this is a quiz question. It's from a self-paced course, but the answer just isn't correct to me no matter how I look at it. There isn't really an active community to consult.

My Regular Expression experience is profoundly in JavaScript and I'm concerned that it poisoned my thinking of Regular Expressions. For the life of me I can't figure this out. Answer A and Answer B I can rationalize, though my logic might be inherently flawed somehow. Being unable to understand how Answer C works brings me to the conclusion that I am profoundly missing something.

The Problem:

Consider the string abbbaacc Which of the following lexical specifications produces the tokenization ab/bb/a/acc ?

Answer A
a(b + c*) 
b+

Answer B
ab
b+
ac*

Answer C
c*
b+
ab
ac*

The two ways that I have tried to resolve Answer C

removing tokens(which I assumed is the correct way.)

abbbaacc

c* passes and returns token **cc**  //abbbaa
b+ passes and returns token **bbb** //aaa
ab passes and returns no token //aaa
ac* passes and returns no token //aaa
ending tokens: 
[cc, bbb]

Keeping String Whole:

abbbaacc

c* passes and returns **cc**
b+ passes and returns **bbb**
ab passes and returns **ab**
ac* passes and returns **acc**
ending tokens:
[cc, bbb, ab, acc]

I've tried other random ways as well but nothing turns out. I really am frustrated with this problem and I've been working on it for quite some time. I've reviewed the coursework that I have and I'm just at a loss. I am convinced that I must be conflating the more common Regular Expressions with this but I don't see where I'm doing so in any way that would make this answer correct. If anyone could provide any assistance I would greatly appreciate it!

Answer 1

Tokenisation does not search. [Note 1]. At each step, it matches (and consumes) a match of one of the patterns starting precisely at the current input point.

Although there are other tokenisation algorithms, the most common one -- usually called maximal munch -- works as follows.

At each step:

• Find the longest match of each pattern starting at the current input point. (This can be done in a single linear-time left-to-right scan of the input.)

• Select the longest of all these matches. If more than one pattern has the same longest match, select the pattern which comes first in the list of patterns. Report the selected pattern and the corresponding matched prefix as the next token.

• Remove the matched prefix from the input, and continue from the first step.

In effect, the match in the first step is a match of a regular expression created from the disjunction of all the patterns. The regular expression matching algorithm is modified so that:

• It also reports which alternative matched, and

• It leaves unmatched input in the input strean, rather than insisting that the regular expression match the entire input.

For your answer C, the regular expression created is $c^*+b^++ab+ac^*$. (Some tokenisers would correct the first pattern to $c^+$ because selecting an empty match would cause the above algorithm to fall into an endless loop.)

The longest prefixes successively matched by this disjunction are:

• $ab$ (3rd alternative). The 4th alternative matches $a$, but that us shorter.

• $bb$ (2nd alternative) The second alternative will also match $b$, but that's not the longest prefix matched by this pattern.

• $a$ (4th alternative)

• $acc$ (4th alternative)

---

Notes

1. This should be intuitive. After all, most programs are read left to right and token order matters: $a = b + c;$ cannot be written as $a b c =+ ;$, and the parser will expect to see the tokens in left-to-right order, so if the lexer produced the stream, $a b c =+ ;$, the parser would get confused.